7

ランダムな順序で反復したい要素の大きなリストがあります。ただし、リストを変更することはできず、リストのコピーも作成したくありません。1) サイズが大きく、2) 反復が早期にキャンセルされることが予想されるためです。

List<T> data = ...;
Iterator<T> shuffled = shuffle(data);
while (shuffled.hasNext()) {
    T t = shuffled.next();
    if (System.console().readLine("Do you want %s?", t).startsWith("y")) {
        return t;
    }
}
System.out.println("That's all");
return t;

O(n)上記のコードが実行される（そしてできればスペースのみを必要とする）アルゴリズムを探しているO(log n)ので、以前に生成された要素をキャッシュすることはオプションではありません。アルゴリズムが偏っているかどうかは気にしません (明らかでない限り)。

(私の質問では疑似 Java を使用していますが、必要に応じて他の言語を使用することもできます)

これが私がこれまでに得た最高のものです。

Iterator<T> shuffle(final List<T> data) {
    int p = data.size();
    while ((data.size() % p) == 0) p = randomPrime();
    return new Iterator<T>() {
        final int prime = p;
        int n = 0, i = 0;
        public boolean hasNext() { return i < data.size(); }
        public T next() {
            i++; n += prime;
            return data.get(n);
        }
    }
}

、定数空間ですべての要素を反復しますが、順列O(n)しか生成できないため、明らかに偏っています。data.size()

4

4 に答える 4

1

これを行うには、バッファを使用してみてください。限られたデータセットを繰り返し処理し、バッファに入れます。そのバッファからランダムな値を抽出し、出力 (または必要な場所) に送信します。次のセットを繰り返し、このバッファを上書きし続けます。この手順を繰り返します。

最終的には n + n 操作になりますが、これはまだ O(n) です。残念ながら、結果は実際にはランダムではありません。バッファサイズを適切に選択すれば、ランダムに近くなります。

別のメモとして、次の 2 つを確認してください: Python - 非線形の方法でループを実行し、Pythonでランダムな反復

おそらく、これをより適切に行うためのより洗練されたアルゴリズムがあるでしょう。よくわかりませんが。このスレッドの他の回答をお待ちしております。

于 2013-04-23T10:21:17.023 に答える
1

これはあなたの質問に対する完璧な答えではありませんが、おそらく役に立ちます。

アイデアは、可逆乱数ジェネレーターと、通常の配列ベースのシャッフル アルゴリズムを遅延してi使用a[i]することです。これはイテレータで実行できます。a[j]j[i..n-1]a[i]

反復が完了したら、RNG の逆方向を使用して「スワップ解除」することにより、配列を元の順序にリセットします。

アンシャッフル リセットは元の反復よりも長くかかることはないため、漸近コストは変わりません。反復は、反復回数において依然として線形です。

リバーシブル RNG を構築する方法は? 暗号化アルゴリズムを使用するだけです。以前に生成された疑似乱数値を暗号化して前進し、復号化して後退します。対称暗号化アルゴリズムを使用している場合は、前進する各ステップで「ソルト」値を追加して、2 の循環を防ぎ、後退するステップごとにそれを減算できます。RC4 はシンプルで高速で対称的であるため、これについて言及します。私は以前、このようなタスクに使用しました。4バイトの値を暗号化し、modを計算してそれらを目的の範囲に収めると、実際に高速になります。

Iteratorリセットを許可するように拡張することで、これを Java イテレーター パターンに押し込むことができます。下記参照。使用法は次のようになります。

ShuffledList<Integer> lst = new SuffledList<>();

... build the list with the usual operations

ResetableInterator<Integer> i = lst.iterator();
while (i.hasNext()) {
  int val = i.next();

  ... use the randomly selected value

  if (anyConditinoAtAll) break;
}
i.reset();  // Unshuffle the array

これが完璧ではないことはわかっていますが、高速でシャッフルがうまくいきます。そうしないresetと、次の反復子は新しいランダム シャッフルのままになりますが、元の順序は永久に失われることに注意してください。ループ本体で例外が生成される可能性がある場合は、finallyブロックでリセットする必要があります。

class ShuffledList<T> extends ArrayList<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return null;
    }   

    public interface ResetableInterator<T> extends Iterator<T> {
        public void reset();
    }

    class ShufflingIterator<T> implements ResetableInterator<T> {

        int mark = 0;

        @Override
        public boolean hasNext() {
            return true;
        }

        @Override
        public T next() {
            return null;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported.");
        }

        @Override
        public void reset() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
    }
}
于 2013-04-24T02:41:17.993 に答える