Fast Generation of Random Permutations Via Networks Simulation
Fast Generation of Random Permutations Via Networks Simulation
复制标题
通过网络模拟快速生成随机排列
作者：
A. Czumaj;Przemyslawa Kanarek;Mirosław Kutyłowski;Krzysztof Lorys
摘要。考虑均匀分布随机排列的生成问题。也就是说，我们要求对于n个元素的任意排列π，概率为1/n！当1≤I≤n时，机器在包含π(I)的第I个输出单元停止。本文在CREW和EREW两种并行计算模型上研究了这一问题。本文的主要成果是生成随机排列的算法，该算法在O（log log n）时间内运行，并在CREW PRAM上使用O（n1+ O(1)）个处理器。这是该问题的第一个o（log n）时间CREW PRAM算法。在EREW PRAM上，我们提出了一个简单的算法，该算法使用n个处理器和O(n)空间在O（log n）时间内生成一个随机排列。该算法优于以前已知的用于独占写pram的每种算法。这两种算法的共同点和新颖之处在于首先设计一个合适的随机交换网络来生成排列，然后在PRAM模型上快速模拟该网络。
Abstract. We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation π of n elements, with probability 1/n! the machine halts with the i th output cell containing π(i) , for 1 ≤ i ≤ n . We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM. The main result of the paper is an algorithm for generating random permutations that runs in O(log log n) time and uses O(n1+o(1)) processors on the CREW PRAM. This is the first o(log n) -time CREW PRAM algorithm for this problem. On the EREW PRAM we present a simple algorithm that generates a random permutation in time O(log n) using n processors and O(n) space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs. The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way.