アルゴリズム・データ構造図鑑 · 基礎から応用へ

長さ不明の列から標本を残す

保持数を固定して各入力位置を等しく扱う更新規則を導き、固定seedの再現・分布の観察・再開時の状態を分けます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 長さ不明の列からk件を残す
  2. 一つの整数乱数で二つの判断をする
  3. 古い要素の採用確率を帰納的に考える
  4. 再現性と分布の観察を分ける
  5. 保持量と入力を読む費用
  6. 再開と並列化で確率を壊さない
  7. 同値の入力と位置の標本を区別する
  8. 生存確率を掛ける課題
  9. この記事をロゲイアに質問する理解を確かめる

長さ不明の列からk件を残す

ログが一件ずつ届き、最終的な総数を先に取得できないとします。全件を保存せず、最終的にk件の一様な標本を残したい場合にリザーバサンプリングを使えます。最初のk件を保存し、以後のi件目ではk/iの確率で新しい要素を採用し、保存中の一つと置き換えます。ここでiは1始まりの処理件数です。掲載コードのenumerateは0始まりなので、乱数の範囲にi+1を使います。

抽出するのは値の種類ではなく、入力の位置です。同じ文字列がログへ二回現れれば、別の二件として扱います。重複しない値だけを抽出する課題なら、同じ算法をそのまま適用できません。また、時刻に近いログを優遇する重み付きの抽出でもありません。全ての位置に等しい採用確率を与えるという目標を先に固定します。

一つの整数乱数で二つの判断をする

保持数k=3で、五件目が届いた場面を考えます。0〜4の整数を一様に一つ選び、0、1、2なら対応する保存位置を置き換え、3か4なら何も変えません。採用確率は3/5で、採用された場合は三つの位置へ同じ確率で入ります。採用と置換位置を別々の乱数で決める実装もできますが、この一つの乱数で両方を表せます。

k=0なら保存位置がないため、全ての入力を読み終えて空の結果を返します。入力件数がkより少なければ、届いた全件を残します。存在しない件を埋めるためにNoneを標本へ足しません。今回の実装は負のkを拒否します。標本が必ずk件になる契約が必要なら、入力が短かった場合をエラーとするなど、呼出し側との規則を追加してください。

5件目の乱数操作確率
0、1、2対応する保存位置を置換各1/5、合計3/5
3、4標本を変更しない合計2/5

古い要素の採用確率を帰納的に考える

i−1件を処理した時点で、古い各要素が保存される確率がk/(i−1)だと仮定します。次の一件で特定の保存位置が置き換わる確率は1/iなので、その古い要素が残る確率は1−1/iです。掛け合わせるとk/(i−1)×(i−1)/i=k/iになります。新しいi件目も確率k/iで入るため、どの位置も同じ所属確率になります。

この計算は、乱数が必要な範囲で一様であることと、置換規則が対応していることを使います。採用だけk/iにして、いつも先頭の保存位置を上書きする案では、古い位置の扱いが偏ります。個々の所属確率の説明に加え、標本全体を一様な部分集合とする性質は同じ更新規則を用いた帰納で考えられます。実測で回数が似たことだけを、分布の証明と取り違えないようにします。

再現性と分布の観察を分ける

付属コードは、同じ入力とseedで結果が一致すること、短い入力とk=0の扱い、標本の件数と重複しない入力位置をassertします。その後、N=20、k=4でseedを0〜1,999へ変え、各位置が入った回数を全て出します。総採用回数は8,000で、一位置あたりの期待回数は400です。出力がちょうど400ずつになることは要求しません。

標本は試行ごとに揺れるので、観測回数の差があることだけで実装の誤りとは判断できません。一方で、全てが同じ保存位置へ偏るなどの誤りを見つける観察にはなります。seedを選び直して見栄えのよい一回だけを報告せず、条件と全回数を残します。乱数生成器の版や実装を変える場合、同じseedが常に同じ列を作るかという互換性も確認してください。

