#!/usr/bin/env python3
# bench-linux-0002.py
# kernel/auditsc.c audit_filter_rules: per-name linear scan of inode list.
# Models O(F*R) → O(F+R) via list-scan inside a loop vs set/dict lookup.

import sys
import time


def bench_defective(n, k):
    """Outer loop over N, inner linear list scan over K — O(N*K)."""
    pool = list(range(k))
    items = list(range(n))
    t0 = time.perf_counter()
    accepted = []
    for x in items:
        if x in pool:                  # list __contains__ = O(K)
            accepted.append(x)
        # simulate nested work: scan pool to find position
        try:
            _ = pool.index(x)
        except ValueError:
            pass
    return time.perf_counter() - t0


def bench_fixed(n, k):
    """Outer loop over N, inner O(1) set/dict lookup."""
    pool = list(range(k))
    pool_set = set(pool)
    pool_pos = {v: i for i, v in enumerate(pool)}
    items = list(range(n))
    t0 = time.perf_counter()
    accepted = []
    for x in items:
        if x in pool_set:              # O(1)
            accepted.append(x)
        _ = pool_pos.get(x)            # O(1)
    return time.perf_counter() - t0


TRIALS = 3
CASES = [(100, 20), (500, 50), (1000, 100), (2000, 200)]


def run():
    lines = []
    header = "=== linux-0002: auditsc audit_filter_rules inode-list scan ==="
    print(header); lines.append(header)
    for n, k in CASES:
        df = min(bench_defective(n, k) for _ in range(TRIALS))
        fx = min(bench_fixed(n, k) for _ in range(TRIALS))
        speedup = (df / fx) if fx > 0 else float("inf")
        line = f"F={n:<5} R={k:<5}: defective={df*1000:.3f}ms  fixed={fx*1000:.3f}ms  speedup={speedup:.1f}x"
        print(line); lines.append(line); sys.stdout.flush()
    return lines


if __name__ == "__main__":
    run()