"""
フィボナッチ数列: 素朴な再帰 vs メモ化 の比較
- 素朴版: 時間 O(2^n), 空間 O(n)（コールスタック）
- メモ化版: 時間 O(n), 空間 O(n)（キャッシュ + コールスタック）
"""
 
import time
import sys
 
 
def fib_naive(n: int) -> int:
    """素朴な再帰によるフィボナッチ数列。
 
    なぜ O(2^n) なのか:
    fib(n) は fib(n-1) と fib(n-2) を呼ぶ。
    この再帰木の高さは n であり、各レベルで分岐が最大2つ。
    よって呼び出し回数は最悪 2^n に近い。
    実際には fib(n) の呼び出し回数は fib(n+1) - 1 回であり、
    これは黄金比 φ = (1+√5)/2 ≈ 1.618 を用いて φ^n に比例する。
    """
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
 
def fib_memo(n: int, memo: dict = None) -> int:
    """メモ化によるフィボナッチ数列。
 
    なぜ O(n) なのか:
    各 fib(k) (k=0..n) は最大1回だけ「実際に計算」される。
    2回目以降は memo から O(1) で取得する。
    よって計算回数は n+1 回、各回 O(1) なので全体 O(n)。
 
    注意: デフォルト引数に mutable オブジェクトを使うと
    関数呼び出し間で共有される。ここでは意図的に None を
    デフォルトにし、初回呼び出しで辞書を生成している。
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
 
 
def fib_bottom_up(n: int) -> int:
    """ボトムアップ DP によるフィボナッチ数列。
 
    なぜこの方法が存在するのか:
    メモ化（トップダウン）は再帰呼び出しを使うため、
    Python のデフォルト再帰上限（通常 1000）に引っかかる。
    ボトムアップはループで計算するため再帰上限の制約がない。
 
    時間 O(n), 空間 O(1)（直前の2値のみ保持）
    """
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
 
 
def benchmark_fibonacci():
    """3手法の性能を比較する。"""
    print("=" * 60)
    print("フィボナッチ数列: 手法別ベンチマーク")
    print("=" * 60)
 
    # 素朴版は n=35 程度が限界（それ以上は待ち時間が長すぎる）
    for n in [10, 20, 30, 35]:
        start = time.perf_counter()
        result = fib_naive(n)
        elapsed = time.perf_counter() - start
        print(f"素朴版     fib({n:2d}) = {result:>15,d}  "
              f"時間: {elapsed:.6f}秒")
 
    print("-" * 60)
 
    # メモ化版とボトムアップ版は大きな n でも高速
    sys.setrecursionlimit(10000)
    for n in [10, 100, 1000, 5000]:
        memo = {}
        start = time.perf_counter()
        result_memo = fib_memo(n, memo)
        elapsed_memo = time.perf_counter() - start
 
        start = time.perf_counter()
        result_bu = fib_bottom_up(n)
        elapsed_bu = time.perf_counter() - start
 
        assert result_memo == result_bu, "結果が一致しません"
        digits = len(str(result_memo))
        print(f"メモ化版   fib({n:4d}): {digits:>5d}桁  "
              f"時間: {elapsed_memo:.6f}秒  "
              f"キャッシュサイズ: {len(memo)}")
        print(f"ボトムアップ fib({n:4d}): {digits:>5d}桁  "
              f"時間: {elapsed_bu:.6f}秒  "
              f"追加空間: O(1)")
 
 
if __name__ == "__main__":
    benchmark_fibonacci()

"""
functools.lru_cache の活用パターンと注意点
 
lru_cache が内部で行っていること:
1. 引数をタプルに変換してハッシュキーを生成
2. キーがキャッシュに存在すれば、そのエントリを「最近使用」に移動して返す
3. 存在しなければ関数を実行し、結果をキャッシュに追加
4. maxsize を超えたら「最も古い」エントリを削除
 
なぜ maxsize=None と maxsize=128 を使い分けるのか:
- maxsize=None: 無制限キャッシュ。全結果を保存。メモリ使用量が増え続ける。
  → 部分問題数が有限で予測可能な場合（DP など）に適する
- maxsize=128（デフォルト）: 最大128エントリ。LRU で古いものを追い出す。
  → 入力の種類が膨大だがアクセスに局所性がある場合に適する
"""
 
from functools import lru_cache
import time
 
 
@lru_cache(maxsize=None)
def fib_cached(n: int) -> int:
    """メモ化フィボナッチ — lru_cache 版
 
    なぜ maxsize=None なのか:
    fib(n) の部分問題数は n+1 個で有限。
    全てキャッシュしても空間 O(n) で収まる。
    LRU の追い出しが発生すると再計算が必要になり非効率。
    """
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)
 
 
@lru_cache(maxsize=256)
def expensive_api_simulation(user_id: int, query: str) -> dict:
    """高コスト処理のキャッシュ例
 
    なぜ maxsize=256 なのか:
    ユーザーID × クエリの組み合わせは膨大になりうる。
    全てキャッシュするとメモリが枯渇する。
    アクセスパターンには時間的局所性があるため、
    最近のエントリのみ保持すれば十分なヒット率が得られる。
    """
    # 重い処理をシミュレート
    time.sleep(0.001)
    return {"user_id": user_id, "query": query, "result": "data"}
 
 
def demonstrate_cache_info():
    """lru_cache の統計情報を確認する。"""
    # キャッシュをクリア
    fib_cached.cache_clear()
 
    # 計算実行
    result = fib_cached(100)
    info = fib_cached.cache_info()
 
    print(f"fib(100) = {result}")
    print(f"キャッシュ情報:")
    print(f"  ヒット数:   {info.hits}")
    print(f"  ミス数:     {info.misses}")
    print(f"  最大サイズ: {info.maxsize}")
    print(f"  現在サイズ: {info.currsize}")
    print(f"  ヒット率:   {info.hits / (info.hits + info.misses) * 100:.1f}%")
 
 
if __name__ == "__main__":
    demonstrate_cache_info()

"""
主要なキャッシュ追い出しポリシーの実装と比較
 
