6

この質問はこれに関連して おり、より正確にはこの質問に対する回答に関連しています。

ここに行きます：私はunsignedintsのC++ / TR1 unordered_setを持ってUいます（大まかなカーディナリティ100-50000、大まかな値の範囲0から10 ^ 6）。カーディナリティを考えると、ランダムであるが一意ののメンバーをNできるだけ早く反復したいと思います。の一般的な値はありませんが、小さい場合は高速に動作するはずです。NUNN

より詳細には、ここでの「ランダム性」の概念は、2つの呼び出しが多少異なるサブセットを生成する必要があるということです。異なるほど良いですが、これはそれほど重要ではありません。たとえば、ブロックの開始インデックスがランダムである限り、のNメンバーの連続（またはラップアラウンド連続）ブロックに満足します。U同じコストで非連続的である方が良いですが、主な関心事は速度です。U穏やかに変化しますが、呼び出し間で常に変化します（呼び出し間で挿入/消去される要素は約0〜10個）。

私がどこまで来たか：

  1. 簡単なアプローチ：次のよう
    なランダムなインデックスを選択します。イテレータを取得し、を使用して時間を進めてから、サブセットに対して実際のループを開始します。利点：簡単です。短所：++の無駄。i(i+N-1) < |U|itU.begin()iit++

  2. バケットアプローチ（そしてこれは上記のリンクから「新しく」派生しました）：上記のように選択し、 -番目の要素が含まれているバケットを見つけ、local_iterator
    を 取得し、の-番目の要素に到達するまで進みます。それ以降は、時間を増やし続けます。バケットの最後に到達した場合は、次のバケットの最初から続行します。もっとランダムにしたい場合は、完全にランダムに選んでバケツを包み込むことができます。ibilitU.begin(b)litlit++iUlitNliti

私の未解決の質問：

  1. 上記のポイント2の場合、 -番目Uの要素を見つけたら、どういうわけかイテレータを入れることができないのは本当ですか？iこれにより、バケット境界の制御などが不要になります。初心者の私にとって、標準のフォワードイテレータが5番目のアイテムでトラバースを続行する方法を知っている必要があることは認識できないようですが、U自分で5番目のアイテムiを見つけたときは上記のポイント2以外をi通過できないようにする必要があります。U
  2. 他に何ができますか？もっと賢い/もっとランダムなものを知っていますか？可能であれば、バケットサイズやハッシュ関数などの手動制御には関与したくありません。これは少し頭がおかしいからです。
4

1 に答える 1

8

必要な実行時の保証に応じて、1 回のパスで数値のストリームから k 個のランダムな要素を選択する有名な O(n) アルゴリズムがあります。アルゴリズムを理解するために、最初にセットから 1 つの要素だけを選択する場合を見てみましょう。次に、k 要素を選択するために機能するように一般化します。このアプローチの利点は、入力セットのサイズに関する事前の知識を必要とせず、要素の確実に均一なサンプリングを保証することです。これは常に非常に優れています。

セットから 1 つの要素を選びたいとします。これを行うには、セット内のすべての要素をパスし、各ポイントで返す予定の候補要素を維持します。要素のリスト全体を反復処理すると、最終的に均一な確率で単一の要素を選択するまで、ある程度の確率で推測を更新します。各ポイントで、次の不変条件を維持します。

k 個の要素を見た後、最初の k 個の要素のいずれかが候補要素として現在選択されている確率は 1 / k です。

配列全体でこの不変条件を維持すると、n 個の要素をすべて確認した後、それぞれが候補要素になる可能性が 1 / n になります。したがって、候補要素は一様にランダムな確率でサンプリングされています。

アルゴリズムがどのように機能するかを見るために、不変条件を維持するために何をしなければならないかを考えてみましょう。最初の要素を見たとします。上記の不変条件を維持するには、確率 1 でそれを選択する必要があるため、候補要素の初期推定を最初の要素に設定します。

