algorithms/benchmark.py

"""
USSU Algorithm Analyzer v4.0 - Benchmark & Speed Analysis Suite
Cross-size performance suites with cyberpunk visualization data.
"""
import time
import random
import math
from typing import List, Dict, Any, Optional
from utils.core import Graph
from algorithms.search import SearchingAlgorithms
from algorithms.sort import SortingAlgorithms
from algorithms.graph import GraphAlgorithms
from algorithms.dp import DynamicProgramming
from algorithms.greedy import GreedyAlgorithms


class BenchmarkSuite:
    """Advanced benchmarking and speed analysis suite"""

    def __init__(self):
        self.results = []

    def benchmark_search(self, sizes: List[int] = None, trials: int = 5) -> List[Dict]:
        if sizes is None:
            sizes = [100, 1000, 5000, 10000]
        searcher = SearchingAlgorithms()
        all_results = []

        for size in sizes:
            arr = sorted(random.sample(range(size * 2), size))
            target = random.choice(arr)
            algorithms = [
                ('Linear Search', lambda a, t: searcher.linear_search(a, t)),
                ('Binary Search', lambda a, t: searcher.binary_search_iterative(a, t)),
                ('Jump Search', lambda a, t: searcher.jump_search(a, t)),
                ('Interpolation', lambda a, t: searcher.interpolation_search(a, t)),
                ('Exponential', lambda a, t: searcher.exponential_search(a, t)),
            ]
            size_results = {'size': size, 'times': {}}
            for name, algo in algorithms:
                # Warmup
                algo(arr.copy(), target)
                times = []
                for _ in range(trials):
                    start = time.perf_counter()
                    algo(arr.copy(), target)
                    times.append((time.perf_counter() - start) * 1000)
                size_results['times'][name] = sum(times) / len(times)
            all_results.append(size_results)
        return all_results

    def benchmark_sort(self, sizes: List[int] = None, trials: int = 3) -> List[Dict]:
        if sizes is None:
            sizes = [100, 500, 1000, 2000]
        sorter = SortingAlgorithms()
        all_results = []

        for size in sizes:
            arr = [random.randint(0, size) for _ in range(size)]
            algorithms = [
                ('Bubble', sorter.bubble_sort),
                ('Insertion', sorter.insertion_sort),
                ('Merge', sorter.merge_sort),
                ('Quick', sorter.quick_sort),
                ('Heap', sorter.heap_sort),
                ('Shell', sorter.shell_sort),
                ('Timsort', sorter.tim_sort),
            ]
            size_results = {'size': size, 'times': {}}
            for name, algo in algorithms:
                if size > 2000 and name in ['Bubble', 'Insertion']:
                    size_results['times'][name] = float('inf')
                    continue
                test_arr = arr.copy()
                start = time.perf_counter()
                algo(test_arr)
                size_results['times'][name] = (time.perf_counter() - start) * 1000
            all_results.append(size_results)
        return all_results

    def benchmark_graph(self, sizes: List[int] = None) -> List[Dict]:
        if sizes is None:
            sizes = [10, 20, 50, 100]
        grapher = GraphAlgorithms()
        all_results = []

        for size in sizes:
            g = Graph.from_random(size, edge_prob=0.2, weighted=True)
            start = time.perf_counter()
            grapher.dijkstra(g, 0)
            dij_time = (time.perf_counter() - start) * 1000

            start = time.perf_counter()
            grapher.bfs(g, 0)
            bfs_time = (time.perf_counter() - start) * 1000

            start = time.perf_counter()
            grapher.dfs_iterative(g, 0)
            dfs_time = (time.perf_counter() - start) * 1000

            all_results.append({
                'size': size,
                'dijkstra': dij_time,
                'bfs': bfs_time,
                'dfs': dfs_time,
            })
        return all_results

    def benchmark_dp(self, sizes: List[int] = None) -> List[Dict]:
        if sizes is None:
            sizes = [5, 10, 15, 20]
        dp = DynamicProgramming()
        all_results = []

        for size in sizes:
            weights = [random.randint(1, 20) for _ in range(size)]
            values = [random.randint(10, 100) for _ in range(size)]
            capacity = sum(weights) // 2

            start = time.perf_counter()
            dp.knapsack_01(weights, values, capacity)
            knap_time = (time.perf_counter() - start) * 1000

            s1 = ''.join(random.choices('ABCDEFGHIJ', k=size))
            s2 = ''.join(random.choices('ABCDEFGHIJ', k=size))
            start = time.perf_counter()
            dp.lcs(s1, s2)
            lcs_time = (time.perf_counter() - start) * 1000

            all_results.append({
                'size': size,
                'knapsack': knap_time,
                'lcs': lcs_time,
            })
        return all_results

    def speed_profile(self, algo_func, *args, warmup: int = 2, trials: int = 10) -> Dict:
        """Detailed speed profiling of a single algorithm"""
        for _ in range(warmup):
            algo_func(*args)

        times = []
        for _ in range(trials):
            start = time.perf_counter()
            result = algo_func(*args)
            elapsed = (time.perf_counter() - start) * 1000
            times.append(elapsed)

        times.sort()
        return {
            'trials': trials,
            'min_ms': min(times),
            'max_ms': max(times),
            'mean_ms': sum(times) / len(times),
            'median_ms': times[len(times)//2],
            'std_ms': (sum((t - sum(times)/len(times))**2 for t in times) / len(times)) ** 0.5,
            'all_times': times,
        }