This is an automated email from the ASF dual-hosted git repository.
skrawcz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/hamilton.git
The following commit(s) were added to refs/heads/main by this push:
new 072c40ce perf: use deque for BFS queue in graph traversal (#1494)
072c40ce is described below
commit 072c40ce3fbfd370cca783d44960fb7798b9ac6a
Author: Giulio Leone <[email protected]>
AuthorDate: Sun Mar 1 07:59:42 2026 +0100
perf: use deque for BFS queue in graph traversal (#1494)
* perf: use deque for BFS queue in graph traversal
compute_nodes_from_sources() drains a BFS queue via .pop(0) which is
O(n) per removal. Switch to collections.deque with .popleft() for
O(1) front removal.
* fix: sort imports per ruff I001
---
hamilton/execution/graph_functions.py | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/hamilton/execution/graph_functions.py
b/hamilton/execution/graph_functions.py
index d94551ea..0fbb3cb2 100644
--- a/hamilton/execution/graph_functions.py
+++ b/hamilton/execution/graph_functions.py
@@ -17,6 +17,7 @@
import logging
import pprint
+from collections import deque
from collections.abc import Collection
from functools import partial
from typing import Any
@@ -65,12 +66,12 @@ def topologically_sort_nodes(nodes: list[node.Node]) ->
list[node.Node]:
in_degrees = {node_.name: len(dependency_map.get(node_.name, [])) for
node_ in nodes}
# TODO -- determine what happens if nodes have dependencies that aren't
present
sources = [node_ for node_ in nodes if in_degrees[node_.name] == 0]
- queue = []
+ queue = deque()
for source in sources:
queue.append(source)
sorted_nodes = []
while len(queue) > 0:
- node_ = queue.pop(0)
+ node_ = queue.popleft()
sorted_nodes.append(node_)
for next_node in depended_on_by_map.get(node_.name, []):
if next_node.name in in_degrees:
