1

我有一个包含 2^30 个无符号 32 位整数值的文件，我需要对它们进行排序，所以我想用最快的算法来完成它。需要使用所有可用的处理器并且使用不超过 256MB 的内存。

我现在的想法：最大 int 值（对于 32 位整数）Sm= 2^32，最低 = 0。可用内存为 M=2^28。

  • 为

    Sm*(sizeof int)/M = 2^32*2^5/2^28 = 2^9 份；每个零件尺寸 2^32/2^9 = 2^23。

首先，编写一个简单的阅读器，从输入文件中读取 int 值，检查它位于哪个范围内，并将该范围内的整数放入 tempfile。之后我将有 2^9 个文件：

1 file= Integers from 0:2^23
2 file = 2^23:2^24
3 file = 2^24:(2^24+2^23),
and etc...
  • 使用 qsort 或金字塔排序等标准算法进行排序（对此算法有什么建议吗？）

我可以在这里使用 Python.multiprocessing 之类的东西进行并行排序，但它需要在每个进程开始之前安全地计算可用内存

您如何看待这种方法？可能存在更干净和更容易的解决方案吗？

4

5 回答 5

3
  1. 一次读取任何适合您内存的内容（我们称其为块），对其进行排序并将其写回磁盘（即对 256 MB 的块进行排序）
  2. 同时打开所有块，从每个块中读取前 n 个条目并构建一个堆（其中 n 是这样的，您可以填充 256 MBytes）
  3. 从堆中获取最小元素（注意它来自哪个块），将其写入目标文件
  4. 从同一输入块中读取下一个元素并将其添加到堆中并重复上一步，直到处理完所有数据

256 MBytes 是 2^28 字节或 2^26（四字节）整数，因此您只需要对 2^4 = 16 个块进行排序。

于 2012-04-16T12:10:31.450 回答
2

“无符号 32 位整数值”是这里的关键点。您可以使用radix sort 对其进行排序。Wiki 页面提供了 Python 中的完整示例。

由于您没有足够的内存一次对所有内容进行排序，因此您必须将工作分成适合内存的部分，对每个部分进行排序，将结果保存到磁盘，然后以类似于merge sort的 merge pass 的方式合并结果。合并不需要将整个内容加载到内存中，您所要做的就是从部分读取，同时写入最终结果。

于 2012-04-16T12:19:12.693 回答
2

1）。将整数分成几部分

a. [0, 2^20 - 1], [2^20, 2^21 - 1]....

2）。对于每个部分，您可以计算每个整数的计数（类似于基数排序），每个部分的时间复杂度是该部分的长度。并且空间复杂度也是零件的长度。

// for each part
int start = 0;      // the starting point of the part
int end = 2^20 - 1; // the ending point of the part
int *hash = new int[end - start + 1];
for (int i = start; i <= end; ++i) {
    // read a integer val
    ++hash[val];
}
for (int i = start; i <= end; ++i) {
    if (hash[i] > 0) {
        for (int j = 0; j < hash[i]; ++j) {
            // print i
        }
     }
}

3）。因为你有 256MB = 256 * 2^20 = 64 * 2^20(int)，所以你可以并行处理 64 个部分。如果需要，您可以将 2^20 设置为其他值。

4）。无论如何，这个算法的总时间复杂度应该是O(n) + O(2 ^ 32)，n表示整数的个数。当 n 非常大，接近 2^32 时，该算法效果很好。此外，该算法可以并行处理。

5）。该算法不需要合并过程，因为部分已排序。

6）。上面提到的堆解决方案似乎不是并行处理的。

于 2012-04-17T09:10:54.350 回答
1

考虑使用合并排序。可以在此处找到简短描述：http ://en.wikipedia.org/wiki/Merge_sort

合并排序非常适合并行实现和内存限制。

于 2012-04-16T12:22:22.543 回答
0

基数排序通常被称为 O(n)，但实际上是 O(nlogn)，因为它需要的时间与最大数的位数 * 数的个数成正比，并且位数会趋于为log(n)。

我建议使用 3 级复合排序：

  1. 对于长度约为 32 或 64 的小型子列表的插入排序 - 找到最佳的基准 - timsort 为您涵盖了这一点。
  2. 大型子列表的 timsort 或合并排序，直到您的最大物理内存量。timsort 被 Python 和 Java 用于他们的排序方法，并且速度非常快，但它是一种比合并排序更复杂的算法，如果你在 C 之类的东西中工作，这很重要 - 所以如果你只需要一些工作得很好并且是很简单，使用mergesort。
  3. 在大文件中，使用合并排序来合并包含已排序大子列表的已排序文件。

Python 的多处理模块允许您将标量类型（如整数）的数组存储在共享内存中。'只是要记住的事情。

绝对让每个核心对一个大的子列表进行排序 - 这对具有多个核心的系统有很大帮助。有时对#3 使用 minheap 是很好的，有时你最好只使用一个数组（对于较小数量的大型子列表）。

于 2012-04-16T17:50:47.760 回答