可以使用MapReduce进行2 ^ 32个数字的随机随机播放

排序2 ^32个数字的典型算法是:

创建一个包含2 ^32个数字的数组,并从0到2 ³² -1 填充它们

设n =数组中的项数= 2 ³²

随机选择一个从0到n-1的数字,从数组中删除数字,并将其推入堆栈

现在,n减1,堆栈大小增加1

转到3.直到数组为空,最后的堆栈才是解决方案

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

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

由于我在一台机器上没有那么多内存,因此使用memmap()可能是一个很好的选择(可能是最直接的方法).

出于好奇,我想知道我是否可以使用MapReduce来解决这个问题？Map和Reduce功能会是什么样的？

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

虽然可以选择适合MapReduce的等效算法,但可能很难想出一个不会降低上述算法随机性的算法.

"MapReduce:大型集群上的简化数据处理"一文描述了(第3页,第3节之前)如何使用MapReduce进行分布式排序.对2 ^ 32个数字进行随机混洗的一种方法是给每个数字一个随机生成的80位密钥,然后用这个密钥对数字+密钥进行排序.使用80位密钥时,关系很少(预期数量约为2 ^ -17),您可以使用最终传递将它们按随机顺序排列.

毫无疑问,如果你准备做很多相对较低级别的编程,有更好的方法可以做到这一点,但是随机的随机播放和排序都需要在机器之间进行大量严重的数据移动,这很可能是很多工作将被用于使排序变得聪明 - 这样你就可以重用它.