algorithm - リザーバーサンプリング

Question

サイズが未定の配列からk 個の乱数を取得するには、リザーバー サンプリングと呼ばれる手法を使用します。サンプルコードでそれがどのように起こるかを簡単に強調できますか?

Answer 1

私は実際にこれに名前があることに気づいていなかったので、これを最初から証明して実装しました:

import random
def random_subset( iterator, K ):
    result = []
    N = 0

    for item in iterator:
        N += 1
        if len( result ) < K:
            result.append( item )
        else:
            s = int(random.random() * N)
            if s < K:
                result[ s ] = item

    return result

出典: http://web.archive.org/web/20141026071430/http://propersubset.com:80/2010/04/choosing-random-elements.html

終わり近くに証拠があります。

Answer 2

ジャワ

import java.util.Random;

public static void reservoir(String filename,String[] list)
{
    File f = new File(filename);
    BufferedReader b = new BufferedReader(new FileReader(f));

    String l;
    int c = 0, r;
    Random g = new Random();

    while((l = b.readLine()) != null)
    {
      if (c < list.length)
          r = c++;
      else
          r = g.nextInt(++c);

      if (r < list.length)
          list[r] = l;

      b.close();}
}