クラウド Mac で検証する iOS のリザーバサンプリング

Windows でログのフィルタリング機能を書いたあと、件数が事前に分からないイベントストリームから、少数のレコードをランダムに残す必要が生じました。全件を配列に読み込んでからシャッフルすると、入力が増えるほどメモリ使用量も増えてしまいます。クラウド Mac なら、まず Swift でリザーバサンプリングの動作を検証し、その実装をそのまま iOS プロジェクトに組み込めます。重要なのは、結果が「ランダムらしく見えるか」を眺めることではなく、選択規則を繰り返し検証できる契約にすることです。

抽出単位と容量の契約を明確にする

ここでは Algorithm R を使います。最初の k 件を保持し、t 件目を読み込んだ時点で、0 から t−1 までの整数 j を一様に選びます。j が k 未満の場合にだけ、対応するスロットを置き換えます。走査が終わると、入力の各位置が選ばれる確率は k/n となり、追加の記憶領域は O(k)、走査時間は O(n) です。

この結論が成り立つには、それまでの履歴を条件としても、各回の抽選が一様である必要があります。乱数が正しい範囲に収まっているだけでは、公平性は保証できません。

まず、境界条件を四つ定めます。容量は負にできないこと、容量がゼロなら入力を消費せず空のサンプルを返すこと、入力件数が容量未満ならすべて保持すること、同じ値でも位置が異なれば別の抽出対象として扱うことです。出力のスロット順はランダムな並べ替えではなく、入力順の維持も保証しません。

公平な抽出でも、毎回異なる結果になるとは限りません。「連続する二回の結果は同じであってはならない」とテストに書くと、正常なランダム出力が断続的なテスト失敗の原因になります。

乱数源を選択ロジックから分離する

OSXMesh のクラウド Mac にログインしたら、ターミナルで xcrun swift --version を実行し、現在のツールチェーンで Swift を実行できることを確認します。以下のコードを ReservoirCheck.swift として保存してください。クロージャには、その値自体を含まない上限を渡すため、本番の乱数源とテスト用スクリプトで同じ選択ロジックを使えます。

func reservoir<S: Sequence>(
    _ input: S,
    capacity: Int,
    draw: (Int) -> Int
) -> [S.Element] {
    precondition(capacity >= 0)
    guard capacity > 0 else { return [] }

    var sample: [S.Element] = []
    var seen = 0

    for value in input {
        seen += 1
        if sample.count < capacity {
            sample.append(value)
        } else {
            let slot = draw(seen)
            precondition(slot >= 0 && slot < seen)
            if slot < capacity {
                sample[slot] = value
            }
        }
    }
    return sample
}

let empty = reservoir([Int](), capacity: 2) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(empty.isEmpty)

let zero = reservoir([1, 2], capacity: 0) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(zero.isEmpty)

let short = reservoir([1, 2], capacity: 3) { _ in
    preconditionFailure("Unexpected draw")
}
precondition(short == [1, 2])

var counts: [String: Int] = [:]

for first in 0..<3 {
    for second in 0..<4 {
        var script = [first, second].makeIterator()
        var bounds: [Int] = []

        let sample = reservoir(0..<4, capacity: 2) { upper in
            bounds.append(upper)
            guard let next = script.next() else {
                preconditionFailure("Draw script exhausted")
            }
            return next
        }

        precondition(bounds == [3, 4])
        precondition(script.next() == nil)
        precondition(sample.count == 2)
        precondition(Set(sample).count == 2)

        let key = sample.sorted().map { String($0) }
            .joined(separator: ",")
        counts[key, default: 0] += 1
    }
}

let expected = ["0,1", "0,2", "0,3", "1,2", "1,3", "2,3"]
precondition(Set(counts.keys) == Set(expected))
precondition(counts.values.allSatisfy { $0 == 2 })

