Объединение N отсортированных файлов с помощью K-способа слияния

Question

Существует достаточно литературы о слиянии отсортированных файлов или о слиянии отсортированных файлов. Все они работают над теорией, согласно которой первый элемент каждого файла помещается в кучу, а затем, пока куча не станет пустой, опрашивает этот элемент, получает другой файл из того места, откуда был взят этот элемент. Это работает до тех пор, пока одна запись каждого файла может быть помещена в кучу.

Теперь допустим, что у меня N отсортированных файлов, но я могу занести только K записей в кучу и K

Answer 1

Существует множество примеров k-way merge, написанных на Java. Одним из них является http://www.sanfoundry.com/java-program-k-way-merge-algorithm/.

Чтобы реализовать слияние, вам просто нужно написать простую оболочку, которая постоянно сканирует ваш каталог, загружая файлы вещей, пока не останется только один. Основная идея:

while number of files > 1
    fileList = Load all file names
    i = 0
    while i < fileList.length
        filesToMerge = copy files i through i+k-1 from file list
        merge(filesToMerge, output file name)
        i += k
    end while
end while

Анализ сложности

Об этом легче думать, если предположить, что каждый файл содержит одинаковое количество элементов.

Вы должны объединить M файлов, каждый из которых содержит n элементов, но вы можете объединять одновременно только k файлов. Таким образом, вы должны сделать log_k(M) проходов. То есть, если у вас есть 1024 файла и вы можете объединить только 16 одновременно, то вы сделаете один проход, который объединит 16 файлов за раз, создав в общей сложности 64 файла. Затем вы сделаете еще один проход, который объединяет 16 файлов одновременно, создавая четыре файла, и ваш последний проход объединит эти четыре файла для создания выходных данных.

Если у вас есть k файлов, каждый из которых содержит n элементов, то сложность их объединения составляет O (n * k log₂ k).

Итак, на первом проходе вы выполняете M/k слияний, каждое из которых имеет сложность O(nk log k). Это O ((M/k) * n * k * log₂ k) или O(Mn log k).

Теперь каждый из ваших файлов содержит nk k элементов, и вы выполняете M/k/k слияния по k файлов каждый. Таким образом, сложность второго прохода O ((M/k²) n * k² * log₂ k). Упрощенно, что тоже работает до O(Mn log k).

Во втором проходе вы делаете k слияний, каждое из которых имеет сложность O(nk). Обратите внимание, что на каждом проходе вы работаете с M*n предметами. Таким образом, каждый проход, который вы делаете, является O(Mn log k). И ты делаешь log_k(M) проходов. Таким образом, общая сложность составляет: O (log_k(M) * (Mn log k)) или

O((Mn log k) log M)

Предположение, что каждый файл содержит одинаковое количество элементов, не влияет на асимптотический анализ, потому что, как я показал, каждый проход обрабатывает одинаковое количество элементов: M*n.

Answer 2

Это все мои мысли

Я бы сделал это в итерации. Сначала я бы пошел на итерацию p=floor(n/k), чтобы получить p отсортированный файл. Затем продолжайте делать это для p+n%k элементов, пока p+n%k не станет меньше k. И тогда, наконец, получит отсортированный файл.

Имеет ли это смысл?