2016-02-29から1日間の記事一覧

貯蔵庫サンプリング(Reservoir sampling)

入力(数>n)からn個をランダムに選択する方法。1. 最初のn個をI[0]...I[n-1]にコピーする。t = n - 1。 2. 入力値がなかったら、5へ。 3. ++tとし、[0, t]の一様乱数uを生成する。 u >= nならば、2へ。 4. I[u] = I[t]とし、2へ。 5. Iをソートして終了。 #in…

選択サンプリング法(selection sampling technique)

N個の中からランダムにn個のを選択するためのアルゴリズム 1. t = 0, m = 0とする。 2. [0, 1]の一様乱数uを生成する。 3. もし、 (N - t) * u >= n - m ならば5へ。それ以外ないなら4へ。 4. tを採用し、++t, ++mとする。もしm 5. ++tとし、2へ。 template <typename U></typename>…