algorithm - 使用 MapReduce 对 2^32 个数字进行随机洗牌的可能性

Question

对 2³² 个数字进行排序的典型算法是:

1. 创建一个由 2³² 个数字组成的数组，并将它们填充为 0 到 2³²-1
2. 令 n = 数组中的项目数 = 2³²
3. 从0到n-1中随机取一个数，从数组中取出数，入栈
4. 现在，n 减 1，堆栈大小增加 1
5. goto 3. 直到数组为空，最后栈就是解

2³² = 4,294,967,296 项

2³² * 4 = 17,179,869,184 字节，如果我们使用 4 字节无符号整数

由于我在一台机器上没有那么多内存，使用 memmap() 可能是一个不错的选择(可能是最直接的方法)。

出于好奇，我想知道是否可以使用 MapReduce 来解决这个问题？ Map 和 Reduce 函数会是什么样子？

这个想法闪过我的脑海，因为虽然我在一台机器上没有那么多内存，但我在局域网上的所有盒子里肯定有那么多内存。 MapReduce 中数据的分布式特性可能会有所帮助。

尽管适合 MapReduce 的替代、等效算法是受欢迎的，但可能很难想出一个不会降低上述算法随机性的算法。

Answer 1

论文“MapReduce:大型集群上的简化数据处理”描述了(第 3 页，就在第 3 节之前)如何使用 MapReduce 进行分布式排序。对 2^32 个数字进行随机洗牌的一种方法是给每个数字一个随机生成的 80 位 key ，然后根据这个 key 对数字+ key 进行排序。使用 80 位 key 时，并列数很少(预期数量约为 2^-17)，您可以使用最终传递将它们放入随机顺序。

毫无疑问，如果您准备进行大量相对低级的编程，那么有更好的方法可以做到这一点，但是随机洗牌和排序都需要在机器之间进行大量重要的数据移动，而且很可能将投入大量工作来使排序更智能 - 这样您就可以重用它。