なぜ複数のポリシーが存在するのか:
アクセスパターンによって最適なポリシーが異なるためである。
- LRU: 時間的局所性（最近アクセスしたものを再びアクセスしやすい）に強い
- LFU: 頻度的局所性（よく使うものは今後も使いやすい）に強い
- FIFO: 実装が最も単純。局所性を仮定しない場合の基本選択
"""
 
from collections import OrderedDict, defaultdict
import time
 
 
class LRUCache:
    """Least Recently Used キャッシュ
 
    なぜ OrderedDict を使うのか:
    LRU は「最も最近使われていないエントリ」を追い出す。
    これには各エントリの「最終アクセス時刻」の管理が必要。
    OrderedDict は挿入順序を保持し、move_to_end() で
    O(1) でエントリを末尾に移動できるため、LRU に最適。
 
    時間計算量: get/put ともに O(1) 平均
    空間計算量: O(capacity)
    """
 
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
        self.hits = 0
        self.misses = 0
 
    def get(self, key):
        if key in self.cache:
            self.hits += 1
            self.cache.move_to_end(key)
            return self.cache[key]
        self.misses += 1
        return None
 
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 先頭（最古）を削除
 
    def hit_rate(self) -> float:
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0.0
 
 
class LFUCache:
    """Least Frequently Used キャッシュ
 
    なぜ LRU ではなく LFU を選ぶ場合があるのか:
    アクセスパターンに「人気アイテム」が存在する場合、
    LFU は高頻度アイテムを保持し続けるため効率が良い。
    例: CDN でのコンテンツキャッシュ（人気動画は常にキャッシュ）
 
    LFU の弱点:
    - 過去に人気だったが今は不要なアイテムが残り続ける
    - 新しいアイテムがキャッシュに定着しにくい（頻度が低いため）
    """
 
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}            # key -> value
        self.freq = defaultdict(int)  # key -> 使用頻度
        self.hits = 0
        self.misses = 0
 
    def get(self, key):
        if key in self.cache:
            self.hits += 1
            self.freq[key] += 1
            return self.cache[key]
        self.misses += 1
        return None
 
    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.cache:
            self.cache[key] = value
            self.freq[key] += 1
            return
        if len(self.cache) >= self.capacity:
            # 最低頻度のキーを見つけて削除
            min_freq_key = min(self.freq, key=lambda k: self.freq[k])
            del self.cache[min_freq_key]
            del self.freq[min_freq_key]
        self.cache[key] = value
        self.freq[key] = 1
 
    def hit_rate(self) -> float:
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0.0
 
 
class TTLCache:
    """Time-To-Live キャッシュ
 
    なぜ TTL が必要なのか:
    外部データ（API レスポンス、DB クエリ結果）は時間とともに
    変化する可能性がある。TTL を設定することで、古くなった
    キャッシュエントリを自動的に無効化し、データの鮮度を保証する。
 
    LRU/LFU との違い:
    - LRU/LFU: 容量制約に基づく追い出し
    - TTL: 時間制約に基づく無効化
    - 実務では LRU + TTL を組み合わせることが多い
    """
 
    def __init__(self, capacity: int, ttl_seconds: float):
        self.capacity = capacity
        self.ttl = ttl_seconds
        self.cache = OrderedDict()  # key -> (value, timestamp)
        self.hits = 0
        self.misses = 0
 
    def _is_expired(self, key) -> bool:
        if key not in self.cache:
            return True
        _, timestamp = self.cache[key]
        return (time.time() - timestamp) > self.ttl
 
    def get(self, key):
        if key in self.cache and not self._is_expired(key):
            self.hits += 1
            value, _ = self.cache[key]
            # タイムスタンプを更新
            self.cache[key] = (value, time.time())
            self.cache.move_to_end(key)
            return value
        # 期限切れエントリがあれば削除
        if key in self.cache:
            del self.cache[key]
        self.misses += 1
        return None
 
    def put(self, key, value):
        self.cache[key] = (value, time.time())
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
 
 
def compare_cache_policies():
    """異なるキャッシュポリシーの比較デモ。
 
    シナリオ: キャッシュ容量5、アクセスパターンに偏りあり
    """
    import random
    random.seed(42)
 
    # Zipf 分布的なアクセスパターン: 少数のキーに集中
    # キー 0-2 が高頻度、キー 3-19 が低頻度
    access_pattern = []
    for _ in range(1000):
        if random.random() < 0.7:
            access_pattern.append(random.randint(0, 2))   # 70%: 人気キー
        else:
            access_pattern.append(random.randint(3, 19))   # 30%: その他
 
    lru = LRUCache(capacity=5)
    lfu = LFUCache(capacity=5)
 
    for key in access_pattern:
        # get して miss なら put
        for cache in [lru, lfu]:
            if cache.get(key) is None:
                cache.put(key, f"value_{key}")
 
    print("キャッシュポリシー比較 (容量=5, アクセス=1000回)")
    print(f"  LRU ヒット率: {lru.hit_rate():.1%}")
    print(f"  LFU ヒット率: {lfu.hit_rate():.1%}")
 
 
if __name__ == "__main__":
    compare_cache_policies()

"""
popcount（整数のビット中の 1 の数）を3つの手法で実装し比較する。
 
なぜ popcount が重要なのか:
- ハミング距離の計算（誤り訂正符号）
- 集合演算のビットベクトル実装
- チェスエンジンのビットボード評価
- ブルームフィルタの実装
"""
 
import time
 
 
def popcount_naive(n: int) -> int:
    """ビットを1つずつ調べる素朴な方法。
 
    時間: O(log n) — n のビット数に比例
    空間: O(1)
 
    なぜ n & 1 でビットが分かるのか:
    n & 1 は n の最下位ビットを取り出す演算。
    n >>= 1 で右シフトすると次のビットが最下位に来る。
    これを n が 0 になるまで繰り返す。
    """
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count
 
 
def popcount_kernighan(n: int) -> int:
    """Brian Kernighan のアルゴリズム。
 
    時間: O(セットビット数) — 1 のビット数に比例
    空間: O(1)
 
    なぜ n & (n-1) で最下位の 1 ビットが消えるのか:
    n = ...10...0 のとき（最下位の1ビットとその右の0）
    n-1 = ...01...1 となる（その1ビットが0になり右が全て1）
    よって n & (n-1) は最下位の1ビットだけが消える。
 
    例: n = 12 = 1100
         n-1 = 11 = 1011
         n & (n-1) = 1000 = 8  → 最下位の 1(位置2) が消えた
    """
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
 
 
# 8ビットルックアップテーブルの構築
# なぜ 8 ビットなのか:
# - 256 エントリで全パターンを網羅でき、メモリは 256 バイトのみ
# - 16 ビット（65536 エントリ）でも良いが、L1 キャッシュに収まる
#   サイズが望ましい
# - 32 ビット（約40億エントリ）は実用的でない
POPCOUNT_TABLE_8BIT = [0] * 256
for i in range(256):
    # i のビット数 = 最下位ビット + (i >> 1) のビット数
    # この漸化式で 0 から順に構築できる
    POPCOUNT_TABLE_8BIT[i] = (i & 1) + POPCOUNT_TABLE_8BIT[i >> 1]
 
 
def popcount_table(n: int) -> int:
    """8ビットテーブル参照による popcount。
 
    時間: O(1) — 32ビット整数なら常に4回のテーブル参照
    空間: O(256) — テーブルのサイズ
 
    なぜ 8 ビットずつに分割するのか:
    32 ビット整数を 4 つの 8 ビットチャンクに分割し、
    各チャンクの popcount をテーブルから O(1) で取得して合計する。
    """
    return (POPCOUNT_TABLE_8BIT[n & 0xFF] +
            POPCOUNT_TABLE_8BIT[(n >> 8) & 0xFF] +
            POPCOUNT_TABLE_8BIT[(n >> 16) & 0xFF] +
            POPCOUNT_TABLE_8BIT[(n >> 24) & 0xFF])
 
 
def benchmark_popcount():
    """3手法の性能比較。"""
    import random
    random.seed(42)
    test_values = [random.randint(0, 2**32 - 1) for _ in range(100000)]
 
    # 正しさの検証
    for v in test_values[:100]:
        assert popcount_naive(v) == popcount_kernighan(v) == popcount_table(v), \
            f"不一致: {v}"
 
    methods = [
        ("素朴版(ビットスキャン)", popcount_naive),
        ("Kernighan法",          popcount_kernighan),
        ("テーブル参照(8bit)",    popcount_table),
    ]
 
    print("popcount ベンチマーク (100,000 回)")
    print("-" * 50)
    for name, func in methods:
        start = time.perf_counter()
        for v in test_values:
            func(v)
        elapsed = time.perf_counter() - start
        print(f"  {name:25s}: {elapsed:.4f}秒")
 
 
if __name__ == "__main__":
    benchmark_popcount()

"""
三角関数のルックアップテーブル
 
