如何对值为100GB的字符串进行排序

我基本上是在重复 Krystian's answer ,但详细说明:

是的,您需要或多或少地在适当的位置执行此操作,因为您没有可用的RAM。但是,仅仅因为到处移动弦线的成本,那些天真的地方将是一场灾难。

与其实际移动字符串,不如跟踪哪些字符串应该与其他字符串交换,并在最后一次将它们移动到最终位置。也就是说,如果你有1000个字符串,那么做一个1000个整数的数组。数组[i]是我应该结束字符串的位置。如果末尾的数组[17]==133,则表示字符串17应在字符串133的点处结束。数组[i]==i代表所有i开始。那么,交换字符串只是交换两个整数的问题。

然后,像Quicksort这样的任何就地算法都可以很好地工作。

运行时间肯定是由弦乐的最后一步决定的。假设每一个移动,您将以适当大小的写入操作移动大约100GB的数据。我可能认为驱动器/控制器/OS可以为您移动大约100MB/秒。1000秒左右?20分钟?

但它是否符合记忆?您有100GB的字符串,每个都是256字节。有多少串?100*2^30/2^8,或约419M串。您需要419M的整数,每个是4字节,或者大约1.7GB。瞧,适合你的2GB。

A1您可能希望实现某种形式的 归并分类 .

A2:比机器上256GB内存的时间长。

编辑:被批评刺痛,我引用了维基百科关于合并排序的文章:

合并排序本质上是连续的,因此使用慢速磁带驱动器作为输入和输出设备来运行它是可行的。这需要非常 内存太少,所需的内存不取决于数字 数据元素。

出于同样的原因,它还可用于对磁盘上的数据进行排序,即 太大,无法完全装入主内存。在磁带驱动器上 前后同时运行,合并过程可以同时运行 方向,避免倒带时间。

我可以这样做:

第一阶段是将100GB分成50个2GB的分区,将50个分区中的每一个读到内存中,使用快速排序和写出。您希望将已排序的分区放在磁盘的顶端。

第二阶段是合并50个排序分区。这是一个棘手的问题,因为磁盘上没有足够的空间来存储分区和最终排序的输出。所以…

1. 进行50路合并,以填充光盘底端的前20GB。

2. 将50个分区中的剩余数据滑动到顶部,使另一个20GB的可用空间与前一个20GB的结尾相邻。

3. 重复步骤1。2。直到完成。

这需要大量的磁盘IO,但是您可以利用2GB内存在复制和合并步骤中进行缓冲,从而通过最小化磁盘查找次数来获得数据吞吐量,并进行大量数据传输。

编辑 -@梅里顿提出了一个减少复制的聪明方法。他建议分区按相反的顺序排序,并在合并阶段向后读取,而不是滑动。这将允许算法通过简单地截断分区文件来释放分区(阶段2,步骤2)使用的磁盘空间。

这样做的潜在缺点是增加了磁盘碎片,以及由于向后读取分区而导致的性能损失。(在后一点上,在Linux/Unix上向后读取文件需要更多的系统调用,而FS实现可能无法在相反的方向上进行“提前读取”。)

最后,我想指出的是,任何理论上对该算法(以及其他算法)所用时间的预测,在很大程度上都是猜测。这些算法在真实的JVM+real OS+real磁盘上的行为对于“返回信封”计算来说过于复杂,无法给出可靠的答案。正确的处理需要实际的实现、调整和基准测试。

听起来像是一项需要 External sorting 方法。《计算机程序设计艺术》第三卷包含一节,对外部排序方法进行了广泛讨论。

我想你应该用博戈索特。您可能需要稍微修改算法以允许就地排序,但这不应该太难。:)

你应该使用 trie (又名:前缀树):构建一个类似树的结构,通过比较前缀,您可以轻松地按顺序遍历字符串。事实上,你不需要将它存储在内存中。您可以将trie构建为文件系统上的目录树(显然,不是数据来自的目录树)。

对于afaik,合并排序需要和数据一样多的可用空间。这可能是任何避免随机访问的外部类型的要求,尽管我对此不确定。