set_diff_Perf.py

"""Goal: Prove that set lookups ($O(1)$) destroy list lookups ($O(n)$) when processing large wordlists."""

import time
import random

# Generate 2 million random integers
size = 2_000_000
search_space = [random.randint(0, size*2) for _ in range(size)]
targets = [random.randint(0, size*2) for _ in range(1000)] # 1000 items to look for

# --- Method 1: List Lookup (Slow) ---
start = time.perf_counter()
found_list = [t for t in targets if t in search_space] # O(n) scan for EVERY target
duration_list = time.perf_counter() - start

# --- Method 2: Set Lookup (Fast) ---
start = time.perf_counter()
search_set = set(search_space) # One-time cost to build set
found_set = [t for t in targets if t in search_set] # O(1) lookup
duration_set = time.perf_counter() - start

print(f"List time:{duration_list:.4f}s")
print(f"Set time:{duration_set:.4f}s")
#Typical results: Set is often 1000x+ faster here.