algorithm - シャッフルされたリストをインプレースで O(1) メモリで出力するアルゴリズム

Question

この質問を読んだ後、私は疑問に思い始めました:元のリストを変更またはコピーしないシャッフルアルゴリズムを持つことは可能ですか?

明確にするために：

オブジェクトのリストが与えられたと想像してください。リストのサイズは任意ですが、かなり大きいと仮定します (たとえば、10,000,000 アイテム)。リストの項目をランダムな順序で印刷する必要があり、できるだけ速くそれを行う必要があります。ただし、次のことを行うべきではありません。

• 元のリストは非常に大きく、コピーすると大量のメモリが浪費されるため (おそらく使用可能な RAM の制限に達する)、元のリストをコピーします。
• 元のリストは何らかの方法でソートされており、後で他の部分がソートされることに依存するため、元のリストを変更します。
• 繰り返しになりますが、リストは非常に大きく、コピーには多くの時間とメモリが必要になるため、インデックス リストを作成します。(明確化: これは、元のリストと同じ数の要素を持つ他のリストを意味します)。

これは可能ですか？

追加:より明確化。

1. すべての順列が同じ確率で真のランダムな方法でリストをシャッフルする必要があります (もちろん、最初に適切な Rand() 関数があると仮定します)。
2. ポインターのリスト、インデックスのリスト、または元のリストと同じ数の要素を持つその他のリストを作成するという提案は、元の質問によって非効率的であると明示的に見なされます。必要に応じて追加のリストを作成できますが、元のリストよりも桁違いに小さいものにする必要があります。
3. 元のリストは配列のようなもので、O(1) のインデックスによって任意の項目を取得できます。(したがって、目的のアイテムに到達するためにリストを反復処理する必要がある、二重にリンクされたリストのものはありません。)

追加 2 : OK、次のように言いましょう: 1 TB の HDD があり、それぞれ 512 バイト (単一セクター) のデータ項目でいっぱいです。すべてのアイテムをシャッフルしながら、このすべてのデータを別の 1TB HDD にコピーします。これをできるだけ速く実行したい (データの単一パスなど)。512MB の RAM が利用可能であり、スワップは必要ありません。(これは理論上のシナリオです。実際にはこのようなものはありません。完璧なアルゴリズムを見つけたいだけです。)

Answer 1

それは、シャッフル以外のランダム性の種類に少し依存します。つまり、すべてのシャッフルが可能性があるか、分布が歪んでいる可能性があります。

N 個の整数の「ランダムに見える」順列を生成する数学的方法があるため、P が 0..N-1 から 0..N-1 への順列である場合、x を 0 から N-1 まで繰り返すだけで、 L(x) の代わりにリスト項目 L(P(x)) を出力すると、シャッフルが得られます。このような順列は、例えば剰余演算を使用して取得できます。たとえば、N が素数の場合、P(x)=(x * k) mod N は任意の 0 < k < N の順列です (ただし、0 を 0 にマップします)。素数 N についても同様に、たとえば P(x)=(x^3) mod N は順列である必要があります (ただし、0 を 0 に、1 を 1 にマップします)。この解は、N より上の最小の素数 (M と呼びます) を選択し、M まで並べ替え、N より上の並べ替えられたインデックスを破棄することにより、非素数 N に簡単に拡張できます (以下も同様)。

累乗剰余は、多くの暗号化アルゴリズム (RSA、Diffie-Hellman など) の基礎であり、この分野の専門家によって強力な疑似乱数操作と見なされていることに注意してください。

もう 1 つの簡単な方法 (素数を必要としない) は、最初に定義域を拡張して、N の代わりに M を考慮します。ここで、M は N の上の 2 の累乗の最小値です。たとえば、N=12 の場合、M=16 を設定します。次に、全単射ビット操作を使用します。

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

次に、リストを出力するときに、x を 0 から M-1 まで反復し、P(x) が実際に < N である場合にのみ L(P(x)) を出力します。

「真の偏りのないランダム」ソリューションは、暗号学的に強力なブロック暗号 (AES など) とランダム キー (k) を修正し、シーケンスを反復することで構築できます。

AES(k, 0), AES(k, 1), ...