なぜゲーム開発で三角関数テーブルが使われるのか:
1. math.sin/cos は内部で Taylor 展開や CORDIC を使い、
   1回あたり数十〜数百ナノ秒かかる
2. ゲームでは毎フレーム（1/60秒）に数千回の三角関数計算が必要
3. テーブル参照なら配列アクセス1回（数ナノ秒）で済む
4. 角度の精度は 1度 や 0.1度 で十分な場合が多い
 
トレードオフ:
- 精度: テーブルの粒度（1度 vs 0.1度 vs 0.01度）で制御
- 空間: 粒度を細かくするほどテーブルが大きくなる
- 補間: テーブル間の値は線形補間で精度を上げられる
"""
 
import math
import time
 
 
class TrigTable:
    """三角関数ルックアップテーブル（線形補間付き）"""
 
    def __init__(self, resolution: float = 1.0):
        """
        resolution: 角度の刻み幅（度）。小さいほど精度が高いが空間が増える。
 
        なぜコンストラクタで全計算するのか:
        テーブルは不変であり、アプリケーション起動時に1回だけ構築すれば、
        以降は全スレッドで安全に共有できる。
        """
        self.resolution = resolution
        self.size = int(360 / resolution)
        self.sin_table = [0.0] * self.size
        self.cos_table = [0.0] * self.size
 
        for i in range(self.size):
            angle_rad = math.radians(i * resolution)
            self.sin_table[i] = math.sin(angle_rad)
            self.cos_table[i] = math.cos(angle_rad)
 
        # 空間使用量の計算
        self.memory_bytes = self.size * 8 * 2  # float64 × 2テーブル
 
    def sin(self, degrees: float) -> float:
        """テーブル参照 + 線形補間による sin 近似。"""
        degrees = degrees % 360
        idx_f = degrees / self.resolution
        idx = int(idx_f)
        frac = idx_f - idx  # 小数部分（補間用）
 
        if frac < 1e-9:
            return self.sin_table[idx % self.size]
 
        # 線形補間: f(x) ≈ f(a) + (f(b) - f(a)) * t
        val_a = self.sin_table[idx % self.size]
        val_b = self.sin_table[(idx + 1) % self.size]
        return val_a + (val_b - val_a) * frac
 
    def cos(self, degrees: float) -> float:
        """テーブル参照 + 線形補間による cos 近似。"""
        degrees = degrees % 360
        idx_f = degrees / self.resolution
        idx = int(idx_f)
        frac = idx_f - idx
 
        if frac < 1e-9:
            return self.cos_table[idx % self.size]
 
        val_a = self.cos_table[idx % self.size]
        val_b = self.cos_table[(idx + 1) % self.size]
        return val_a + (val_b - val_a) * frac
 
 
def benchmark_trig():
    """精度と速度の比較。"""
    import random
    random.seed(42)
 
    table_1deg = TrigTable(resolution=1.0)    # 360 エントリ
    table_01deg = TrigTable(resolution=0.1)   # 3600 エントリ
 
    test_angles = [random.uniform(0, 360) for _ in range(100000)]
 
    # 精度の比較
    max_error_1deg = 0
    max_error_01deg = 0
    for angle in test_angles[:1000]:
        exact = math.sin(math.radians(angle))
        err_1 = abs(table_1deg.sin(angle) - exact)
        err_01 = abs(table_01deg.sin(angle) - exact)
        max_error_1deg = max(max_error_1deg, err_1)
        max_error_01deg = max(max_error_01deg, err_01)
 
    print("三角関数テーブル: 精度と速度の比較")
    print("=" * 55)
    print(f"  1度刻み:   最大誤差 = {max_error_1deg:.8f}  "
          f"空間 = {table_1deg.memory_bytes:,} bytes")
    print(f"  0.1度刻み: 最大誤差 = {max_error_01deg:.8f}  "
          f"空間 = {table_01deg.memory_bytes:,} bytes")
    print()
 
    # 速度の比較
    methods = [
        ("math.sin",       lambda a: math.sin(math.radians(a))),
        ("テーブル(1度)",   table_1deg.sin),
        ("テーブル(0.1度)", table_01deg.sin),
    ]
    print("速度比較 (100,000 回)")
    print("-" * 45)
    for name, func in methods:
        start = time.perf_counter()
        for a in test_angles:
            func(a)
        elapsed = time.perf_counter() - start
        print(f"  {name:20s}: {elapsed:.4f}秒")
 
 
if __name__ == "__main__":
    benchmark_trig()

"""
ブルームフィルタの完全実装 — パラメータ最適化と偽陽性率の検証付き
 