さて、2 番目の要素については、2 つの要素を見たので、各要素が 1/2 の確率で選択されるという不変条件を保持する必要があります。では、確率 1/2 で 2 番目の要素を選択するとします。次に、次のことがわかります。

  • 2 番目の要素を選択した確率は 1/2 です。
  • 最初の要素を選択した確率は、最初にそれを選択した確率 (1) に、2 番目の要素を選択しなかった確率 (1/2) を掛けたものです。これも 1/2 になります。

したがって、この時点ではまだ不変条件が維持されています。3 番目の要素になるとどうなるか見てみましょう。この時点で、各要素が 1/3 の確率で選択されるようにする必要があります。さて、確率 1/3 で最後の要素を選択するとします。それから私たちはそれを知っています

  • 3 番目の要素を選択した確率は 1/3 です。
  • 最初の 2 つの要素のいずれかを選択した確率は、最初の 2 つのステップの後にそれが選択された確率 (1/2) に、3 番目の要素を選択しなかった確率 (2/3) を掛けたものです。これは 1/3 になります。

繰り返しますが、不変式が成り立ちます!

ここでの一般的なパターンは次のようになります: k 個の要素を見た後、各要素は 1/k の確率で選択されます。(k + 1) 番目の要素を見ると、1 / (k + 1) の確率でそれを選択します。これは、1 / (k + 1) の確率で選択され、それより前のすべての要素が、(1 / k) の前に選択して (k + 1) を選択しなかった確率に等しい確率で選択されることを意味します。 )今回は (k / (k + 1)) 番目の要素であり、これらの要素が選択される確率はそれぞれ 1 / (k + 1) になります。これにより、各ステップで不変条件が維持されるため、優れたアルゴリズムが得られます。

  1. 最初の要素が表示されたら候補として選択します。
  2. 連続する要素ごとに、候補要素をその要素に確率 1 / k で置き換えます。ここで、k はこれまでに検出された要素の数です。

これは O(n) 時間で実行され、O(1) スペースが必要で、データ ストリームから一様にランダムな要素を返します。

では、セットから 1 つだけでなくk 個の要素を選択したい場合に、これを機能するようにスケールアップする方法を見てみましょう。この考え方は、前のアルゴリズムと非常によく似ています (実際には、より一般的なアルゴリズムの特殊なケースになります)。1 つの候補を維持する代わりに、k 個の異なる候補を維持し、1、2、...、k の番号を付けた配列に格納します。各ポイントで、この不変条件を維持します。

m > k 個の要素を見た後、最初の m 個の要素のいずれかが選択される確率は k / m です。

配列全体をスキャンすると、完了時に各要素が選択される確率が k / n になることを意味します。k 個の異なる要素を選択しているため、配列から要素を一様にランダムにサンプリングすることを意味します。

アルゴリズムは以前と同様です。最初に、セットから最初の k 個の要素を確率 1 で選択します。これは、k 個の要素を見たときに、それらのいずれかが選択された確率が 1 = k / k であり、不変式が成り立つことを意味します。ここで、帰納的に m 回の反復後に不変式が成り立つと仮定し、(m + 1) 回目の反復を考えます。1 から (m + 1) までの乱数を選択します。1 から k (両端を含む) の間の数を選択した場合、その候補要素を次の要素に置き換えます。それ以外の場合は、次の要素を選択しないでください。これは、必要に応じて確率 k / (m + 1) で次の要素を選択することを意味します。最初の m 個の要素のいずれかが選択される確率は、その要素を含むスロットが選択されなかった確率 (m / (m + 1)) の (k / m) 倍の前に選択された確率です。これにより、必要に応じて k / (m + 1) が選択される合計確率が得られます。帰納法により、これは、アルゴリズムがセットから k 個の要素を完全に均一かつランダムにサンプリングすることを証明します!

さらに、実行時間は O(n) であり、これはセットのサイズに比例し、選択する要素の数とは完全に無関係です。また、O(k) メモリのみを使用し、格納される要素の型について何の仮定も行いません。

あなたはこれを C++ でやろうとしているので、恥知らずな自己宣伝として、このアルゴリズムの実装 (STL アルゴリズムとして書かれたもの)を私の個人的な Web サイトで入手できます。お気軽にご利用ください！

お役に立てれば！

于 2010-12-18T20:52:30.067 に答える