3

非常に大きな疑似乱数順列 p : [0,n-1] -> [0,n-1] を生成し、m << n の場合、m 個の特定の値 p[i] を計算します。O(m)時間でこれを行うことは可能ですか? 動機は、各プロセッサが順列の小さな部分のみを確認する必要がある大規模な並列計算ですが、順列はプロセッサ間で一貫している必要があります。

並列の場合に役立つように、互いに素な i 値のセットを計算するさまざまなプロセスが、誤って i != j に対して p[i] == p[j] を生成してはならないことに注意してください。

4

2 に答える 2

2

編集:ブロック暗号に基づいたもっと賢いアルゴリズムがあり、Geoff が書き上げると思います。

順列を生成するための 2 つの一般的なアルゴリズムがあります。Knuth のシャッフルは本質的にシーケンシャルであるため、並列処理には適していません。もう 1 つは、繰り返しが発生するたびに再試行するランダム選択です。任意の順序で適用された場合、ランダム選択は明らかに同等であるため、次の単純なアルゴリズムを提案します。

  1. for eachの候補p[i]を(並列で) ランダムにサンプリングします。[0,n-1]iNeeded
  2. から衝突していないすべてのエントリを削除しNeeded、(オプションで) 衝突からいくつかの決定論的な選択 (たとえば、p[i]ifを保持i < {j | p[j] = p[i]}) を削除します。
  3. 新しい (より小さい) set でステップ 1 から繰り返しNeededます。

このプロセスでエントロピーが失われていないため、結果は本質的に、i衝突しなかった場所 (事前にその順序を知らなかった) から始まる、いくつかの異なる順序での順次ランダム サンプリングと同等です。たとえば、計算された値を比較に使用すると、バイアスが発生することに注意してください。

于 2012-12-29T02:06:14.280 に答える
0

非常に強度の低いバージョンの例:

  1. 2k = O(1) のランダム整数 a_i,b_i を [0,n-1] に生成します。a_i は n と互いに素です。
  2. 弱い順列 wp : [0,n-1] -> [0,n-1] を選択します。たとえば w(i) = i で上位ビットを除くすべてが反転します。
  3. p[i] = b_0 + a_0 * wp(b_1 + a_1 * wp(... i ...))
于 2012-12-29T01:50:43.810 に答える