このコードは以下を含む:
1. 基本的なブルームフィルタクラス
2. 最適パラメータの自動計算
3. 偽陽性率の理論値と想定される実測値の比較
"""
 
import hashlib
import math
 
 
class BloomFilter:
    """ブルームフィルタの完全実装。
 
    なぜ md5 を使うのか:
    ブルームフィルタのハッシュ関数に求められるのは暗号学的安全性ではなく、
    出力の均一分布性である。md5 は暗号用途では破られているが、
    128ビットの出力が均一に分布するという性質は健在であり、
    ブルームフィルタには十分である。
 
    実務では mmh3（MurmurHash3）や xxHash のような
    非暗号学的ハッシュ関数がより高速で推奨される。
    """
 
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        """
        expected_items: 想定される追加要素数
        false_positive_rate: 許容する偽陽性率（0〜1）
 
        なぜこのコンストラクタで m と k を自動計算するのか:
        ユーザーが最適な m と k を手動で計算するのは面倒であり、
        間違いやすい。expected_items と false_positive_rate から
        自動的に最適値を導出する方が安全で使いやすい。
        """
        # 最適なビット配列サイズ: m = -n*ln(p) / (ln2)^2
        self.size = self._optimal_size(expected_items, false_positive_rate)
        # 最適なハッシュ関数数: k = (m/n) * ln2
        self.num_hashes = self._optimal_hash_count(
            self.size, expected_items
        )
        self.bit_array = bytearray(
            (self.size + 7) // 8  # ビット→バイトに変換（切り上げ）
        )
        self.count = 0  # 追加した要素数
 
        # パラメータの記録
        self.expected_items = expected_items
        self.target_fpr = false_positive_rate
 
    @staticmethod
    def _optimal_size(n: int, p: float) -> int:
        """最適なビット配列サイズを計算する。
 
        導出:
        偽陽性率 p = (1 - e^(-kn/m))^k を最小化する m を求める。
        k を最適値 k = (m/n)*ln2 で置換すると:
        m = -n * ln(p) / (ln2)^2
        """
        m = -n * math.log(p) / (math.log(2) ** 2)
        return int(math.ceil(m))
 
    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        """最適なハッシュ関数数を計算する。"""
        k = (m / n) * math.log(2)
        return max(1, int(round(k)))
 
    def _get_bit(self, index: int) -> bool:
        """ビット配列の指定位置の値を取得する。"""
        byte_index = index // 8
        bit_offset = index % 8
        return bool(self.bit_array[byte_index] & (1 << bit_offset))
 
    def _set_bit(self, index: int):
        """ビット配列の指定位置を 1 にする。"""
        byte_index = index // 8
        bit_offset = index % 8
        self.bit_array[byte_index] |= (1 << bit_offset)
 
    def _hashes(self, item: str) -> list:
        """要素から k 個のハッシュ値を生成する。
 
        なぜ double hashing を使うのか:
        k 個の独立したハッシュ関数を用意するのは面倒である。
        代わりに、2つのハッシュ値 h1, h2 から
        gi(x) = h1(x) + i*h2(x) (mod m)  (i = 0, 1, ..., k-1)
        として k 個のハッシュ値を生成する。
        Kirsch & Mitzenmacher (2006) により、この方法は
        k 個の独立ハッシュ関数と同等の偽陽性率を達成することが
        証明されている。
        """
        h = hashlib.md5(str(item).encode()).hexdigest()
        h1 = int(h[:16], 16)
        h2 = int(h[16:], 16)
        return [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
 
    def add(self, item: str):
        """要素を追加する。"""
        for pos in self._hashes(item):
            self._set_bit(pos)
        self.count += 1
 
    def might_contain(self, item: str) -> bool:
        """要素の存在を確認する。
 
        True: 「たぶん存在する」（偽陽性の可能性あり）
        False: 「確実に存在しない」（偽陰性は発生しない）
        """
        return all(self._get_bit(pos) for pos in self._hashes(item))
 
    def theoretical_fpr(self) -> float:
        """現在の状態での理論的偽陽性率。"""
        if self.count == 0:
            return 0.0
        exponent = -self.num_hashes * self.count / self.size
        return (1 - math.exp(exponent)) ** self.num_hashes
 
    def memory_usage_bytes(self) -> int:
        """メモリ使用量（バイト）。"""
        return len(self.bit_array)
 
    def info(self) -> dict:
        """フィルタの状態情報を返す。"""
        return {
            "ビット配列サイズ(m)": self.size,
            "ハッシュ関数数(k)": self.num_hashes,
            "追加済み要素数": self.count,
            "メモリ使用量": f"{self.memory_usage_bytes():,} bytes",
            "理論的偽陽性率": f"{self.theoretical_fpr():.6f}",
            "目標偽陽性率": f"{self.target_fpr:.6f}",
        }
 
 
def verify_bloom_filter():
    """ブルームフィルタの動作検証。"""
    print("=" * 60)
    print("ブルームフィルタの動作検証")
    print("=" * 60)
 
    # 10000 要素、偽陽性率 1% で構築
    bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)
 
    # フィルタ情報
    for key, val in bf.info().items():
        print(f"  {key}: {val}")
    print()
 
    # 10000 個の要素を追加
    added = set()
    for i in range(10000):
        word = f"word_{i}"
        bf.add(word)
        added.add(word)
 
    # 偽陰性の確認（追加した要素は必ず True）
    false_negatives = 0
    for word in added:
        if not bf.might_contain(word):
            false_negatives += 1
    print(f"偽陰性数: {false_negatives} (理論上 0)")
 
    # 偽陽性率の計測
    false_positives = 0
    test_count = 100000
    for i in range(test_count):
        word = f"test_{i}"
        if word not in added and bf.might_contain(word):
            false_positives += 1
 
    actual_fpr = false_positives / test_count
    print(f"想定される偽陽性率: {actual_fpr:.4f} "
          f"(理論値: {bf.theoretical_fpr():.4f})")
 
    # ハッシュセットとの空間比較
    import sys
    hash_set_size = sys.getsizeof(added)
    bloom_size = bf.memory_usage_bytes()
    print(f"\n空間比較:")
    print(f"  ハッシュセット: {hash_set_size:>10,} bytes")
    print(f"  ブルームフィルタ: {bloom_size:>10,} bytes")
    print(f"  削減率: {(1 - bloom_size / hash_set_size) * 100:.1f}%")
 
 
if __name__ == "__main__":
    verify_bloom_filter()

"""
配列内の重複要素検出: 空間 vs 時間のトレードオフ
 
