用小物理内存对10亿个整数进行排序
用小物理内存对10亿个整数进行排序
提问于 2011-08-26 10:08:27
想要对10亿个整数进行排序，而我的系统只有1GB的RAM.What，这可能是最快和有效的排序方法吗？
- 假设我们在文本文件中有一个输入，每一行一个整数。
- 我们正在使用java程序进行排序。
- 我指定了RAM，因为我们不能保存RAM中的所有输入整数。
更新:整数是7位数。
回答 4
Stack Overflow用户
回答已采纳
发布于 2011-08-26 10:26:05
最简单的方法是将输入分解为较小的文件，这些文件可以放入内存并对每个文件进行排序，然后合并结果。
Guido van Rossum很好地描述了在python中这样做的情况。虽然显然不是同一种语言，但原则是一样的。
Stack Overflow用户
发布于 2011-08-26 10:32:19
整数是7位数。
因此，可能的价值只有1000万。
你有1GB的内存。制作一个计数器数组，每个可能值一个。
读一遍文件，数一数计数器。
完成后，根据最后的计数器值输出数字。
每一个数字最多可发生10亿次。所以32位计数器就足够了。这意味着一个10 mx4字节= 40M字节数组。
Stack Overflow用户
发布于 2011-08-26 10:30:58
使用具有40亿个可能值的BitSet占用512 MB。只需设置您所看到的所有int值，并按顺序写出它们(它们自然排序)
这只有在你不关心重复的情况下才能起作用。
如果计数重复的事情，我仍然会考虑一个内存映射的文件进行计数，或使用合并排序的数据子节。(我相信后者是一个预期的答案)
我最近购买了一台24 GB的个人电脑，它的容量低于1K，所以，除非你受到一个托管解决方案的限制，否则几个GB就不算多了。(或使用移动设备)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7203159
复制相关文章
相似问题
腾讯云开发者
