[速習] 配列から欠けている数字を見つける「XORトリック」の深い理論と実践 #Python – Qiita

# benchmark_xor.py
import time
import random
from typing import Callable, List, Tuple

N = 10**7

def generate_missing_array(n: int) -> tuple[List[int], int]:
    """1からnまでの数から1つランダムに欠損させた配列を生成"""
    missing = random.randint(1, n)
    arr = [i for i in range(1, n+1) if i != missing]
    random.shuffle(arr)
    return arr, missing

def xor_1_to_n(n: int) -> int:
    """1 ^ 2 ^ ... ^ n を O(1) で計算"""
    return [n, 1, n + 1, 0][n & 3]

# 方法1: XOR法
def find_missing_xor(arr: List[int], n: int) -> int:
    result = xor_1_to_n(n)
    for num in arr:
        result ^= num
    return result

# 方法2: 総和法
def find_missing_sum(arr: List[int], n: int) -> int:
    expected = n * (n + 1) // 2
    actual = sum(arr)
    return expected - actual

# 方法3: set差分
def find_missing_set(arr: List[int], n: int) -> int:
    full_set = set(range(1, n + 1))
    arr_set = set(arr)
    return (full_set - arr_set).pop()

def benchmark(func: Callable, arr: List[int], n: int, name: str, runs: int = 3) -> tuple[float, int]:
    times = []
    for _ in range(runs):
        start = time.perf_counter()
        result = func(arr, n)
        elapsed = time.perf_counter() - start
        times.append(elapsed)
    
    avg_time = sum(times) / len(times)
    return avg_time, result

# 実行
print(f"=== パフォーマンス比較 (n={N:,}) ===")
arr, missing = generate_missing_array(N)
print(f"欠損値: {missing}\n")

methods = [
    (find_missing_xor, "XOR法"),
    (find_missing_sum, "総和法"),
    (find_missing_set, "set差分"),
]

for func, name in methods:
    avg_time, result = benchmark(func, arr.copy(), N, name)
    print(f"| {name} | {avg_time * 1000:.0f}ms | {result} |")