このパターンはコーディング面接で最頻出の一つである。
「空間を O(n) 使えば時間を O(n^2) から O(n) に改善できる」
という典型的なトレードオフを示す。
"""
 
import time
import random
 
 
def has_duplicate_brute_force(arr: list) -> bool:
    """全ペア比較による重複検出。
 
    時間: O(n^2) — 全ペアを比較
    空間: O(1)   — 追加メモリなし
 
    なぜ O(n^2) なのか:
    外側ループが n 回、内側ループが平均 n/2 回。
    合計で n*(n-1)/2 回の比較 = O(n^2)。
    """
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False
 
 
def has_duplicate_sort(arr: list) -> bool:
    """ソート後に隣接要素を比較する方法。
 
    時間: O(n log n) — ソートの時間
    空間: O(n)       — ソート用（Timsort の場合）
 
    なぜソートすると隣接比較だけで済むのか:
    ソート後は同じ値が隣り合う。よって隣接ペアのみ
    チェックすれば全重複を検出できる。
    """
    sorted_arr = sorted(arr)
    for i in range(len(sorted_arr) - 1):
        if sorted_arr[i] == sorted_arr[i + 1]:
            return True
    return False
 
 
def has_duplicate_hash_set(arr: list) -> bool:
    """ハッシュセットによる重複検出。
 
    時間: O(n) — 各要素を1回ずつ処理
    空間: O(n) — ハッシュセットのサイズ
 
    なぜ O(n) なのか:
    set の in 演算子と add 演算子はハッシュテーブルにより
    平均 O(1) で動作する。n 個の要素を1回ずつ処理するので
    全体で O(n)。
    """
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False
 
 
def benchmark_duplicate_detection():
    """3手法の性能比較。"""
    random.seed(42)
 
    print("重複検出ベンチマーク")
    print("=" * 65)
 
    for n in [1000, 5000, 10000]:
        arr = list(range(n))
        arr[-1] = 0  # 最後の要素を重複させる（最悪ケース）
 
        results = {}
        for name, func in [
            ("全ペア比較 O(n^2)", has_duplicate_brute_force),
            ("ソート後比較 O(n log n)", has_duplicate_sort),
            ("ハッシュセット O(n)", has_duplicate_hash_set),
        ]:
            start = time.perf_counter()
            result = func(arr[:])  # コピーして渡す
            elapsed = time.perf_counter() - start
            results[name] = elapsed
            assert result is True
 
        print(f"\nn = {n:,}")
        for name, elapsed in results.items():
            print(f"  {name:30s}: {elapsed:.6f}秒")
 
 
if __name__ == "__main__":
    benchmark_duplicate_detection()

"""
Two Sum: 配列から合計が target になるペアを見つける
 
この問題は LeetCode #1 であり、面接で最も頻出する問題の一つ。
3つの手法が存在し、それぞれ異なるトレードオフを示す。
"""
 
 
def two_sum_brute_force(nums: list, target: int) -> tuple:
    """全ペア探索。
    時間: O(n^2), 空間: O(1)
    """
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None
 
 
def two_sum_sort(nums: list, target: int) -> tuple:
    """ソート + 二分探索 / 二ポインタ。
    時間: O(n log n), 空間: O(n)（インデックスの保持）
 
    注意: ソートするとインデックスが変わるため、
    元のインデックスを別途保持する必要がある。
    """
    indexed = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(indexed) - 1
    while left < right:
        current_sum = indexed[left][1] + indexed[right][1]
        if current_sum == target:
            return (indexed[left][0], indexed[right][0])
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None
 
 
def two_sum_hash(nums: list, target: int) -> tuple:
    """ハッシュマップ。
    時間: O(n), 空間: O(n)
 
    なぜ 1-pass で済むのか:
    各要素 nums[i] を見るとき、target - nums[i] が
    既にマップに登録されていればペアが見つかる。
    まだなければ nums[i] を登録して次へ。
    1回の走査で完了する。
    """
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None
 
 
def test_two_sum():
    """3手法の正当性と性能を検証。"""
    test_cases = [
        ([2, 7, 11, 15], 9, {(0, 1)}),
        ([3, 2, 4], 6, {(1, 2)}),
        ([3, 3], 6, {(0, 1)}),
    ]
 
    for nums, target, expected in test_cases:
        for name, func in [
            ("brute_force", two_sum_brute_force),
            ("sort",        two_sum_sort),
            ("hash",        two_sum_hash),
        ]:
            result = func(nums, target)
            assert result is not None, f"{name}: 解が見つかりません"
            pair = tuple(sorted(result))
            assert pair in expected, \
                f"{name}: {pair} は期待値 {expected} に含まれません"
 
    print("全テストケース通過")
 
 
if __name__ == "__main__":
    test_two_sum()

"""
アンチパターン: 二分探索にメモ化を適用する
 
なぜこれが無意味なのか:
二分探索は各再帰呼び出しで探索範囲が異なる（lo, hi の組み合わせが一意）。
つまり同じ引数で2回呼ばれることがない。
キャッシュに格納してもヒットが0回であり、空間の無駄である。
 
一般原則: メモ化が有効なのは「同じ部分問題が複数回出現する」場合のみ。
再帰であっても、分割統治（二分探索、マージソート、クイックソート）
のように各部分問題が1回しか呼ばれない構造にはメモ化は不要。
"""
 
from functools import lru_cache
 
 
# BAD: 無意味なメモ化（全呼び出しがキャッシュミス）
@lru_cache(maxsize=None)
def binary_search_bad(arr_tuple: tuple, target: int,
                      lo: int, hi: int) -> int:
    """二分探索にメモ化を適用 — 無意味な例。
 
    問題点:
    1. (arr_tuple, target, lo, hi) の組み合わせは全て一意
       → キャッシュヒット率 = 0%
    2. arr_tuple のハッシュ計算に O(n) かかる
       → メモ化なしより遅くなる
    3. キャッシュが O(log n) エントリ分のメモリを無駄に消費する
    """
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr_tuple[mid] == target:
        return mid
    elif arr_tuple[mid] < target:
        return binary_search_bad(arr_tuple, target, mid + 1, hi)
    else:
        return binary_search_bad(arr_tuple, target, lo, mid - 1)
 
 
# GOOD: メモ化なしの素直な実装
def binary_search_good(arr: list, target: int) -> int:
    """素直な二分探索 — 再帰ではなくループ版。
 
    なぜループ版が良いのか:
    1. 再帰オーバーヘッドがない
    2. スタック空間 O(1)（再帰版は O(log n)）
    3. 末尾再帰最適化がない Python では特に重要
    """
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
 
def demonstrate_useless_memoization():
    """無意味なメモ化のコスト。"""
    import time
 
    arr = list(range(100000))
    arr_tuple = tuple(arr)
    target = 99999
 
    # キャッシュクリア
    binary_search_bad.cache_clear()
 
    start = time.perf_counter()
    for _ in range(100):
        binary_search_bad.cache_clear()
        binary_search_bad(arr_tuple, target, 0, len(arr) - 1)
    elapsed_bad = time.perf_counter() - start
 
    start = time.perf_counter()
    for _ in range(100):
        binary_search_good(arr, target)
    elapsed_good = time.perf_counter() - start
 
    info = binary_search_bad.cache_info()
    print("無意味なメモ化の実例")
    print(f"  メモ化版:  {elapsed_bad:.4f}秒")
    print(f"  素直な版:  {elapsed_good:.4f}秒")
    print(f"  キャッシュヒット: {info.hits}回 "
          f"(ミス: {info.misses}回)")
    print(f"  → ヒット率 0% であり、メモ化は完全に無駄")
 
 
if __name__ == "__main__":
    demonstrate_useless_memoization()

"""
アンチパターン: 入力空間を過大評価したルックアップテーブル
 
なぜこれが危険なのか:
テーブルサイズが大きすぎると:
1. メモリ不足（OOM）でプロセスがクラッシュする
2. テーブルが L1/L2 キャッシュに収まらず、参照が遅くなる
   → テーブル参照のはずが、毎回メインメモリアクセスになる
   → 元の計算より遅くなる逆転現象が発生しうる
