分配1亿个具有较小物理内存的整数
想要输出1亿个整数，我的系统只有1 GB的RAM。什么是最快速有效的排序方式？
-
假设我们在文本文件中有一个输入，每行一个整数。
-
我们正在使用java程序进行排序。
-
我已经指定了RAM，因为我们无法保存RAM中的所有输入整数。
更新：整数是7位数字。
最简单的方法是将输入分解为可以放入内存并对每个文件进行排序的较小文件，然后合并结果。
Guido van Rossum很好地描述了在python中这样做，而显然不是同一种语言，原则是相同的。
整数是7位数字。
因此，只有1000万个可能的值。
你有1GB的RAM。 创建一个计数器数组，每个可能的值一个。
通读文件一次，计算计数器。
完成后，根据最终计数器值输出数字。
每个数字最多可以出现10亿次。 所以32位计数器就足够了。 这意味着10M x 4字节= 40M字节数组。
您指定的是排序十亿个7（十进制）数字。
如果没有重复项，您可以使用基数排序在内存中使用10 7 BITS进行排序。 由于你必须有重复项（10 7少于10 9 ），你可以使用（比方说）10 7 8位计数器的数组实现基数排序，使用HashMap来处理相对较少的情况，其中柜台溢出。 或者只是一个包含10 7个32位计数器的arrays。
另一种更通用的方法（适用于任何类型的值）是将文件拆分为N个较小的子文件，对内存中的每个子文件进行排序，然后执行已排序子文件的N路合并。
使用具有40亿个可能值的BitSet占用512 MB。 只需设置您看到的所有int值并按顺序将它们写出来（它们是自然排序的）
这只适用于您不关心重复项的情况。
如果重复计数很重要，我仍然会考虑用于计数的内存映射文件，或者使用合并排序的数据子部分。 （我相信后者是预期的答案）
我最近以低于1K的价格买了一台24 GB的PC，所以除非你受到托管解决方案的限制，否则几GB不会那么多。 （或使用移动设备）
假设每个整数恰好出现一次，你可以读取文件，你找到的每个数字都设置了一个位 – 位数组必须保持10000000位 – 这只使用1,28 MB RAM应该是可用的……你有读取你刚刚遍历数组的所有整数并输出有点设置的数字…