大数据排序问题：10G的数据，在2G内存的单台机器上排序的算法

Question

有10的8次方个数据项，大约要10G的存储空间来存储，给一台单核pc机,内存2G，什么样的算法能够快速计算出结果？

本人初步认为，问题的关键在于减少磁盘的读写次数，因为一次盘操作的时间是一次内存操作时间的上百倍。

普通的排序算法貌似不太可取，因为普通的排序算法中，每一个数据项都有可能要和其他数据项进行比较，然而2G内存无法装入10G的数据，因此普通排序算法肯定会导致多次的读取磁盘，这样就势必会造成在磁盘操作上消耗掉很多时间。

请问大家有没有好的解决方案。

Answer 1

这个方法不错，很有启发。不过如果排序的内容是不定长字符串这个方法可能就不适用啊。

Answer 2

个人来试试，先将整个的数据，分成比如说 10 份， 每一份在内存中拍好序，在写会磁盘保存，接着排序下一份，最后将排好序的数据合并。

Answer 3

现成的算法可能没有，您可以参考《编程珠玑》中关于字符串处理那一章的内容，希望对您有帮助

Answer 4

如果数据数据之间没有重复，而且是整数，可以用bitmap的技巧，我懒得算了，大概10^8个bit 2G内存能装的下？

然后只要一次磁盘读取就可以完成排序（影响效率的关键因素在I／O上，这点没错，CPU优化几百次运算都不如让磁盘少读一个word的数据），读一个数据，对应的bit置位，全部数据读取完，排序就完成了。

例如已知数据范围为1-8 你只有三个数据  1,8,2 最后你的bitmap（用一个byte的空间存储即可）是 11000001

1,2,8三个bit有置位，所以排序出来是 1,2,8。

大bitmap的位操作有一定开销，但总比磁盘来回几次好。

 

这种情况只适合数据不重复，已知数据范围的情况……其他条件的原则也是一样，尽量少倒腾硬盘，最佳情况所有数据过一遍结果就出来

Answer 5

为什么要排序啊？

Answer 6

用基于磁盘的二叉树（数据库都一直这么干的）

Answer 7

还有数据数值的范围？

Answer 8

hadoop

Answer 9

很关键的问题

数据是什么类型的？int long float?

数据数据之间是否有重复？

Answer 10

堆排序行不？

Answer 11

相当有意义的课题，坐等答案！

我一直以为这种极端的东西只能在数据中心的集群中出现……一直不敢有所涉猎……

Answer 12

就是存有很多数据项的文件里面的数据项排序，排好序之后然后存到另一个文件里面

Answer 13

10 的 8 次方，相当于 1 亿条数据。问题是排序后怎么处理呢？

例如是将一个有一亿行数据的文件排序，然后存到另外的文件中？