4

有关于合并排序文件或合并 K 排序文件的不错的文献。他们都基于这样一个理论,即每个文件的第一个元素都放在一个堆中,然后直到堆为空轮询该元素,然后从该元素所在的文件中获取另一个元素。只要可以将每个文件的一条记录放在堆中,这就会起作用。

现在让我们说我有 N 个已排序的文件,但我只能将 K 条记录放入堆中并且 K < N 并让我们说 N = Kc 其中“c”是乘数,意味着 N 太大以至于它是 c 的某个倍数. 显然,它需要一遍又一遍地进行 K 路合并,直到我们只剩下 K 个文件,然后我们将它们作为最后一次合并到最终排序中。我如何实现这一点,这将是什么复杂性?

4

2 回答 2

3

有多个用 Java 编写的 k-way 合并示例。一个是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) pass。也就是说,如果您有 1,024 个文件并且一次只能合并 16 个,那么您将进行一次合并 16 个文件的过程,总共创建 64 个文件。然后,您将进行另一遍,一次合并 16 个文件,创建四个文件,最后一遍将合并这四个文件以创建输出。

如果你有 k 个文件,每个文件包含 n 个项目,那么合并它们的复杂度是 O(n*k log 2 k)。

因此,在第一遍中,您进行 M/k 合并,每个合并的复杂度为 O(nk log k)。那是 O((M/k) * n * k * log 2 k),或 O(Mn log k)。

现在,您的每个文件都包含 n k k 个项目,并且您每个都对 k 个文件进行 M/k/k 合并。所以第二遍复杂度是 O((M/k 2 ) n * k 2 * log 2 k)。简化后,这也适用于 O(Mn log k)。

在第二遍中,您进行 k 次合并,每个合并的复杂度为 O(nk)。请注意,在每次传递中,您都在使用 M*n 项。所以你做的每一遍都是O(Mn log k)。你正在做 log k (M) pass。所以总复杂度是:O(log k (M) * (Mn log k)),或者

O((Mn log k) log M)

每个文件包含相同数量的项目的假设不会影响渐近分析,因为正如我所展示的,每次传递都操作相同数量的项目:M*n。

于 2017-12-22T15:05:56.017 回答
-1

这是我所有的想法

我会在迭代中做到这一点。首先,我会进行 p=floor(n/k) 迭代以获取 p 排序文件。然后继续对 p+n%k 个项目执行此操作,直到 p+n%k 变得小于 k。然后最后会得到排序后的文件。

是否有意义?

于 2017-12-22T04:51:50.550 回答