python
import random
from collections import Counter
def reservoir(stream,k,rng):
    if k<0:raise ValueError('negative sample size')
    result=[]
    for i,item in enumerate(stream):
        if i<k:result.append(item)
        else:
            slot=rng.randrange(i+1)
            if slot<k:result[slot]=item
    return result
assert reservoir(iter([1,2]),5,random.Random(7))==[1,2]
assert reservoir(range(10),0,random.Random(7))==[]
assert reservoir(range(20),4,random.Random(7))==reservoir(iter(range(20)),4,random.Random(7))
counts=Counter()
for seed in range(2000):
    sample=reservoir(range(20),4,random.Random(seed));assert len(sample)==len(set(sample))==4
    counts.update(sample)
assert sum(counts.values())==8000
print('seeds=0..1999 N=20 k=4 inclusion_counts=',[counts[i] for i in range(20)])
print('expected inclusion count=400; observations do not prove uniformity')

保持量と入力を読む費用

標本として保存する要素は高々k件なので、追加領域はO(k)です。一方、最後の一件まで全てを読むこの方式の時間はO(N)です。標本が小さいから入力の読取りもk件だけになるわけではありません。重いログ本文をコピーせず参照だけ保存する場合でも、元の領域が参照によって生き続ける費用を考えます。k件の参照と、保持される実データの量は同じ尺度ではありません。

最初から総数が分かり、ランダム位置へ安くアクセスできる入力なら、別の抽出方法が適する場合があります。逆に順次ストリームでは、何件飛ばすかを工夫するアルゴリズムもありますが、ここでは一件ずつの判断を理解する基本形を扱います。外部からの無限ストリームへは終了条件を別に設けます。任意の時点で取り出す標本は、その時点までの全履歴からの標本で、最近の窓だけからの標本ではありません。

再開と並列化で確率を壊さない

途中で処理を止めて後から続ける場合、標本だけでなく、これまで読んだ件数と乱数生成器の状態も必要です。件数をkへ戻して再開すると、次の要素の採用確率が実際の履歴より大きくなり、後半の入力を優遇してしまいます。再現したい実行では入力の順序と同一性も保ちます。同じログを二度流したなら、二つの位置として扱われることにも注意します。

複数のワーカーがそれぞれ同じk件を持ち、その標本を単に連結してk件へ減らすだけでは、元の入力件数が違うワーカーを適切に重み付けできない場合があります。全件の母集団と各区分のサイズを含む統合規則が必要です。今回の単一ストリームの実装を、並列ストリーム全体の一様標本として無条件に使わないでください。保存の境界と、どの母集団から選んでいるかを一緒に説明します。

入力の同じ値が複数回現れた場合も、それぞれの出現位置を別の候補として扱います。値ごとの重複排除をするなら、母集団そのものが変わります。

同値の入力と位置の標本を区別する

入力がA、A、B、Bなら、k=1で保持する値がAかBである確率はそれぞれ1/2になります。位置は四つとも1/4ですが、同じ値の二位置を合わせるからです。A、A、A、Bへ変えれば、値Aの確率は3/4です。異なる値AとBを等確率にする標本とは違います。

ログの内容をsetへ変換してから処理すると、重複位置を消し母集団を変えます。これはメモリを節約した同じ抽出ではありません。記録一件を単位にするか、利用者一人を単位にするかなど、標本の単位を先に固定します。分布の検査で位置のカウントを出す理由も、値の頻度と算法の偏りを混ぜないためです。

生存確率を掛ける課題

課題はk=2で四件を処理した後、最初の要素が残る確率を求めることです。最初の二件には必ず含まれ、三件目で置き換えられない確率は2/3、四件目では3/4です。積は1/2で、k/N=2/4と一致します。四件目の新要素も採用確率2/4なので同じです。途中の生存と最終的な所属を分け、条件付きの計算を省略しないでください。

追加課題は、20件の入力から4件を残す途中で、10件読んだ後に件数を0へ戻して処理を再開する案です。解答は、後半を新しい先頭として優遇し、全20位置の一様性を壊すおそれがある、です。標本と処理件数が同じ履歴へ対応していなければ、採用率の分母が誤ります。数学的な規則、コードの添字、保存して再開する状態を対応させて説明してください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