# linear_algebra_timeit.py

import timeit

def dot_loop(a, b):
    result = 0
    for i in range(len(a)):
        result += a[i] * b[i]
    return result

def dot_linalg(a, b):
    return sum(x * y for x, y in zip(a, b))

def matrix_mult_loop(A, B):
    rows_A, cols_A = len(A), len(A[0])
    rows_B, cols_B = len(B), len(B[0])
    result = [[0] * cols_B for _ in range(rows_A)]
    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                result[i][j] += A[i][k] * B[k][j]
    return result

def matrix_mult_linalg(A, B):
    return [[sum(a * b for a, b in zip(row, col)) for col in zip(*B)] for row in A]

def normalize_loop(v):
    mag = 0
    for x in v:
        mag += x * x
    mag = mag ** 0.5
    result = []
    for x in v:
        result.append(x / mag)
    return result

def normalize_linalg(v):
    mag = sum(x * x for x in v) ** 0.5
    return [x / mag for x in v]

def add_loop(a, b):
    result = []
    for i in range(len(a)):
        result.append(a[i] + b[i])
    return result

def add_linalg(a, b):
    return [x + y for x, y in zip(a, b)]

def transpose_loop(M):
    rows, cols = len(M), len(M[0])
    result = []
    for c in range(cols):
        row = []
        for r in range(rows):
            row.append(M[r][c])
        result.append(row)
    return result

def transpose_linalg(M):
    return list(map(list, zip(*M)))

def cross_product_loop(a, b):
    return [
        a[1] * b[2] - a[2] * b[1],
        a[2] * b[0] - a[0] * b[2],
        a[0] * b[1] - a[1] * b[0]
    ]

def cross_product_linalg(a, b):
    return [a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]

def run_benchmarks():
    print("=" * 70)
    print("LINEAR ALGEBRA VS LOOPS PERFORMANCE")
    print("=" * 70)
    
    sizes = [100, 500, 1000]
    
    for n in sizes:
        print(f"\n--- SIZE n={n} ---\n")
        
        v1 = list(range(n))
        v2 = list(range(n, 2*n))
        
        print(f"DOT PRODUCT (n={n}):")
        t1 = timeit.timeit(lambda: dot_loop(v1, v2), number=1000)
        t2 = timeit.timeit(lambda: dot_linalg(v1, v2), number=1000)
        print(f"  Loop:        {t1:.6f}s")
        print(f"  Comprehension: {t2:.6f}s")
        print(f"  Speedup:     {t1/t2:.2f}x\n")
        
        print(f"ELEMENT-WISE ADD (n={n}):")
        t1 = timeit.timeit(lambda: add_loop(v1, v2), number=1000)
        t2 = timeit.timeit(lambda: add_linalg(v1, v2), number=1000)
        print(f"  Loop:        {t1:.6f}s")
        print(f"  Comprehension: {t2:.6f}s")
        print(f"  Speedup:     {t1/t2:.2f}x\n")
        
        print(f"NORMALIZE (n={n}):")
        t1 = timeit.timeit(lambda: normalize_loop(v1), number=1000)
        t2 = timeit.timeit(lambda: normalize_linalg(v1), number=1000)
        print(f"  Loop:        {t1:.6f}s")
        print(f"  Comprehension: {t2:.6f}s")
        print(f"  Speedup:     {t1/t2:.2f}x\n")
        
        if n <= 100:
            m = 50
            M1 = [[i+j for j in range(m)] for i in range(m)]
            M2 = [[i*j+1 for j in range(m)] for i in range(m)]
            
            print(f"MATRIX MULTIPLY ({m}x{m}):")
            t1 = timeit.timeit(lambda: matrix_mult_loop(M1, M2), number=10)
            t2 = timeit.timeit(lambda: matrix_mult_linalg(M1, M2), number=10)
            print(f"  Nested loops: {t1:.6f}s")
            print(f"  Comprehension: {t2:.6f}s")
            print(f"  Speedup:     {t1/t2:.2f}x\n")
            
            print(f"MATRIX TRANSPOSE ({m}x{m}):")
            t1 = timeit.timeit(lambda: transpose_loop(M1), number=1000)
            t2 = timeit.timeit(lambda: transpose_linalg(M1), number=1000)
            print(f"  Loop:        {t1:.6f}s")
            print(f"  zip(*M):     {t2:.6f}s")
            print(f"  Speedup:     {t1/t2:.2f}x\n")
        
        if n == 100:
            v3 = [1.0, 2.0, 3.0]
            v4 = [4.0, 5.0, 6.0]
            print(f"CROSS PRODUCT (3D):")
            t1 = timeit.timeit(lambda: cross_product_loop(v3, v4), number=10000)
            t2 = timeit.timeit(lambda: cross_product_linalg(v3, v4), number=10000)
            print(f"  Loop:        {t1:.6f}s")
            print(f"  Inline:      {t2:.6f}s")
            print(f"  Speedup:     {t1/t2:.2f}x\n")
    
    print("=" * 70)
    print("SUMMARY: List comprehensions and built-in functions are faster")
    print("         than explicit loops due to optimized C implementations")
    print("=" * 70)

run_benchmarks()