xcrun swift ReservoirCheck.swift を実行します。成功時は何も出力せず、失敗時はゼロ以外の終了ステータスで終了します。このスクリプトは事前条件による検査を使っているため、安全性チェックを無効にする最適化オプションでは実行しないでください。実際のアプリケーションで外部から容量を受け取る場合は、不正な入力でプロセスを終了させるのではなく、事前に値を検証してからアルゴリズムを呼び出します。

十二通りの経路を全列挙して選択規則を検証する

四つの候補位置から二つを選ぶ場合、三件目では三通り、四件目では四通りの選択があるため、経路は全部で十二通りです。先ほどの乱数源の仮定のもとでは、各経路の確率はいずれも十二分の一となり、順序を区別しない六つの位置の組み合わせは、それぞれ二回ずつ現れるはずです。

ここで検査するのは、各位置の出現回数だけではなく、組み合わせの分布です。誤った実装でも、各位置の周辺頻度はほぼ均等なのに、一部の組み合わせがまったく現れないことがあります。

スクリプトでは、乱数源に渡された上限が三と四であることに加え、用意した抽選列がちょうど使い切られたことも確認しています。呼び出しが一回少ない場合も、一回多い場合も、上限を誤って現在のスロット数にした場合も失敗します。ソートは比較用のキーを作るためだけに使い、本番関数の戻り値の契約をひそかに変えてはいけません。

この規模の検査でも、置き換え条件に関する典型的な誤りは検出できます。ただし、任意の入力規模に対する数学的証明ではありません。マージ前には帰納法の成立条件も確認し、ほかの小さな容量についても全列挙のテストケースを追加する必要があります。

重複値とストリーミング入力の落とし穴を押さえる

重複値のテストには、一意の連番を付けたレコードを使います。たとえば内容が同じ二つのイベントにも、それぞれ位置ゼロと位置一を付け、選ばれた位置が重複しないことを検証します。サンプル内の業務上の値が一意である、と単純に検証してはいけません。先に重複を除いてから抽出すると、イベントの種類ごとの重みが変わり、追加の記憶領域も必要になります。

容量が一の場合は、必ず置き換えるケースと必ず見送るケースをそれぞれ作ります。容量が入力件数と等しい場合、乱数源は呼び出されてはいけません。容量が入力件数より大きい場合、出力件数は入力件数と一致する必要があります。

一度しか消費できないシーケンスには、読み取り回数を数えるイテレータも用意します。容量がゼロなら読み取り回数もゼロでなければならず、容量が正なら走査は一回だけです。長さを先に知るために Array(input) を呼び出してはいけません。抽出結果が正しくても、ストリーミング処理でメモリ使用量を抑えるという目標は達成できなくなります。

また、このカウンタを使うには、入力件数が Int で表現できる必要があります。終わりのないイベントストリームでは、ウィンドウを区切って抽出を完了させるべきであり、この同期関数が自動的に戻ることは期待できません。キャンセルとウィンドウの終了は上位層で制御します。

プロジェクトへの組み込み時に再現可能な証拠を残す

本番では、Int.random(in: 0..<upper) で整数を生成できます。乱数の剰余を取って範囲に収めたり、固定のテスト用抽選列を本番機能に持ち込んだりしてはいけません。ここでの抽出は一般的なデータ処理向けであり、セキュリティ上の保証が必要な抽選にそのまま使うべきではありません。

スクリプトをリポジトリにコミットし、クラウド Mac のビルド手順では、プロジェクトのテストより先に実行します。失敗時には、少なくとも入力の位置、容量、抽選列、ツールチェーンのバージョンを保存してください。調査のためであっても、実際のユーザーイベントの本文は記録しないでください。

最後に、検証を三層に分けます。決定的な境界テスト、小規模な経路の全列挙、そして独立した統計的観察です。統計的観察は乱数源の接続ミスを見つけるのに適していますが、頻度の許容範囲を狭くしすぎて、コミットのたびに通過を妨げる用途には向きません。回帰テストの根拠にすべきなのは、ある抽出結果がたまたま直感に反したことではなく、明確に再現できる失敗経路です。

よくある質問