有效合并排序文件？

Question

我有n文件,50 <= n <= 100包含排序整数,所有文件大小相同,250MB或500MB.

例如

1st file: 3, 67, 123, 134, 200, ...
2nd file: 1, 12, 33, 37, 94, ...
3rd file: 11, 18, 21, 22, 1000, ...

我在4核机器上运行它,目标是尽快合并文件.

由于总大小可以达到50GB,我无法将它们读入RAM.

到目前为止,我尝试执行以下操作:

1) Read a number from every file, and store them in an array.
2) Find the lowest number.
3) Write that number to the output.
4) Read one number from the file you found the lowest before (if file not empty)

重复步骤2-4,直到我们没有数字为止.

使用4MB的缓冲区进行读写.

我上面的算法工作正常,但它没有像我想要的那样快.最大的问题是,如果我有100个文件x 250MB而不是50个文件x 500MB,则表现最差.

在我的案例中,最有效的合并算法是什么？

Answer 1

那么,您可以通过改进算法中的步骤(2)来明智地提高效率.而不是对所有数字进行线性搜索,使用最小堆,任何插入和删除堆中的最小值都是在对数时间内完成的,因此它将提高大量文件的速度.这会改变时间复杂度O(nlogk),超过天真O(n*k)(其中n元素总数和k文件数)

此外,您需要最大限度地减少文件中"随机"读取的次数,因为很少的连续大读取比许多小型随机读取快得多.例如,您可以通过增加缓冲区大小来实现这一点(写入也是如此)