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

loveczp 发布于 2011/08/04 02:18
阅读 15K+
收藏 4

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

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

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

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

加载中
0
华宰
华宰

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

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

loveczp
loveczp
就是存有很多数据项的文件里面的数据项排序,排好序之后然后存到另一个文件里面
0
笨蛋EGG
笨蛋EGG

相当有意义的课题,坐等答案!

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

0
h
hjhjsword
堆排序行不?
0
hawkyoung
hawkyoung

很关键的问题

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

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

0
hawkyoung
hawkyoung
还有数据数值的范围?
0
bastetwang
bastetwang
用基于磁盘的二叉树(数据库都一直这么干的)
0
卢温禾
卢温禾
为什么要排序啊?
0
hawkyoung
hawkyoung

如果数据数据之间没有重复,而且是整数,可以用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的位操作有一定开销,但总比磁盘来回几次好。

 

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

hawkyoung
hawkyoung
@陈作平 : 现成的算法可能没有,您可以参考《编程珠玑》中关于字符串处理那一章的内容,希望对您有帮助
loveczp
loveczp
这个方法不错,很有启发。不过如果排序的内容是不定长字符串这个方法可能就不适用啊。
0
-10
-10
个人来试试,先将整个的数据,分成比如说 10 份, 每一份在内存中拍好序,在写会磁盘保存,接着排序下一份,最后将排好序的数据合并。
返回顶部
顶部