3. 構築時間が長くなり、アプリケーションの起動が遅延する
"""
 
import sys
 
 
def demonstrate_table_size_problem():
    """テーブルサイズの見積もり失敗例。"""
    print("テーブルサイズの見積もり")
    print("=" * 50)
 
    sizes = [
        ("8ビット",  2**8,   "popcount 等に最適"),
        ("16ビット", 2**16,  "まだ許容範囲"),
        ("20ビット", 2**20,  "L2 キャッシュに収まる可能性"),
        ("24ビット", 2**24,  "16MB — L3 キャッシュの限界"),
        ("32ビット", 2**32,  "16GB — 一般的なPCのRAMを超える"),
    ]
 
    for name, size, comment in sizes:
        # int のリストの場合（Python の int は 28 バイト以上）
        memory_mb = size * 28 / (1024 * 1024)
        feasible = "OK" if memory_mb < 100 else "危険" if memory_mb < 10000 else "不可能"
        print(f"  {name:10s}: {size:>15,}エントリ  "
              f"~{memory_mb:>10,.0f}MB  [{feasible}] {comment}")
 
    print()
    print("対策: 分割テーブル")
    print("  32ビット値の popcount を求めるとき:")
    print("  BAD:  table[2^32] = 16GB のテーブル")
    print("  GOOD: table[2^8] = 256 エントリ × 4回参照 = 実質 O(1)")
 
 
# BAD: メモリを大量消費するテーブル
def create_bad_table():
    """絶対に実行しないこと — メモリを 16GB 以上消費する。"""
    # table = [0] * (2**32)  # ~16GB — 実行するとクラッシュの恐れ
    print("このコードは危険なので実行をスキップします")
 
 
# GOOD: 分割テーブルで同じ結果を達成
SMALL_TABLE = [0] * 256
for i in range(256):
    SMALL_TABLE[i] = (i & 1) + SMALL_TABLE[i >> 1]
 
 
def popcount_safe(n: int) -> int:
    """安全な分割テーブルによる popcount。
 
    なぜ 4 回のテーブル参照が 1 回の巨大テーブル参照と同等なのか:
    32ビット整数は 4 つの 8 ビットチャンクに分割できる。
    各チャンクの popcount は独立に計算でき、合計すれば全体の
    popcount になる。4 回の O(1) 参照は依然として O(1) である。
    しかもテーブルは L1 キャッシュに確実に収まるため、
    巨大テーブルよりキャッシュ効率が良い。
    """
    return (SMALL_TABLE[n & 0xFF] +
            SMALL_TABLE[(n >> 8) & 0xFF] +
            SMALL_TABLE[(n >> 16) & 0xFF] +
            SMALL_TABLE[(n >> 24) & 0xFF])
 
 
if __name__ == "__main__":
    demonstrate_table_size_problem()

"""
アンチパターン: 変化するデータに対してキャッシュを無効化しない
 
なぜこれが危険なのか:
キャッシュした値が古くなると「正しくない結果」を返すようになる。
これはサイレントバグ（エラーにならず静かに間違った結果を返す）であり、
デバッグが非常に困難である。
 
Phil Karlton の有名な格言:
"There are only two hard things in Computer Science:
 cache invalidation and naming things."
（コンピュータサイエンスで本当に難しいのは
 キャッシュの無効化と命名の2つだけだ）
"""
 
from functools import lru_cache
import time
 
 
# BAD: 外部状態に依存する関数をキャッシュ
EXCHANGE_RATE = {"USD_JPY": 150.0}  # 為替レートは常に変動する
 
 
@lru_cache(maxsize=128)
def convert_usd_to_jpy_bad(amount: float) -> float:
    """BAD: 為替レートが変わってもキャッシュが古い値を返す。"""
    return amount * EXCHANGE_RATE["USD_JPY"]
 
 
# GOOD: TTL 付きキャッシュで鮮度を保証
class CurrencyConverter:
    """為替変換器 — TTL 付きキャッシュ版。
 
    なぜ TTL が必要なのか:
    為替レートは秒単位で変動する。しかし、
    毎回 API を呼ぶのはコストが高い（レート制限、遅延）。
    TTL を設定することで「最大 N 秒前のレート」を使い、
    API 呼び出し回数を削減しつつ、ある程度の鮮度を保証する。
    """
 
    def __init__(self, ttl_seconds: float = 60.0):
        self.ttl = ttl_seconds
        self._cache = {}
        self._timestamps = {}
 
    def get_rate(self, pair: str) -> float:
        """為替レートを取得（キャッシュ付き）。"""
        now = time.time()
        if pair in self._cache:
            age = now - self._timestamps[pair]
            if age < self.ttl:
                return self._cache[pair]
 
        # キャッシュミスまたは期限切れ → API 呼び出し（シミュレート）
        rate = self._fetch_rate_from_api(pair)
        self._cache[pair] = rate
        self._timestamps[pair] = now
        return rate
 
    def _fetch_rate_from_api(self, pair: str) -> float:
        """API からレートを取得（シミュレート）。"""
        # 実際にはここで外部 API を呼ぶ
        return EXCHANGE_RATE.get(pair, 1.0)
 
    def convert(self, amount: float, pair: str = "USD_JPY") -> float:
        """通貨変換。"""
        return amount * self.get_rate(pair)
 
 
def demonstrate_cache_invalidation():
    """キャッシュ無効化の重要性を示す。"""
    print("キャッシュ無効化の問題")
    print("=" * 50)
 
    # BAD 版
    convert_usd_to_jpy_bad.cache_clear()
    result1 = convert_usd_to_jpy_bad(100.0)
    print(f"BAD版: $100 = ¥{result1:.0f} (レート: {EXCHANGE_RATE['USD_JPY']})")
 
    EXCHANGE_RATE["USD_JPY"] = 140.0  # レートが変動
    result2 = convert_usd_to_jpy_bad(100.0)
    print(f"BAD版: $100 = ¥{result2:.0f} (レート変動後も古い値が返る!)")
 
    # GOOD 版
    converter = CurrencyConverter(ttl_seconds=0.1)  # TTL 0.1秒
    result3 = converter.convert(100.0)
    print(f"GOOD版: $100 = ¥{result3:.0f}")
 
    EXCHANGE_RATE["USD_JPY"] = 130.0
    time.sleep(0.15)  # TTL を超えるまで待つ
    result4 = converter.convert(100.0)
    print(f"GOOD版: $100 = ¥{result4:.0f} (TTL経過後に新レートを取得)")
 
 
if __name__ == "__main__":
    demonstrate_cache_invalidation()

"""
エッジケース: メモ化で再帰制限に到達する
 
Python のデフォルト再帰制限は 1000 である。
メモ化フィボナッチで fib(1000) を直接呼ぶと
RecursionError が発生する。
 
