リザーバーサンプリング

🔥 Vibe プロンプト

「1000万ログエントリから100人のランダムユーザーをO(n)時間、O(k)メモリでサンプリング。」

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

def log_stream():
    for i in range(10000000):
        yield f"user_{i}"

import time
start = time.time()
sample = reservoir_sample(log_stream(), 100)
print(f"時間: {time.time()-start:.2f}s")
print(f"メモリ: O(100)アイテム")
print(f"サンプル: {sample[:5]}...")

応用

• リアルタイムWeb分析サンプリング
• A/Bテスト割り当て
• ネットワークパケットサンプリング
• MLトレーニングデータ選択

重要なポイント

• コアコンセプトをしっかり理解する
• ハンズオンコード例で実践する
• 実世界の問題に応用する
• 演習で知識を強化する

さらに学ぶ

• 公式ドキュメント
• GitHubのオープンソースプロジェクト
• コミュニティフォーラムとディスカッション
• 関連コースとチュートリアル