鉴于120GB的硬盘驱动器,其中100个充满了长度为256和2 GB的字符串,我如何最有效地在Java中对这些字符串进行排序？这需要多长时间？
Hig*_*ark 22
A1.您可能希望实现某种形式的合并排序.
A2:比你机器上有256GB RAM的时间要长.
编辑:受批评指责,我引用维基百科关于合并排序的文章:
合并排序本质上是顺序的,使用慢速磁带驱动器作为输入和输出设备来运行它是切实可行的.它只需要很少的内存,所需的内存不依赖于数据元素的数量.
出于同样的原因,对于太大而无法完全适合主存储器的磁盘上的数据进行排序也很有用.在可以向后和向前运行的磁带驱动器上,可以在两个方向上运行合并传递,从而避免重绕时间.
Ste*_*n C 18
我是这样做的:
阶段1是将100Gb拆分为50个2Gb分区,将50个分区中的每个分区读入内存,使用快速排序进行排序,然后写出.您希望排序的分区位于光盘的顶端.
阶段2然后合并50个已排序的分区.这是棘手的一点,因为光盘上没有足够的空间来存储分区和最终排序的输出.所以......
进行50路合并以填充光盘底端的第一个20Gb.
将50个分区中的剩余数据滑动到顶部,以使另一个20Gb的可用空间与第一个20Gb的末端相邻.
重复步骤1.和2.直到完成.
这会占用很多光盘IO,但您可以利用2Gb内存来缓冲复制和合并步骤,通过最小化光盘搜索次数来获取数据吞吐量,并进行大量数据传输.
编辑 - @meriton提出了一种减少复制的聪明方法.他没有滑动,而是建议将分区按顺序排序,并在合并阶段向后读取.这将允许算法通过简单地截断分区文件来释放分区使用的磁盘空间(阶段2,步骤2).
这可能的缺点是磁盘碎片增加,以及由于向后读取分区而导致性能下降.(在后一点上,在Linux/UNIX上向后读取文件需要更多的系统调用,而FS实现可能无法反向执行"预读".)
最后,我想指出,任何理论上对该算法(和其他算法)所用时间的预测都是猜测工作.这些算法在真正的JVM +真实操作系统+真实光盘上的行为对于"回到包络"计算来说太复杂了,无法给出可靠的答案.适当的处理需要实际实施,调整和基准测试.
Sea*_*wen 17
我基本上重复克里斯蒂安的答案,但详细说明:
是的,您需要或多或少地执行此操作,因为您可用的RAM很少.但是天真的原地排序将是一场灾难,仅仅是因为移动字符串的成本.
而不是实际移动字符串,只需跟踪哪些字符串应与其他字符串交换并实际移动它们,最后一次到达最终位置.也就是说,如果您有1000个字符串,请创建一个1000个整数的数组.array [i]是字符串i应该结束的位置.如果最后是array [17] == 133,则意味着字符串17应该在字符串133的最后位置.array [i] == i表示所有i的开始.然后,交换字符串只是交换两个整数的问题.
然后,像quicksort这样的任何就地算法都能很好地工作.
运行时间肯定是由弦的最后移动决定的.假设每一个都移动,你就会在合理大小的写入中移动大约100GB的数据.我可能会认为驱动器/控制器/操作系统可以为您移动大约100MB /秒.那么,1000秒左右？20分钟？
但它适合记忆吗？你有100GB的字符串,每个字符串是256个字节.多少串？100*2 ^ 30/2 ^ 8,或约419M字符串.您需要419M整数,每个是4个字节,或大约1.7GB.瞧,适合你的2GB.