commit 328a47a49ee9f27a9b7ccabcec4e387f3f6cc1a2 parent 62466026a1596e0211ac75417647a2392e37d542 Author: Andrew Laack <andrew@laack.co> Date: Fri, 18 Sep 2026 00:52:11 -0500 Moved benchmarking code Diffstat:
26 files changed, 0 insertions(+), 1036 deletions(-)
diff --git a/graph/benchmarking/no_render_1_itr/bench.sh b/graph/benchmarking/no_render_1_itr/bench.sh @@ -1,4 +0,0 @@ -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/info.txt b/graph/benchmarking/no_render_1_itr/info.txt @@ -1 +0,0 @@ -this has a copying issue where k1 = random.choice... which creates an array every iteration, bunch of copies. not good. 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 @@ -1,80 +0,0 @@ -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 @@ -1,38 +0,0 @@ -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/no_render_2_fixed_itr/bench.sh b/graph/benchmarking/no_render_2_fixed_itr/bench.sh @@ -1,5 +0,0 @@ -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/graph/benchmarking/no_render_2_fixed_itr/out b/graph/benchmarking/no_render_2_fixed_itr/out @@ -1,2 +0,0 @@ -Command terminated by signal 2 -0.08,10.23,10.35 diff --git a/graph/benchmarking/no_render_2_fixed_itr/prim.py b/graph/benchmarking/no_render_2_fixed_itr/prim.py @@ -1,82 +0,0 @@ -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/graph/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc b/graph/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc @@ -1,208 +0,0 @@ -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/graph/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/bench.sh @@ -1,5 +0,0 @@ -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/graph/benchmarking/no_render_3_fixed_itr_fixed_check/out b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/out @@ -1 +0,0 @@ -0.06,8.36,8.48 diff --git a/graph/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/prim.py @@ -1,83 +0,0 @@ -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/graph/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc b/graph/benchmarking/no_render_3_fixed_itr_fixed_check/v100000e1000000nosc @@ -1,6 +0,0 @@ -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/graph/benchmarking/no_render_final/bench.sh b/graph/benchmarking/no_render_final/bench.sh @@ -1,5 +0,0 @@ -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/graph/benchmarking/no_render_final/prim.py b/graph/benchmarking/no_render_final/prim.py @@ -1,90 +0,0 @@ -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/graph/benchmarking/no_render_final/v200000e2000000 b/graph/benchmarking/no_render_final/v200000e2000000 @@ -1,6 +0,0 @@ -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/graph/benchmarking/render_1_itr/bench.sh b/graph/benchmarking/render_1_itr/bench.sh @@ -1,5 +0,0 @@ -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 @@ -1,116 +0,0 @@ -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 @@ -1,43 +0,0 @@ -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/graph/benchmarking/render_final/bench.sh b/graph/benchmarking/render_final/bench.sh @@ -1,5 +0,0 @@ -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/graph/benchmarking/render_final/prim.py b/graph/benchmarking/render_final/prim.py @@ -1,128 +0,0 @@ -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/graph/benchmarking/render_final/v10000e100000 b/graph/benchmarking/render_final/v10000e100000 @@ -1,5 +0,0 @@ -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/graph/benchmarking/render_fixed/bench.sh b/graph/benchmarking/render_fixed/bench.sh @@ -1,5 +0,0 @@ -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/graph/benchmarking/render_fixed/out b/graph/benchmarking/render_fixed/out @@ -1,2 +0,0 @@ -Command terminated by signal 2 -0.07,3.66,3.09 diff --git a/graph/benchmarking/render_fixed/prim.py b/graph/benchmarking/render_fixed/prim.py @@ -1,110 +0,0 @@ -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/graph/benchmarking/render_fixed/v_10000_e_100000 b/graph/benchmarking/render_fixed/v_10000_e_100000 @@ -1 +0,0 @@ -1.33,10730.71,10772.74