随机访问随机排列 [英] Random access random permutations

问题描述

我想生成一个非常大的伪随机置换p:[0，n-1]-> [0，n-1]，然后计算m个特定值p [i]，其中m< .是否可以在O(m)时间执行此操作?动机是进行大型并行计算，其中每个处理器仅需要查看一小部分排列，但是排列在处理器之间必须保持一致.

请注意，为了帮助并行处理，计算i值的不相交集的不同过程不应偶然产生i！= j的p [i] == p [j].

解决方案

还有很多 解决方案

EDIT: There is a much more clever algorithm based on block ciphers that I think Geoff will write up.

There are two common algorithms for generating permutations. Knuth's shuffle is inherently sequential so not a nice choice for parallelism. The other is random selection with retry any time repetition is encountered. Random selection is clearly equivalent when applied in any order, thus I propose the following simple algorithm:

1. Randomly sample candidate p[i] in [0,n-1] for each i in Needed (in parallel).
2. Remove all non-collided entries from Needed, as well as (optionally) some deterministic choice from the collisions (e.g., keep p[i] if i < {j | p[j] = p[i]}).
3. Repeat from step 1 with new (smaller) set Needed.

Since we haven't lost entropy in this process, the result is essentially equivalent to sequential random sampling in some different order, starting with the locations i that did not collide (we just didn't know that order in advance). Note that if we used the computed value in a comparison, for example, we would have introduced bias.

这篇关于随机访问随机排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！