1

原来的问题是这样的：
你要对 1PB 大小的整数进行排序，范围是 -2^31 ~ 2^31 - 1 (int)，你有 1024 台机器，每台机器有 1TB 磁盘空间和 16GB 内存空间。假设磁盘速度为 128MB/s (r/w)，内存速度为 8GB/s (r/w)。CPU时间可以忽略。为简单起见，可以忽略网络传输时间。计算所需的近似时间。

我知道通过外部排序，我们可以在大约 10 小时内对单台机器上的 1TB 数据进行排序，计算如下：

磁盘访问（2r2w）：1T * 4 / 128MB/s = 2 ^ 15 sec ~ 9 hrs
内存访问：
将 2^48 个整数分成 64 个部分（每个 2 ^ 42 个）大约需要 1.3 分钟。所以总共1.4小时。
63 路合并需要几秒钟，因此被忽略。

但是下一步呢：1024T数据的组合呢？我不知道这是如何计算的。那么有什么帮助吗？

4

1 回答 1

1

2^31 = 20 亿（2“千兆”）。因此，您正在查看大量重复数字和固定范围。所以考虑基数排序（http://en.wikipedia.org/wiki/Radix_sort）。

每个处理器，对于一个子集 od 数据）创建“计数”数组（x[0] 包含 0 的计数等）。然后您可以将所有结果合并到一个数组中。稍后您可以“构造”排序后的数组。

于 2013-02-27T01:20:41.693 回答