使用最少的内部存储器资源有效地为磁盘排序字符串的算法

Question

我有一个非常(多个terrabytes)大量的字符串存储在磁盘上,我需要按字母顺序排序并尽快存储在另一个文件中(最好是在C/C++中)并使用尽可能少的内部存储器.事先预先索引字符串不是一个选项,因此我需要在接近实时的时候对需要的字符串进行排序.

在我的情况下,最好的算法是什么？我更喜欢线性算法的建议,而不仅仅是像Lucene这样的现有软件库的链接.

Answer 1

您通常会将大量外部数据分块,然后对其进行操作并最终将它们合并.在选择排序算法时,您通常会查看您的要求:

• 如果您需要一个稳定的时间复杂度保证,您可以使用mergesort(保证为O(nlogn)),尽管它需要额外的O(n)空间.

• 如果存在严重的内存限制,您可能需要尝试Smoothsort(常量内存,时间O(nlogn))

否则,您可能需要查看gpgpu加速器字段中的研究内容,如GPUTeraSort.

谷歌服务器通常会遇到这类问题.

Answer 2

简单构建数字树（Trie） 内存将比输入数据少得多，因为许多单词将具有公共前缀。在向树添加数据时，您将最后一个子标记（增量）标记为单词结尾。如果你添加所有单词，那么你会执行DFS（优先级为你想要排序的 ex a->z ）并将数据输出到文件。时间复杂度与内存大小完全相同。很难说复杂性如何，因为它取决于字符串（许多短字符串的复杂性更好），但它仍然比输入数据 O(n*k)（其中 n 个字符串）要好得多；k-字符串的平均长度。我对我的英语感到抱歉。

附言。为了解决内存大小的问题，你可以将文件分成最小的部分，用我的方法对它们进行排序，如果你有ex（1000个文件），你将记住每个第一个单词（如），下一个你将queues输出正确的单词并在很短的时间内输入下一个。