なぜこれが問題なのか:
メモ化は再帰を前提とするため、深い再帰が必要な問題では
Python の再帰制限がボトルネックになる。
 
解決策:
1. sys.setrecursionlimit() で上限を引き上げる（推奨しない）
   → スタックオーバーフローのリスクがある
2. ボトムアップ DP に書き換える（推奨）
   → ループなので再帰制限に依存しない
3. 反復的深化: 小さい値から段階的に呼ぶ（妥協策）
   → キャッシュが温まるので深い再帰が発生しない
"""
 
import sys
 
 
def fib_memo_recursive(n: int, memo: dict = None) -> int:
    """メモ化フィボナッチ（再帰版）。"""
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo_recursive(n - 1, memo) + \
              fib_memo_recursive(n - 2, memo)
    return memo[n]
 
 
def fib_iterative_warmup(n: int) -> int:
    """反復的にキャッシュを温めてから大きな値を計算する。
 
    なぜこの方法が有効なのか:
    fib(500) を先に呼ぶと、fib(0)〜fib(500) がキャッシュされる。
    その後 fib(1000) を呼ぶと、fib(501)〜fib(1000) の計算で
    fib(499) と fib(500) はキャッシュから取得される。
    再帰の深さは最大 500 となり、制限内に収まる。
    """
    memo = {}
    step = 400  # 再帰制限よりも十分小さいステップ
    for start in range(0, n + 1, step):
        target = min(start + step, n)
        fib_memo_recursive(target, memo)
    return memo.get(n, fib_memo_recursive(n, memo))
 
 
def fib_bottom_up_space_optimized(n: int) -> int:
    """ボトムアップ DP（空間最適化版）。
 
    なぜ空間 O(1) で済むのか:
    fib(i) の計算には fib(i-1) と fib(i-2) の2つの値だけが必要。
    それより前の値は不要であるため、2変数のみで十分。
    """
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1
 
 
def demonstrate_recursion_limit():
    """再帰制限の問題と解決策。"""
    print("再帰制限のエッジケース")
    print("=" * 50)
 
    # 現在の再帰制限
    print(f"現在の再帰制限: {sys.getrecursionlimit()}")
 
    # 小さい値は問題なし
    memo = {}
    result = fib_memo_recursive(100, memo)
    print(f"fib(100) = {len(str(result))}桁 [OK]")
 
    # 大きい値は RecursionError
    try:
        memo2 = {}
        fib_memo_recursive(5000, memo2)
        print("fib(5000) [OK — 再帰制限が十分大きい環境]")
    except RecursionError:
        print("fib(5000) [RecursionError発生]")
 
    # 反復的ウォームアップで回避
    result_warmup = fib_iterative_warmup(5000)
    print(f"fib(5000) (ウォームアップ版) = {len(str(result_warmup))}桁 [OK]")
 
    # ボトムアップで回避
    result_bu = fib_bottom_up_space_optimized(5000)
    print(f"fib(5000) (ボトムアップ版) = {len(str(result_bu))}桁 [OK]")
 
    assert result_warmup == result_bu, "結果が一致しません"
 
 
if __name__ == "__main__":
    demonstrate_recursion_limit()

"""
エッジケース: ブルームフィルタに想定以上の要素を追加すると偽陽性率が急増する
 
なぜこれが重要なのか:
ブルームフィルタのサイズは想定要素数から事前に決定される。
想定以上の要素を追加すると、ビット配列がほぼ全て 1 になり
（「飽和」状態）、偽陽性率が 100% に近づく。
これは事実上フィルタが役に立たない状態である。
 
対策:
1. 要素数を事前に見積もり、余裕を持ったサイズにする
2. Scalable Bloom Filter を使う（要素数に応じて自動拡張）
3. 飽和を検知したら新しいフィルタに切り替える
"""
 
import math
import hashlib
 
 
class MonitoredBloomFilter:
    """飽和監視付きブルームフィルタ。"""
 
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        self.expected_items = expected_items
        self.target_fpr = false_positive_rate
        m = int(-expected_items * math.log(false_positive_rate) /
                (math.log(2) ** 2))
        self.size = max(m, 64)
        self.num_hashes = max(1, int(round(
            (self.size / expected_items) * math.log(2)
        )))
        self.bit_array = bytearray((self.size + 7) // 8)
        self.count = 0
        self._set_bits = 0  # 1 になっているビット数
 
    def _hashes(self, item: str) -> list:
        h = hashlib.md5(str(item).encode()).hexdigest()
        h1 = int(h[:16], 16)
        h2 = int(h[16:], 16)
        return [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
 
    def _get_bit(self, idx: int) -> bool:
        return bool(self.bit_array[idx // 8] & (1 << (idx % 8)))
 
    def _set_bit(self, idx: int):
        byte_idx = idx // 8
        bit_off = idx % 8
        if not (self.bit_array[byte_idx] & (1 << bit_off)):
            self._set_bits += 1
            self.bit_array[byte_idx] |= (1 << bit_off)
 
    def add(self, item: str):
        for pos in self._hashes(item):
            self._set_bit(pos)
        self.count += 1
 
    def might_contain(self, item: str) -> bool:
        return all(self._get_bit(pos) for pos in self._hashes(item))
 
    def saturation(self) -> float:
        """飽和率（0.0〜1.0）を返す。"""
        return self._set_bits / self.size
 
    def estimated_fpr(self) -> float:
        """現在の飽和率から推定される偽陽性率。"""
        sat = self.saturation()
        return sat ** self.num_hashes
 
    def is_saturated(self, threshold: float = 0.5) -> bool:
        """フィルタが飽和状態かどうかを判定する。
 
        なぜ閾値 0.5 なのか:
        最適なハッシュ関数数のとき、各ビットが 1 になる確率は
        ちょうど 0.5 である。これを超えると急速に偽陽性率が上昇する。
        """
        return self.saturation() > threshold
 
 
def demonstrate_saturation():
    """飽和の進行と偽陽性率の上昇を示す。"""
    print("ブルームフィルタの飽和")
    print("=" * 65)
    print(f"{'追加数':>10s}  {'飽和率':>8s}  {'推定FPR':>10s}  "
          f"{'想定される実FPR':>15s}  {'状態':>8s}")
    print("-" * 65)
 
    bf = MonitoredBloomFilter(expected_items=1000, false_positive_rate=0.01)
 
    checkpoints = [100, 500, 1000, 2000, 5000, 10000]
 
    for target in checkpoints:
        while bf.count < target:
            bf.add(f"item_{bf.count}")
 
        # 偽陽性率を計測
        fp = 0
        tests = 10000
        for i in range(tests):
            probe = f"probe_{i}"
            if bf.might_contain(probe):
                fp += 1
        actual_fpr = fp / tests
 
        status = "正常" if not bf.is_saturated() else "飽和!"
        print(f"{bf.count:>10,d}  {bf.saturation():>8.1%}  "
              f"{bf.estimated_fpr():>10.4f}  "
              f"{actual_fpr:>15.4f}  {status:>8s}")
 
 
if __name__ == "__main__":
    demonstrate_saturation()

"""
演習1: グリッド経路数の計算にメモ化を適用する
 
