有效合并排序文件？

Question

我有n文件，50 <= n <= 100包含排序的整数，它们都是相同大小的，250 or或500 or。

e.g

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

我正在一台4核机器上运行这个程序，目标是尽快合并文件。

由于总大小可以达到50‘t，所以我无法将它们读入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个文件x250MB，而有50个文件x500MB，那么它的性能会非常糟糕。

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

Answer 1

首先，您可以通过改进算法中的步骤(2)来显着地提高效率。相反，要对所有数字进行线性搜索，使用min堆，任何从堆中插入和删除最小值的操作都是在对数时间内完成的，因此它将提高大量文件的速度。这就改变了O(nlogk)的时间复杂性，通过简单的O(n*k) (其中n是元素的总数，k是文件的数量)。

此外，您还需要最小化文件中的“随机”读取数，因为很少有顺序的大读取比许多小的随机读取快得多。您可以通过增加缓冲区大小来做到这一点，例如(写入也是如此)。

Answer 2

(java)使用GZipInputStream和GZipOutputStream进行.gz压缩。也许这会在一定程度上允许内存的使用。使用快速而不是高压缩。

然后，几个文件在磁盘上的移动应该减少，例如，更多合并文件的2个文件，两个较大的序列。

对于重复，可以使用“运行长度-编码”代替重复，添加一个重复计数：11 12 13#7 15。

Answer 3

利用多核的一种有效方法可能是在与主比较线程不同的线程中执行输入和输出，使所有核都保持忙碌，并且主线程不会不必要地阻塞输入或输出。一个线程执行核心比较，一个线程写入输出，NumCores-2处理输入(每个线程来自输入文件的子集)，以保持主线程的供给。

输入和输出线程还可以执行特定于流的预处理和后处理--例如，根据输入数据的分布，@Joop所提到的类型的运行长度编码方案可以有效地排序整个输入范围，从而大大加快主线程的速度。

当然，所有这些都增加了复杂性和出错的可能性。