commit 43a5346eeccd509892acdd67251bdefa739026f0 parent 340a6627d52a77923c71aacc92db0d378dd18dd9 Author: Andrew Laack <andrew@laack.co> Date: Fri, 18 Sep 2026 00:51:48 -0500 Python benchmark info Diffstat:
26 files changed, 1036 insertions(+), 0 deletions(-)
diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/bench.sh b/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/bench.sh @@ -0,0 +1,4 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v10000e100000nosc +done diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/info.txt b/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/info.txt @@ -0,0 +1 @@ +this has a copying issue where k1 = random.choice... which creates an array every iteration, bunch of copies. not good. diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/out b/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/out diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/prim.py b/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/prim.py @@ -0,0 +1,80 @@ +import heapq +import random +import math + +VERTICES = 10000 +EDGES = 100000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(list(graph.keys())) + k2 = random.choice(list(graph.keys())) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + +mst = [] + +start = random.choice(list(graph.keys())) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + +while True: + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + mst.append(item) + for edge in graph[new_vertex]: + heapq.heappush(edge_heap, edge) diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/v10000e100000nosc b/assets/abg/benchmarking-python/benchmarking/no_render_1_itr/v10000e100000nosc @@ -0,0 +1,38 @@ +system,user,wall +0.00,5.26,5.27 +0.00,5.25,5.27 +0.00,5.31,5.32 +0.00,5.17,5.19 +0.00,5.45,5.46 +0.01,5.22,5.24 +0.01,5.20,5.22 +0.00,5.27,5.28 +0.01,5.51,5.53 +0.01,5.68,5.70 +0.00,5.64,5.66 +0.01,5.78,5.80 +0.01,5.53,5.56 +0.00,5.53,5.54 +0.00,5.64,5.65 +0.01,5.62,5.65 +0.01,5.72,5.75 +0.01,5.62,5.64 +0.00,5.75,5.76 +0.00,5.74,5.76 +0.01,5.60,5.62 +0.01,5.66,5.68 +0.01,5.64,5.66 +0.01,5.64,5.66 +0.01,5.59,5.61 +0.00,5.50,5.51 +0.00,5.69,5.70 +0.01,5.54,5.57 +0.01,5.59,5.62 +0.01,5.72,5.74 +0.01,5.61,5.64 +0.00,5.52,5.54 +0.01,5.64,5.66 +0.01,5.57,5.60 +0.00,5.60,5.62 +0.01,5.63,5.65 +0.01,5.59,5.61 diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/bench.sh b/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v100000e1000000nosc + sleep 1 +done diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/out b/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/out @@ -0,0 +1,2 @@ +Command terminated by signal 2 +0.08,10.23,10.35 diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/prim.py b/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/prim.py @@ -0,0 +1,82 @@ +import heapq +import random +import math + +VERTICES = 100000 +EDGES = 1000000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + +mst = [] + +start = random.choice(list(graph.keys())) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + +while True: + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + mst.append(item) + for edge in graph[new_vertex]: + heapq.heappush(edge_heap, edge) diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc b/assets/abg/benchmarking-python/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc @@ -0,0 +1,208 @@ +0.06,12.10,12.21 +0.08,12.22,12.35 +0.08,12.16,12.29 +0.09,12.00,12.13 +0.09,11.89,12.02 +0.06,11.92,12.01 +0.06,11.87,11.97 +0.06,12.07,12.16 +0.08,11.84,11.98 +0.07,11.87,12.02 +0.06,11.80,11.89 +0.09,11.84,11.96 +0.07,11.86,11.97 +0.07,11.93,12.04 +0.07,11.97,12.10 +0.07,12.02,12.13 +0.05,12.01,12.11 +0.06,11.80,11.90 +0.06,11.71,11.82 +0.08,11.99,12.11 +0.06,12.02,12.12 +0.06,12.00,12.11 +0.07,11.95,12.06 +0.06,12.08,12.18 +0.07,11.81,11.92 +0.08,12.00,12.12 +0.06,11.88,11.98 +0.06,11.96,12.07 +0.06,11.99,12.09 +0.07,11.84,11.97 +0.07,11.99,12.10 +0.06,12.05,12.15 +0.08,11.91,12.03 +0.08,11.81,11.93 +0.08,11.83,11.94 +0.07,11.87,12.01 +0.07,11.80,11.94 +0.08,12.11,12.24 +0.08,11.87,12.00 +0.07,11.85,11.96 +0.07,11.97,12.08 +0.06,12.10,12.20 +0.06,11.86,11.96 +0.06,11.88,11.98 +0.07,11.95,12.06 +0.07,11.88,11.98 +0.07,11.85,11.97 +0.06,11.86,11.97 +0.08,11.98,12.10 +0.07,11.79,11.90 +0.07,12.03,12.16 +0.06,11.86,11.97 +0.06,11.94,12.03 +0.06,11.91,12.01 +0.06,11.96,12.06 +0.06,12.13,12.22 +0.07,12.00,12.11 +0.06,12.00,12.10 +0.07,12.02,12.14 +0.06,11.85,11.95 +0.08,11.94,12.06 +0.08,11.76,11.88 +0.07,11.89,12.00 +0.05,12.06,12.15 +0.07,11.94,12.05 +0.06,11.92,12.02 +0.08,11.85,11.97 +0.07,11.93,12.06 +0.08,11.75,11.87 +0.06,11.75,11.86 +0.07,11.89,11.99 +0.06,11.89,12.02 +0.06,11.81,11.93 +0.07,11.82,11.93 +0.07,12.03,12.14 +0.06,11.84,11.94 +0.08,12.22,12.34 +0.07,11.89,12.00 +0.08,12.03,12.14 +0.07,12.06,12.17 +0.08,11.74,11.86 +0.07,11.90,12.01 +0.06,11.82,11.93 +0.08,11.84,11.96 +0.07,11.78,11.88 +0.08,12.31,12.44 +0.08,11.87,11.99 +0.08,12.04,12.17 +0.06,12.02,12.12 +0.08,11.85,11.96 +0.05,11.93,12.03 +0.07,11.67,11.79 +0.07,11.82,11.92 +0.08,11.83,11.95 +0.07,11.86,11.97 +0.06,11.98,12.10 +0.07,12.05,12.16 +0.07,11.84,11.94 +0.07,11.91,12.02 +0.07,11.88,11.99 +0.07,11.89,12.00 +0.07,11.94,12.06 +0.07,11.84,11.95 +0.07,11.88,11.99 +0.08,11.85,11.98 +0.07,11.99,12.10 +0.08,11.85,11.97 +0.07,12.12,12.23 +0.08,11.86,11.98 +0.08,11.89,12.00 +0.07,12.05,12.15 +0.07,11.89,11.99 +0.07,11.93,12.05 +0.07,11.82,11.94 +0.06,11.94,12.05 +0.07,11.86,11.98 +0.07,11.76,11.87 +0.07,11.96,12.07 +0.07,11.89,12.00 +0.07,12.16,12.27 +0.07,11.91,12.02 +0.07,11.83,11.94 +0.05,11.85,11.94 +0.07,11.92,12.03 +0.06,11.79,11.90 +0.07,11.76,11.87 +0.07,11.92,12.03 +0.06,11.86,11.96 +0.07,11.81,11.93 +0.07,11.90,12.01 +0.07,11.89,12.00 +0.07,11.91,12.02 +0.07,11.87,11.98 +0.08,11.87,11.99 +0.07,11.83,11.96 +0.06,11.88,11.99 +0.07,11.79,11.90 +0.06,11.84,11.95 +0.06,11.85,11.96 +0.06,11.83,11.95 +0.07,11.85,11.99 +0.07,11.94,12.05 +0.05,11.97,12.07 +0.07,11.90,12.01 +0.06,11.93,12.03 +0.07,11.89,12.00 +0.06,11.91,12.01 +0.06,11.83,11.93 +0.06,11.92,12.02 +0.05,11.88,11.97 +0.08,11.91,12.03 +0.07,11.89,12.00 +0.07,11.83,11.95 +0.09,11.89,12.02 +0.07,11.85,11.97 +0.06,11.82,11.92 +0.07,11.85,11.96 +0.06,11.98,12.08 +0.07,11.79,11.93 +0.07,12.01,12.12 +0.08,11.87,12.01 +0.06,11.85,11.98 +0.07,11.76,11.89 +0.06,11.86,11.97 +0.07,11.88,11.99 +0.08,11.79,11.94 +0.07,11.81,11.96 +0.07,11.90,12.01 +0.06,11.84,11.97 +0.08,11.83,11.98 +0.07,11.93,12.07 +0.07,11.84,11.99 +0.07,11.82,11.94 +0.07,11.96,12.09 +0.07,11.84,11.95 +0.08,11.94,12.09 +0.06,11.83,11.94 +0.06,11.90,12.00 +0.06,11.87,11.98 +0.06,12.04,12.14 +0.05,12.01,12.13 +0.07,11.84,11.98 +0.06,11.80,11.93 +0.05,11.89,12.02 +0.06,11.84,11.94 +0.06,12.11,12.21 +0.06,12.06,12.17 +0.07,11.76,11.89 +0.07,11.93,12.07 +0.08,11.91,12.03 +0.07,11.85,11.96 +0.07,11.95,12.06 +0.09,12.01,12.13 +0.06,11.97,12.07 +0.06,11.97,12.07 +0.07,11.86,11.97 +0.06,11.84,11.94 +0.07,11.98,12.09 +0.07,11.93,12.04 +0.07,12.19,12.30 +0.06,11.88,11.98 +0.07,11.88,11.99 +0.07,11.90,12.00 +0.06,11.99,12.10 +0.06,11.85,11.95 +0.07,11.93,12.04 +0.07,11.96,12.07 +0.07,11.86,11.97 diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh b/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v100000e1000000nosc + sleep 1 +done diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/out b/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/out @@ -0,0 +1 @@ +0.06,8.36,8.48 diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py b/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py @@ -0,0 +1,83 @@ +import heapq +import random +import math + +VERTICES = 100000 +EDGES = 1000000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + +mst = [] + +start = random.choice(list(graph.keys())) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + +while True: + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + mst.append(item) + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc b/assets/abg/benchmarking-python/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc @@ -0,0 +1,6 @@ +0.06,8.38,8.47 +0.06,8.39,8.48 +0.06,8.47,8.60 +0.07,8.52,8.63 +0.06,8.35,8.44 +0.06,8.36,8.48 diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_final/bench.sh b/assets/abg/benchmarking-python/benchmarking/no_render_final/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v200000e2000000 + sleep 1 +done diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_final/prim.py b/assets/abg/benchmarking-python/benchmarking/no_render_final/prim.py @@ -0,0 +1,90 @@ +import heapq +import random +import math + +VERTICES = 200_000 +EDGES = 2_000_000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + + +start = random.choice(keys) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + +first = True + +# we still have this for consistency with the c++ variant because the c++ variant is also tracking this info. +to_draw_vert = [] +to_draw_edge = [] + +while True: + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) diff --git a/assets/abg/benchmarking-python/benchmarking/no_render_final/v200000e2000000 b/assets/abg/benchmarking-python/benchmarking/no_render_final/v200000e2000000 @@ -0,0 +1,6 @@ +0.12,19.95,20.18 +0.11,19.83,20.01 +0.12,20.17,20.36 +0.13,20.10,20.30 +0.13,20.12,20.33 +0.11,20.15,20.34 diff --git a/assets/abg/benchmarking-python/benchmarking/render_1_itr/bench.sh b/assets/abg/benchmarking-python/benchmarking/render_1_itr/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v1000e10000nosc + sleep 10 +done diff --git a/assets/abg/benchmarking-python/benchmarking/render_1_itr/prim.py b/assets/abg/benchmarking-python/benchmarking/render_1_itr/prim.py @@ -0,0 +1,116 @@ +import pygame +import heapq +import random +import math + +pygame.init() + +display = pygame.display.set_mode((5120,1440)) + +VERTICES = 1000 +EDGES = 10000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + + def draw_vertex(self,display): + if self.visited: + pygame.draw.circle(display, white, (self.x,self.y), 5) + else: + pygame.draw.circle(display, grey, (self.x,self.y), 5) + +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + + def draw_edge(self,display, c): + pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(list(graph.keys())) + k2 = random.choice(list(graph.keys())) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + +mst = [] + +start = random.choice(list(graph.keys())) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + +while True: + for event in pygame.event.get(): + if event.type == pygame.QUIT: + pygame.quit() + quit() + + display.fill(black) + for edge in edge_list: + edge.draw_edge(display, light_grey) + for edge in mst: + edge.draw_edge(display, white) + for vertex in graph: + vertex.draw_vertex(display) + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + pygame.display.update() + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + mst.append(item) + for edge in graph[new_vertex]: + heapq.heappush(edge_heap, edge) + + #dir_name = "/dev/shm/bg/" + #if not os.path.exists(dir_name): + # os.mkdir(dir_name) + #pygame.image.save(display, dir_name + "out.png") + #os.system("/usr/bin/feh --no-fehbg --bg-tile '/dev/shm/bg/out.png' ") + #time.sleep(.1) + pygame.display.update() diff --git a/assets/abg/benchmarking-python/benchmarking/render_1_itr/v1000e10000nosc b/assets/abg/benchmarking-python/benchmarking/render_1_itr/v1000e10000nosc @@ -0,0 +1,43 @@ +system,user,wall +0.15,101.47,101.33 +0.18,103.93,103.92 +0.19,106.28,106.26 +0.18,103.27,103.16 +0.17,105.34,105.25 +0.17,104.35,104.26 +0.21,105.54,105.59 +0.18,105.43,105.39 +0.19,104.71,104.67 +0.16,104.19,104.08 +0.17,105.10,105.00 +0.17,107.76,107.66 +0.18,103.39,103.29 +0.17,105.66,105.66 +0.18,107.11,107.03 +0.18,104.47,104.42 +0.17,104.11,104.01 +0.18,102.00,101.95 +0.16,101.21,101.10 +0.20,101.21,101.14 +0.17,103.84,103.74 +0.19,106.28,106.25 +0.18,102.96,102.89 +0.18,103.79,103.70 +0.17,106.01,105.94 +0.19,105.63,105.63 +0.18,107.66,107.59 +0.20,105.48,105.49 +0.18,108.72,108.65 +0.17,102.09,101.99 +0.17,104.53,104.42 +0.16,105.52,105.41 +0.18,107.20,107.13 +0.20,104.25,104.24 +0.17,105.09,105.03 +0.18,102.54,102.46 +0.19,106.56,106.50 +0.18,106.23,106.15 +0.16,105.62,105.50 +0.21,104.78,104.85 +0.19,102.27,102.23 +0.17,105.98,105.87 diff --git a/assets/abg/benchmarking-python/benchmarking/render_final/bench.sh b/assets/abg/benchmarking-python/benchmarking/render_final/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v10000e100000 + sleep 1 +done diff --git a/assets/abg/benchmarking-python/benchmarking/render_final/prim.py b/assets/abg/benchmarking-python/benchmarking/render_final/prim.py @@ -0,0 +1,128 @@ +import pygame +import heapq +import random +import math + +pygame.init() + +display = pygame.display.set_mode((5120,1440)) + +VERTICES = 10000 +EDGES = 100000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self,display): + if self.visited: + pygame.draw.circle(display, white, (self.x,self.y), 5) + else: + pygame.draw.circle(display, grey, (self.x,self.y), 5) +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self,display, c): + pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + + +start = random.choice(keys) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + +first = True + +to_draw_vert = [] +to_draw_edge = [] + +while True: + for event in pygame.event.get(): + if event.type == pygame.QUIT: + pygame.quit() + quit() + + if first: + display.fill(black) + + for edge in edge_list: + edge.draw_edge(display, light_grey) + first = False + + for vertex in graph: + vertex.draw_vertex(display) + + for edge in to_draw_edge: + edge.draw_edge(display, white) + for vert in to_draw_vert: + vert.draw_vertex(display) + + to_draw_vert = [] + to_draw_edge = [] + + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + + pygame.display.update() diff --git a/assets/abg/benchmarking-python/benchmarking/render_final/v10000e100000 b/assets/abg/benchmarking-python/benchmarking/render_final/v10000e100000 @@ -0,0 +1,5 @@ +1.49,52.97,59.67 +1.35,53.08,59.09 +1.37,52.48,58.43 +1.32,52.55,58.51 +1.29,52.14,58.09 diff --git a/assets/abg/benchmarking-python/benchmarking/render_fixed/bench.sh b/assets/abg/benchmarking-python/benchmarking/render_fixed/bench.sh @@ -0,0 +1,5 @@ +while [ 1 ]; do + /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1 + cat out | tee -a v_10000_e_100000 + sleep 1 +done diff --git a/assets/abg/benchmarking-python/benchmarking/render_fixed/out b/assets/abg/benchmarking-python/benchmarking/render_fixed/out @@ -0,0 +1,2 @@ +Command terminated by signal 2 +0.07,3.66,3.09 diff --git a/assets/abg/benchmarking-python/benchmarking/render_fixed/prim.py b/assets/abg/benchmarking-python/benchmarking/render_fixed/prim.py @@ -0,0 +1,110 @@ +import pygame +import heapq +import random +import math + +pygame.init() + +display = pygame.display.set_mode((5120,1440)) + + +VERTICES = 10000 +EDGES = 100000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self,display): + if self.visited: + pygame.draw.circle(display, white, (self.x,self.y), 5) + else: + pygame.draw.circle(display, grey, (self.x,self.y), 5) +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self,display, c): + pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + +mst = [] + +start = random.choice(list(graph.keys())) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + +while True: + for event in pygame.event.get(): + if event.type == pygame.QUIT: + pygame.quit() + quit() + + + display.fill(black) + for edge in edge_list: + edge.draw_edge(display, light_grey) + for edge in mst: + edge.draw_edge(display, white) + for vertex in graph: + vertex.draw_vertex(display) + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + mst.append(item) + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + pygame.display.update() diff --git a/assets/abg/benchmarking-python/benchmarking/render_fixed/v_10000_e_100000 b/assets/abg/benchmarking-python/benchmarking/render_fixed/v_10000_e_100000 @@ -0,0 +1 @@ +1.33,10730.71,10772.74