そして、AES(k,i) < N の場合、シーケンスから対応するアイテムを出力します。これは、一定の空間 (暗号に必要な内部メモリ) で実行でき、ランダム順列と区別がつきません (暗号の暗号特性による)。 ）しかし、明らかに非常に遅いです。AES の場合、i = 2^128 になるまで繰り返す必要があります。

Answer 2

コピーを作成したり、変更したり、アクセスした要素を追跡したりすることは許可されていませんか? 私はそれが不可能だと言うつもりです。私があなたの3番目の基準を誤解していない限り。

10,000,000 の対応するブール値の配列を作成し、対応する要素を印刷したときに true に設定することは許可されていないことを意味します。また、10,000,000 個のインデックスのリストを作成し、リストをシャッフルして、要素をその順序で出力することは許可されていません。

Answer 3

次のいずれかを行う必要があるため、真の乱数ジェネレーターでこれを行うことはできません。

• どの数字がすでに選択されているかを覚えておいて、それらをスキップします (これにはブール値の O(n) リストが必要で、スキップする数字が増えるにつれて実行時間が徐々に悪化します)。また
• 各選択後にプールを減らします (元のリストを変更するか、別の O(n) リストを変更する必要があります)。

どちらもあなたの質問の可能性ではないので、「いいえ、できません」と言わざるを得ません。

この場合、使用された値のビット マスクを使用する傾向がありますが、前述のように、使用された値が蓄積されると実行時間が悪化するため、スキップではありません。

ビット マスクは、39Gb の元のリスト (1000 万ビットは約 1.2M にすぎません) よりも大幅に優れています。これは、まだ O(n) ですが、要求されたよりも桁違いに小さくなっています。

実行時の問題を回避するには、乱数を毎回 1 つだけ生成し、関連する「使用済み」ビットが既に設定されている場合は、設定されていないビットが見つかるまでビット マスクを順方向にスキャンします。

つまり、乱数ジェネレーターがまだ使用されていない数値を取得することを切望してぶらぶらしている必要はありません。実行時間は、1.2M のデータをスキャンするのにかかる時間と同じくらい悪くなります。

もちろん、これは、いつでも選択された特定の数が、すでに選択されている数に基づいて歪められていることを意味しますが、それらの数はとにかくランダムであるため、歪曲はランダムです (そして、数が最初から真にランダムではなかった場合、その場合、ゆがみは問題になりません)。

もう少し多様性が必要な場合は、検索方向を交互に (上または下にスキャン) することもできます。

結論：あなたが求めていることが実行可能だとは思いませんが、妻が迅速かつ頻繁に証明するように、私は以前に間違っていたことを覚えておいてください:-) しかし、すべてのものと同様に、通常は方法がありますそのような問題を回避します。

Answer 4

これらの 10,000,000 項目は、実際の項目への参照 (またはポインター) にすぎないため、リストはそれほど大きくありません。すべての参照 + そのリストの内部変数のサイズに対して、32 ビット アーキテクチャでは最大 40 MB しかありません。アイテムが基準サイズよりも小さい場合は、リスト全体をコピーするだけです。

Answer 5

以下は、どの PRNG スキームも機能しないという非常に単純な証明です。

PRNG のアイデアには 2 つのフェーズがあります。まず、PRNG とその初期状態を選択します。次に、PRNG を使用して出力をシャッフルします。さて、Nがあります！可能な順列なので、少なくともN!が必要です。これは、フェーズ 2 の開始時に、少なくともlog ₂ N!が必要であることを意味します。許可されていない状態のビット。

ただし、これは、アルゴリズムが進行中に環境から新しいランダム ビットを受け取るスキームを除外するものではありません。たとえば、初期状態を遅延して読み取るが、繰り返さないことが保証されている PRNG があるかもしれません。ないことを証明できますか？

完全なシャッフル アルゴリズムがあるとします。実行を開始し、半分まで完了したら、コンピューターをスリープ状態にするとします。これで、プログラムの完全な状態がどこかに保存されました。この中間点でプログラムが取り得るすべての状態の集合を S とします。

