Spaces:
Runtime error
Runtime error
File size: 5,859 Bytes
bd86de0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | """
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,
}
|