#!/usr/bin/env python3
# bench-linux-0004.py
# net/core/neighbour.c lookup_neigh_parms: tbl->parms_list linear scan per op.
# Models O(N) lookups -> O(1) via hash/dict membership.

import sys
import time


def bench_defective(n):
    """Per-op linear list scan — O(N) per op."""
    items = list(range(n))
    ops = list(range(n))
    t0 = time.perf_counter()
    for op in ops:
        _ = op in items                # O(N) per op
    return time.perf_counter() - t0


def bench_fixed(n):
    """Per-op O(1) dict/set lookup."""
    items = set(range(n))
    ops = list(range(n))
    t0 = time.perf_counter()
    for op in ops:
        _ = op in items                # O(1) per op
    return time.perf_counter() - t0


TRIALS = 3
SIZES = [100, 500, 1000, 2000]


def run():
    lines = []
    header = "=== linux-0004: neighbour.c lookup_neigh_parms list walk ==="
    print(header); lines.append(header)
    for n in SIZES:
        df = min(bench_defective(n) for _ in range(TRIALS))
        fx = min(bench_fixed(n) for _ in range(TRIALS))
        speedup = (df / fx) if fx > 0 else float("inf")
        line = f"P={n:<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()