リザーバサンプリング（貯水池抽出法）とは？C++実装例で学ぶランダム抽出アルゴリズム

リザーバサンプリング（Reservoir Sampling：貯水池抽出法）は、ランダム化アルゴリズムの一種です。このアルゴリズムでは、n個の異なる要素からなるリストの中から、k個の要素を無作為に選び出します。

基本的なアイデア

まず思いつく単純な方法としては、サイズkの配列を「リザーバ（貯水池）」として用意し、元のリストから要素をランダムに1つ取り出してはリザーバへ格納していくやり方が挙げられます。ただし、一度選んだ要素が重複しないよう管理する必要があるため、この手法は効率が悪く、計算量が増大してしまうという欠点があります。

そこで有効なのが次の手法です。まずリストの先頭k個の要素をリザーバにコピーします。続いて、(k+1)番目以降の要素を順番に処理していきます。現在注目している要素のインデックスをiとするとき、0〜iの範囲から乱数でインデックスjを1つ選びます。もしjが0〜k-1の範囲内であれば、リザーバのj番目の要素reservoir[j]を、リストのi番目の要素list[i]と入れ替えます。

入力と出力の例

Input:
整数リスト: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, k = 6
Output:
配列から選ばれたk個の要素: 8 2 7 9 12 6

アルゴリズム

chooseKItems(array, n, k)

入力: 配列、配列の要素数n、選択する要素数k。

出力: 配列からランダムに選ばれたk個の要素。

Begin
    サイズkの出力配列を定義する
    配列の先頭k個の要素を出力配列へコピーする

    i < n の間、以下を繰り返す
        j := 0〜i の範囲からランダムに値を1つ選ぶ
        もし j < k ならば
            output[j] := array[i]
        i を 1 増やす
    繰り返し終了
    出力配列を表示する
End

C++による実装例

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void display(int array[], int n) {
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

void chooseKItems(int array[], int n, int k) {  //配列からk個の要素を選択する
    int i;
    int output[k];
    for (i = 0; i < k; i++)
        output[i] = array[i];

    srand(time(NULL));    //time関数を使い毎回異なるシード値を得る

    while(i < n) {
        int j = rand() % (i+1);    //0〜iの範囲のランダムなインデックス

        if (j < k)    //出力配列のj番目にi番目の要素を格納
            output[j] = array[i];
        i++;
    }

    cout << "K-Selected items in the given array: ";
    display(output, k);
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int n = 12;
    int k = 6;
    chooseKItems(array, n, k);
}

実行結果

K-Selected items in the given array: 8 2 7 9 12 6

このアルゴリズムはO(n)の時間計算量で動作します。さらに、データ全体の件数が事前に分からないストリームデータに対しても、各要素が等確率で選ばれるサンプルを1パスで取得できる点が大きな特徴です。