commit 2024abd1274376f4ef61716eac202e1ececcc084
parent 68ab63038f2a64ae671e7915e91bb8355e5167e4
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 16:20:04 -0500
Added some full benchmarking
Diffstat:
7 files changed, 286 insertions(+), 0 deletions(-)
diff --git a/graph/benchmarking/no_render_1_itr/bench.sh b/graph/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/graph/benchmarking/no_render_1_itr/out b/graph/benchmarking/no_render_1_itr/out
diff --git a/graph/benchmarking/no_render_1_itr/prim.py b/graph/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/graph/benchmarking/no_render_1_itr/v10000e100000nosc b/graph/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/graph/benchmarking/render_1_itr/bench.sh b/graph/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/graph/benchmarking/render_1_itr/prim.py b/graph/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/graph/benchmarking/render_1_itr/v1000e10000nosc b/graph/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
