From 87c791bee874ff132017c31f464a854bf8ea8817 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 20 Nov 2020 18:30:29 +0100 Subject: initial timing --- algorithms.py | 7 +++++++ store.py | 4 ++++ 2 files changed, 11 insertions(+) diff --git a/algorithms.py b/algorithms.py index 6e01287..d0988ee 100644 --- a/algorithms.py +++ b/algorithms.py @@ -1,5 +1,6 @@ import heapq import math +import time def length_haversine(p1, p2): @@ -22,12 +23,15 @@ def get_closest_node_id(nodes, source_node): min_node = None min_value = None + start = time.monotonic() + for node_id, node in nodes.items(): length = length_haversine(source_node, node) if min_node is None or length < min_value: min_node = node_id min_value = length + print(f"Found the closest node in {time.monotonic() - start} s") return min_node @@ -39,12 +43,15 @@ def find_shortest_path(nodes, source_id, target_id): queue = [(0, (source_id,))] visited = set() + start = time.monotonic() + while queue: # consider an unchecked walk walk_dist, walk = heapq.heappop(queue) walk_end = walk[-1] if walk_end == target_id: # you have reached your destination + print(f"Found a path in {time.monotonic() - start} s") return walk if walk_end in visited: # there exists a shorter walk to walk_end diff --git a/store.py b/store.py index 9e6d4f7..ba2e4ef 100644 --- a/store.py +++ b/store.py @@ -1,3 +1,4 @@ +import time from osm_parser import get_default_parser @@ -38,6 +39,8 @@ def extract_osm_nodes(f_name): parser = get_default_parser(f_name) nodes = dict() + start = time.monotonic() + for node in parser.iter_nodes(): nodes[node['id']] = Node(node['id'], node['lat'], node['lon']) @@ -48,6 +51,7 @@ def extract_osm_nodes(f_name): if not node.neighbours: del nodes[node_id] + print(f"Extracted {len(nodes)} nodes in {time.monotonic() - start} s") return nodes -- cgit v1.2.1