計算理論の地平：P vs NP・近似アルゴリズム・最近の発見

import time, random, itertools
random.seed(0)n, capacity = 22, 50          # 全数探索の限界くらいitems = [(random.randint(1, 20), random.randint(1, 30)) for _ in range(n)]  # (weight, value)
# ① 総当たり O(2^n)def brute(items, cap):    best = 0    for mask in range(1 << len(items)):        w = sum(items[i][0] for i in range(len(items)) if mask >> i & 1)        v = sum(items[i][1] for i in range(len(items)) if mask >> i & 1)        if w <= cap:            best = max(best, v)    return best
# ② DP O(n × cap)def dp(items, cap):    table = [0] * (cap + 1)    for w, v in items:        for c in range(cap, w - 1, -1):            table[c] = max(table[c], table[c - w] + v)    return table[cap]
# ③ 貪欲（価値/重さ比、近似）def greedy(items, cap):    sorted_items = sorted(items, key=lambda x: -x[1] / x[0])    total = 0    for w, v in sorted_items:        if cap >= w:            cap -= w; total += v    return total
t0 = time.perf_counter(); v_b = brute(items, capacity);  t_b = time.perf_counter() - t0t0 = time.perf_counter(); v_d = dp(items, capacity);     t_d = time.perf_counter() - t0t0 = time.perf_counter(); v_g = greedy(items, capacity); t_g = time.perf_counter() - t0print(f"総当たり: {v_b}  ({t_b:.4f} s)")print(f"DP:       {v_d}  ({t_d:.4f} s)")print(f"貪欲近似: {v_g}  ({t_g:.4f} s, ratio={v_g/v_b:.2%})")

import hashlib, math
class BloomFilter:    def __init__(self, n_items, fp_rate=0.01):        # ビット配列のサイズと使うハッシュ関数の数        self.size = int(-n_items * math.log(fp_rate) / (math.log(2) ** 2))        self.k = int(self.size / n_items * math.log(2))        self.bits = [False] * self.size
    def _hashes(self, x):        h = hashlib.md5(str(x).encode()).digest()        for i in range(self.k):            yield int.from_bytes(h[i*2:(i+1)*2], 'big') % self.size
    def add(self, x):        for h in self._hashes(x):            self.bits[h] = True
    def contains(self, x):        return all(self.bits[h] for h in self._hashes(x))
# 使ってみるbf = BloomFilter(10000, fp_rate=0.01)for x in range(10000):    bf.add(f"item-{x}")
print("入ってる:", bf.contains("item-42"))   # → Trueprint("入ってない:", bf.contains("nope"))     # → ほぼ Falsefp = sum(bf.contains(f"unknown-{x}") for x in range(10000)) / 10000print(f"誤検出率: {fp:.2%} (目標 1.00%)")

import hashlib, math
class HyperLogLog:    def __init__(self, p=14):       # p=14 → 16384 バケット → 約 0.81% 誤差        self.p = p        self.m = 1 << p        self.M = [0] * self.m
    def add(self, x):        h = int(hashlib.md5(str(x).encode()).hexdigest()[:16], 16)        idx = h & (self.m - 1)        rest = h >> self.p        # 末尾の 0 の個数 + 1        rho = (rest & -rest).bit_length() if rest else 64 - self.p        self.M[idx] = max(self.M[idx], rho)
    def estimate(self):        alpha = 0.7213 / (1 + 1.079 / self.m)        Z = 1.0 / sum(2 ** -m for m in self.M)        return alpha * self.m * self.m * Z
# 1000万ユニーク要素を投入hll = HyperLogLog(p=14)true_count = 10_000_000for x in range(true_count):    hll.add(x)estimated = hll.estimate()print(f"真の値: {true_count}")print(f"推定:   {estimated:.0f}  誤差: {abs(estimated-true_count)/true_count:.2%}")