問題:
m x n のグリッドにおいて、左上 (0,0) から右下 (m-1,n-1) まで
右か下にのみ移動する場合の経路数を求めよ。
 
ヒント:
- grid_paths(m, n) = grid_paths(m-1, n) + grid_paths(m, n-1)
- 基底条件: m == 1 または n == 1 のとき経路は 1 通り
"""
 
import time
 
 
def grid_paths_naive(m: int, n: int) -> int:
    """メモ化なし版。時間計算量は？ 自分で考えてみよ。"""
    if m == 1 or n == 1:
        return 1
    return grid_paths_naive(m - 1, n) + grid_paths_naive(m, n - 1)
 
 
# TODO: grid_paths_memo(m, n) をメモ化付きで実装せよ
# def grid_paths_memo(m, n, memo=None):
#     ...
 
 
# 検証用
if __name__ == "__main__":
    # 小さい入力で確認
    print(f"grid_paths(3, 3) = {grid_paths_naive(3, 3)}")  # 6
    print(f"grid_paths(4, 4) = {grid_paths_naive(4, 4)}")  # 20
 
    # m=15, n=15 で素朴版の遅さを体感（数秒かかるはず）
    start = time.perf_counter()
    result = grid_paths_naive(15, 15)
    elapsed = time.perf_counter() - start
    print(f"grid_paths(15, 15) = {result}  ({elapsed:.3f}秒)")
    # メモ化版なら瞬時に完了するはず

"""
演習2: ビット反転テーブル
 
問題:
8ビット値のビット反転テーブルを構築せよ。
例: 0b11010010 → 0b01001011  (上位と下位を入れ替え)
 
ヒント:
reverse_bits_8(n) は n の 8ビットを反転する。
0b10110000 → 0b00001101
 
全 256 パターンを事前計算してテーブルに格納する。
"""
 
 
def reverse_bits_8(n: int) -> int:
    """8ビット値のビット反転（素朴版）。"""
    result = 0
    for _ in range(8):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result
 
 
# TODO: テーブルを構築
# REVERSE_TABLE = [reverse_bits_8(i) for i in range(256)]
 
# TODO: 32ビット整数のビット反転をテーブル参照で実装
# def reverse_bits_32(n):
#     ...

"""
演習3: LRU キャッシュの自作実装
 
要件:
1. get(key): O(1) でキャッシュから取得。ミス時は -1 を返す。
2. put(key, value): O(1) で追加/更新。容量超過時は最古を削除。
 
ヒント:
- ハッシュマップ: key → ノードへの参照（O(1) アクセス）
- 二重連結リスト: アクセス順を管理（O(1) で移動・削除）
- ダミーの head と tail ノードを使うと境界条件の処理が楽になる
"""
 
 
class Node:
    """二重連結リストのノード。"""
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
 
 
class LRUCacheManual:
    """LRU キャッシュ — 自作版。"""
 
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key → Node
 
        # ダミーノード（番兵）
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    # TODO: _remove(node), _add_to_front(node), get(key), put(key, value)
    # を実装せよ
 
 
# テスト
if __name__ == "__main__":
    cache = LRUCacheManual(2)
    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1      # key=1 にアクセス → 最新に
    cache.put(3, 3)               # 容量超過 → key=2 が追い出される
    assert cache.get(2) == -1     # key=2 は追い出し済み
    cache.put(4, 4)               # 容量超過 → key=1 が追い出される
    assert cache.get(1) == -1
    assert cache.get(3) == 3
    assert cache.get(4) == 4
    print("全テスト通過")

"""
演習4: Counting Bloom Filter
 
通常のブルームフィルタは削除ができない（ビットを 0 に戻すと
他の要素の情報が失われるため）。Counting Bloom Filter は
各位置にカウンタを持つことでこの問題を解決する。
 
要件:
1. add(item): 各ハッシュ位置のカウンタをインクリメント
2. remove(item): 各ハッシュ位置のカウンタをデクリメント
3. might_contain(item): 全カウンタが 0 より大きいか判定
4. カウンタオーバーフロー（> 15）時の対処を考慮すること
 
注意:
- 追加していない要素を remove するとカウンタが不整合になる
- この問題はブルームフィルタの本質的な制約であり、
  Counting Bloom Filter でも完全には解決できない
"""
 
 
class CountingBloomFilter:
    """Counting Bloom Filter のスケルトン。"""
 
    def __init__(self, size: int = 1000, num_hashes: int = 3):
        self.size = size
        self.num_hashes = num_hashes
        # 4ビットカウンタ → 1バイトに2カウンタを格納可能
        # ここでは簡略化のためリストで実装
        self.counters = [0] * size
 
    # TODO: _hashes(item), add(item), remove(item),
    #       might_contain(item) を実装せよ
    # ヒント: remove で counter < 0 にならないようにすること
 
 
if __name__ == "__main__":
    cbf = CountingBloomFilter(size=10000, num_hashes=5)
    cbf.add("apple")
    cbf.add("banana")
    assert cbf.might_contain("apple") is True
    assert cbf.might_contain("banana") is True
 
    cbf.remove("apple")
    assert cbf.might_contain("apple") is False  # 削除成功
    assert cbf.might_contain("banana") is True   # 影響なし
    print("Counting Bloom Filter テスト通過")

"""
演習5: LCS の空間最適化
 
通常の LCS DP テーブル:
     ""  a  b  c  d  e
  "" [0, 0, 0, 0, 0, 0]
  a  [0, 1, 1, 1, 1, 1]
  c  [0, 1, 1, 2, 2, 2]
  e  [0, 1, 1, 2, 2, 3]
 
空間 O(m*n) → 文字列が長いとメモリ不足に
 
ヒント:
- dp[i][j] は dp[i-1][j] と dp[i][j-1] と dp[i-1][j-1] のみに依存
- 2行分だけ保持すれば十分 → 空間 O(n)
- さらに工夫すると 1行 + 1変数 で O(n) に
"""
 
 
def lcs_full_table(s1: str, s2: str) -> int:
    """通常版 LCS — 空間 O(m*n)。"""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
 
 
# TODO: lcs_space_optimized(s1, s2) を空間 O(min(m,n)) で実装せよ
# def lcs_space_optimized(s1, s2):
#     ...
 
if __name__ == "__main__":
    assert lcs_full_table("abcde", "ace") == 3
    assert lcs_full_table("abc", "def") == 0
    # assert lcs_space_optimized("abcde", "ace") == 3
    print("LCS テスト通過")