用很小的物理内存对10亿个整数进行排序

Question

要对10亿个整数进行排序，而我的系统只有1 GB的RAM。最快、最有效的排序方法是什么?

1. 假设我们在一个文本文件中输入一个每行整数

2. 我们正在用java程序排序

3. 我指定了RAM，因为我们无法在RAM中保存所有输入整数。

更新:整数是7位数字

Answer 1

整数是7位数字。

所以只有1000万个可能的值

你有1GB的RAM。创建一个计数器数组，每个计数器对应一个可能的值。

通读文件一次，计算计数器。

完成后，根据最终计数器的值输出数字。

每个数字最多可以出现10亿次。所以32位计数器就足够了。这意味着10M x 4字节= 40M字节数组。

Answer 2

最简单的方法是将输入分解成可以装入内存的小文件，并对每个文件进行排序，然后合并结果。

Guido van Rossum很好地描述了在python中实现这一点，虽然显然不是同一种语言，但原理是相同的。

Answer 3

您指定要排序的是十亿个7位(十进制)数字。

如果没有重复，您可以使用基数排序在内存中使用10⁷ BITS进行排序。由于必须有重复项(10⁷小于10⁹)，您可以使用(例如)一个包含10⁷ 8位计数器的数组来实现基数排序，并使用HashMap<Integer, Integer>来处理计数器溢出的相对较少的情况。或者只是一个包含10⁷ 32位计数器的数组。

另一种更通用的方法(适用于任何类型的值)是将文件拆分为N个较小的子文件，在内存中对每个子文件进行排序，然后对排序后的子文件执行N向合并。

Answer 4

使用具有40亿个可能值的BitSet占用512 MB。只需设置您看到的所有int值并按顺序写出来(它们自然排序)

这只在你不关心重复项的情况下有效。

如果计数重复的问题，我仍然会考虑要么内存映射文件计数，或使用合并排序数据的子部分。(我相信后者是预期的答案)

我最近花了不到1000英镑买了一台24gb的电脑，所以几GB并不多，除非你受到托管解决方案的限制。(或使用移动设备)

Answer 5

假设每个整数正好出现一次，您可以读取文件，并且对于您发现的每个数字设置一个位-位数组必须保存10000000位-这只使用应该可用的1,28 MB RAM…在你读取了所有的整数之后，你只需要遍历数组并输出一个位列表的数字…