アルゴリズムは正しく、終了することが保証されているため、保存されたプログラムの状態と十分な長さのビット列が与えられると、シャッフルを完了するディスクの読み取りと書き込みの有効なシーケンスを生成する関数fがあります。コンピュータ自体がこの機能を実装しています。しかし、それを数学関数と考えてください:

f : (S × ビット) → 読み取りと書き込みのシーケンス

次に、自明ですが、保存されたプログラムの状態のみが与えられると、まだ読み書きされていないディスクの場所のセットを生成する関数gが存在します。(任意のビット列をfに渡すだけで、結果を確認できます。)

g : S →読み書きする場所のセット

証明の残りの部分は、アルゴリズムの選択に関係なく、gの定義域が少なくとも_N C _{N/2 個の異なるセットを含むことを示すことです。}そうである場合、 Sには少なくともその数の要素が存在する必要があるため、プログラムの状態には、要件に違反して、中間点に少なくともlog _{2 N} C _{N/2ビットが含まれている必要があります。}

ただし、アルゴリズムによっては、読み取る場所のセットまたは書き込む場所のセットのいずれかが低エントロピーになる可能性があるため、最後のビットを証明する方法がわかりません。問題を解決できる情報理論の明らかな原理があるのではないかと思います。誰かが提供してくれることを期待して、このコミュニティ wiki にマークを付けます。

Answer 6

それは不可能に聞こえます。

しかし、10,000,000 個の 64 ビット ポインターは約 76MB しかありません。

Answer 7

線形フィードバック シフト レジスタは、ほとんどのことを行うことができます。数値のリストを、ある程度の制限まで生成しますが、(合理的に) ランダムな順序で生成します。それが生成するパターンは、ランダム性を試すことから期待されるものと統計的に類似していますが、暗号学的に安全でさえありません. Berlekamp-Massey アルゴリズムを使用すると、出力シーケンスに基づいて同等の LFSR をリバース エンジニアリングできます。

〜10,000,000項目のリストの要件を考えると、24ビットの最大長LFSRが必要になり、リストのサイズよりも大きい出力を単純に破棄します。

それだけの価値があるため、LFSR は一般に、同時期の典型的な線形合同 PRNG と比較して非常に高速です。ハードウェアでは、LFSR は非常に単純で、N ビットのレジスタと M 個の 2 入力 XOR (M はタップの数です。場合によっては 2 つだけで、半ダース程度を超えることはめったにありません) で構成されます。

Answer 8

基本的に必要なのは、0..n-1の数値をそれぞれ1回だけ生成する乱数ジェネレーターです。

中途半端なアイデアは次のとおりです。nよりわずかに大きい素数pを選択し、乗法群mod pの順序がp-1である1とp-1の間のランダムxを選択することでかなりうまくいく可能性があります（ランダムxsとi<p-1に対してx^i！= 1を満たすものをテストします。1つを見つける前に、いくつかテストするだけで済みます）。次にxがグループを生成するので、1 <= i<=p-2のx^i mod pを計算するだけで、2とp-1の間のp-2個の異なるランダムな数が得られます。2を引き、> = nのものを捨てると、印刷する一連のインデックスが得られます。

これはそれほどランダムではありませんが、同じ手法を複数回使用して、上記のインデックス（+1）を取得し、それらを別の素数p2を法とする別のジェネレータx2の指数として使用できます（n <p2 <pが必要です）。 、 等々。十数回繰り返すと、物事はかなりランダムになります。

Answer 9

ブロック暗号を使用して、疑似乱数の「安全な」順列を作成できます。こちらを参照してください。彼らの重要な洞察は、n ビット長のブロック暗号が与えられた場合、「折りたたみ」を使用して m < n ビットに短縮できることです。範囲外の値を破棄する時間。

Answer 10

十分なスペースがある場合は、ノードのポインターを配列に格納し、ビットマップを作成して、次に選択したアイテムを指すランダムな int を取得できます。すでに選択されている場合 (ビットマップに保存)、アイテムがなくなるまで、最も近いもの (左または右、ランダム化できます) を取得します。

十分なスペースがない場合は、ノードのポインターを保存せずに同じことを行うことができますが、時間がかかります (これは時空間のトレードオフです ☺)。