Namaran

Code daily. Without assist.

2026-10-13

reservoir.cpp

#include <iostream>
#include <random>
#include <sstream>

int main() {
    std::mt19937 gen(1);
    std::uniform_int_distribution<int> slot(0, 1);
    int hits = 0;
    for (int run = 0; run < 1000; ++run) {
        std::istringstream in("0 1 2 3 4");
        int keep[2] = {};
        for (int x, n = 0; in >> x; ++n) {
            if (n < 2)
                keep[n] = x;
            else
                keep[slot(gen)] = x;
        }
        hits += keep[0] == 4 || keep[1] == 4;
    }
    std::cout << hits << '\n';
}

この main は、何個来るか分からない入力から2個を一様に選ぶ処理を、"0 1 2 3 4" に対して1000回くり返し、4 が選ばれた回数を数えます。どの値も5分の2の確率で残るはずなので、本来は 400 前後が表示されるはずですが、いまは 1000 が表示されます。乱数の種を変えても 1000 のままです。

Answer

Wrong

else
    keep[slot(gen)] = x;

slot は0か1を返すので、3個目からの値は必ずどちらかの枠を上書きします。最後に読む 4 も必ず枠に入り、そのあとに追い出す値は来ないので、1000回すべてで残ります。値が枠に入る確率を、読んだ個数が増えるにつれて下げていく仕組みがどこにもありません。

Right

else if (int j = std::uniform_int_distribution<int>(0, n)(gen); j < 2)
    keep[j] = x;

n 番目(0から数える)の値では、0以上 n 以下から j を引き、j が2未満のときだけその枠を置き換えます。値が枠に入る確率は 2 / (n + 1) になり、最後の 4 が入るのは5回に2回です。前から来た値も同じ割合で追い出されずに残るので、5個のどれもが5分の2の確率で選ばれます1。範囲が値ごとに変わるので、分布はループの中で作ります。使わなくなった slot の宣言は消します。

  1. この手順は Algorithm R と呼ばれ、Knuth の『The Art of Computer Programming』第2巻で扱われています。