15

サーバーを流れる一連のイベントがあります。すべてを保存することは現実的ではありませんが、定期的にそれらの一部をまとめて処理できるようにしたいと考えています。だから、私が見たすべてのもののランダムサンプリングであるが、最大サイズに制限されているストリームのサブセットを保持したい.

そのため、新しいアイテムごとに、保存されたセットに追加するか、破棄するかを決定するアルゴリズムが必要です。追加した場合、すでに限界に達しているため、古いアイテムの 1 つを削除するアルゴリズムが必要です。

明らかに、制限を下回っている限り、これは簡単です (すべてを保存するだけです)。しかし、その制限を超えたら、古いアイテムや新しいアイテムに偏ることなく、適切なランダム サンプリングを維持するにはどうすればよいでしょうか?

ありがとう、

4

6 に答える 6

6

これはよくある面接の質問です。

これを行う簡単な方法の 1 つは、確率 k/n (または 1 のいずれか小さい方) で n 番目の要素を保存することです。新しいサンプルを保存するために要素を削除する必要がある場合は、ランダムな要素を削除します。

これにより、n 要素の均一にランダムなサブセットが得られます。n がわからない場合は、それを推定して、ほぼ均一なサブセットを取得できます。

于 2010-12-02T22:27:19.537 に答える
1

この論文はまさにあなたが探しているものではありませんが、検索の良い出発点になるかもしれません。

于 2010-12-02T22:04:19.557 に答える
1

サンプルを先入れ先出し (FIFO) キューに保存します。

サンプル間の非常に多くのイベントのサンプリング レートを設定するか、イベントのパターンに応じて、これを少しランダム化します。

n 番目のイベントごとに保存するか、レートが指示するたびに保存してから、キューの最後に貼り付けます。

サイズが大きすぎる場合は、上から 1 つポップします。

于 2010-12-02T22:04:33.800 に答える
1

これは、受信するイベントの総数がわからず、サブセット内の要素の最小数を必要としないことを前提としています。

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1.
counter = 1 //Initialize a counter.

while(receiving event){
  random = //Generate a random number between 1 and counter
  if( counter == random ){
     if( counter <= MAX_SIZE ){
        arr[counter] = event
     }
     else{
        tmpRandom = //Generate a random number between 1 and MAX_SIZE
        arr[tmpRandom] = event
     }
  }
  counter =+ 1

}
于 2010-12-02T22:13:57.210 に答える
0

各イベントを記録する確率を割り当て、インデックス可能なデータ構造にイベントを保存します。構造体のサイズがしきい値に達したら、ランダムな要素を削除して新しい要素を追加します。Rubyでは、これを行うことができます：

@storage = []
prob = 0.002

while ( message = getnextMessage) do
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN
    @storage << message if (rand() < prob) 
end

これにより、最大サイズと、イベントが発生した時期に対する偏りがないことに対処できます。保存された要素をバケットに分割し、複数の要素を持つバケットから要素を削除することで、削除する要素を選択することもできます。たとえば、バケット メソッドを使用すると、1 時間ごとに 1 つを保持できます。

また、サンプリング理論がビッグ マスであることも知っておく必要があります。これについて素人の考え以上のものが必要な場合は、お住まいの地域の有資格の数学者に相談してください。

于 2010-12-02T22:13:22.393 に答える