Python 中的寻路效率
Path-finding efficiency in Python
我已经编写了一些代码来查找树突流网络中给定范围上游的所有路径。例如，如果我代表以下网络：
4 -- 5 -- 8
/
2 --- 6 - 9 -- 10
/ \
1 -- 11
\
3 ----7
作为一组父子对：
{(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
它将return节点上游的所有路径，例如：
get_paths(h, 1) # edited, had 11 instead of 1 in before
[[Reach(2), Reach(6), Reach(9), Reach(11)], [Reach(2), Reach(6), Reach(9), Reach(10)], [Reach(2), Reach(4), Reach(5), Reach(8)], [Reach(3), Reach(7)]]
下面包含代码。
我的问题是：我正在将此应用于非常大（例如，新英格兰）区域中的每个范围，其中任何给定的范围可能有数百万条路径。可能无法避免这是一个非常长的操作，但是是否有一种 pythonic 方式来执行此操作，以便每个 运行 都不会生成全新的路径？
比如我运行 get_paths(h, 2) 和2上游的所有路径都找到了，我以后可以运行 get_paths(h, 1) 不回溯 2 中的所有路径?
import collections
# Object representing a stream reach. Used to construct a hierarchy for accumulation function
class Reach(object):
def __init__(self):
self.name = None
self.ds = None
self.us = set()
def __repr__(self):
return "Reach({})".format(self.name)
def build_hierarchy(flows):
hierarchy = collections.defaultdict(lambda: Reach())
for reach_id, parent in flows:
if reach_id:
hierarchy[reach_id].name = reach_id
hierarchy[parent].name = parent
hierarchy[reach_id].ds = hierarchy[parent]
hierarchy[parent].us.add(hierarchy[reach_id])
return hierarchy
def get_paths(h, start_node):
def go_up(n):
if not h[n].us:
paths.append(current_path[:])
for us in h[n].us:
current_path.append(us)
go_up(us.name)
if current_path:
current_path.pop()
paths = []
current_path = []
go_up(start_node)
return paths
test_tree = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
h = build_hierarchy(test_tree)
p = get_paths(h, 1)
编辑：
几周前，我问了一个关于在网络中寻找 "ALL" 上游范围的类似问题，并很快得到了一个很好的答案：
class Node(object):
def __init__(self):
self.name = None
self.parent = None
self.children = set()
self._upstream = set()
def __repr__(self):
return "Node({})".format(self.name)
@property
def upstream(self):
if self._upstream:
return self._upstream
else:
for child in self.children:
self._upstream.add(child)
self._upstream |= child.upstream
return self._upstream
import collections
edges = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
nodes = collections.defaultdict(lambda: Node())
for node, parent in edges:
nodes[node].name = node
nodes[parent].name = parent
nodes[node].parent = nodes[parent]
nodes[parent].children.add(nodes[node])
我注意到这段代码的 def upstream(): 部分按顺序添加了上游节点，但是因为它是一个迭代功能 我找不到将它们附加到单个列表的好方法。也许有一种方法可以修改保留顺序的代码。
是的，你可以做到。我不完全确定你的限制是什么；但是，这应该会让您走上正轨。最坏情况 运行 的时间是 O(|E|+|V|)，唯一的区别是在 p.dfsh 中，我们正在缓存先前评估的路径，而不是 p.dfs，我们不是。
这将增加额外的 space 开销，因此请注意这种权衡 - 您将节省许多迭代（取决于您的数据集），但无论如何都会占用更多内存。不幸的是，缓存并没有提高增长的顺序，只有实用的 运行 时间：
points = set([
(11, 9),
(10, 9),
(9, 6),
(6, 2),
(8, 5),
(5, 4),
(4, 2),
(2, 1),
(3, 1),
(7, 3),
])
class PathFinder(object):
def __init__(self, points):
self.graph = self._make_graph(points)
self.hierarchy = {}
def _make_graph(self, points):
graph = {}
for p in points:
p0, p1 = p[0], p[1]
less, more = min(p), max(p)
if less not in graph:
graph[less] = set([more])
else:
graph[less].add(more)
return graph
def dfs(self, start):
visited = set()
stack = [start]
_count = 0
while stack:
_count += 1
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
if vertex in self.graph:
stack.extend(v for v in self.graph[vertex])
print "Start: {s} | Count: {c} |".format(c=_count, s=start),
return visited
def dfsh(self, start):
visited = set()
stack = [start]
_count = 0
while stack:
_count += 1
vertex = stack.pop()
if vertex not in visited:
if vertex in self.hierarchy:
visited.update(self.hierarchy[vertex])
else:
visited.add(vertex)
if vertex in self.graph:
stack.extend([v for v in self.graph[vertex]])
self.hierarchy[start] = visited
print "Start: {s} | Count: {c} |".format(c=_count, s=start),
return visited
p = PathFinder(points)
print p.dfsh(1)
print p.dfsh(2)
print p.dfsh(9)
print p.dfsh(6)
print p.dfsh(2)
print
print p.dfs(1)
print p.dfs(2)
print p.dfs(9)
print p.dfs(6)
print p.dfs(2)
p.dfsh 的输出如下：
Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
Start: 9 | Count: 3 | set([9, 10, 11])
Start: 6 | Count: 2 | set([9, 10, 11, 6])
Start: 2 | Count: 1 | set([2, 4, 5, 6, 8, 9, 10, 11])
常规 p.dfs 的输出是：
Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
Start: 9 | Count: 3 | set([9, 10, 11])
Start: 6 | Count: 4 | set([9, 10, 11, 6])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
如您所见，我进行了 DFS，但我会在合理范围内跟踪之前的迭代。我不想跟踪所有可能的先前路径，因为如果您在大型数据集上使用它，它会占用大量内存。
在输出中，您可以看到 p.dfsh(2) 的迭代计数从 8 变为 1。同样，由于先前计算 [=]，p.dfsh(6) 的计数也下降到 2 19=]。这是标准 DFS 的适度 运行 时间改进，尤其是在非常大的数据集上。
当然，假设您有足够的内存来存储来自每个节点的所有路径，您可以直接修改您在该答案中收到的代码：
class Reach(object):
def __init__(self):
self.name = None
self.ds = None
self.us = set()
self._paths = []
def __repr__(self):
return "Reach({})".format(self.name)
@property
def paths(self):
if not self._paths:
for child in self.us:
if child.paths:
self._paths.extend([child] + path for path in child.paths)
else:
self._paths.append([child])
return self._paths
请注意，对于大约 20,000 个范围，该方法所需的内存将以千兆字节为单位。假设通常平衡的河段树，所需内存为 O(n^2)，其中 n 是河段总数。根据您的系统，20,000 次到达需要 4-8 GiB。但是，在计算了来自 h[1] 的路径之后，任何节点所需的时间都是 O(1)。
我已经编写了一些代码来查找树突流网络中给定范围上游的所有路径。例如，如果我代表以下网络：
4 -- 5 -- 8
/
2 --- 6 - 9 -- 10
/ \
1 -- 11
\
3 ----7
作为一组父子对：
{(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
它将return节点上游的所有路径，例如：
get_paths(h, 1) # edited, had 11 instead of 1 in before
[[Reach(2), Reach(6), Reach(9), Reach(11)], [Reach(2), Reach(6), Reach(9), Reach(10)], [Reach(2), Reach(4), Reach(5), Reach(8)], [Reach(3), Reach(7)]]
下面包含代码。
我的问题是：我正在将此应用于非常大（例如，新英格兰）区域中的每个范围，其中任何给定的范围可能有数百万条路径。可能无法避免这是一个非常长的操作，但是是否有一种 pythonic 方式来执行此操作，以便每个 运行 都不会生成全新的路径？
比如我运行 get_paths(h, 2) 和2上游的所有路径都找到了，我以后可以运行 get_paths(h, 1) 不回溯 2 中的所有路径?
import collections
# Object representing a stream reach. Used to construct a hierarchy for accumulation function
class Reach(object):
def __init__(self):
self.name = None
self.ds = None
self.us = set()
def __repr__(self):
return "Reach({})".format(self.name)
def build_hierarchy(flows):
hierarchy = collections.defaultdict(lambda: Reach())
for reach_id, parent in flows:
if reach_id:
hierarchy[reach_id].name = reach_id
hierarchy[parent].name = parent
hierarchy[reach_id].ds = hierarchy[parent]
hierarchy[parent].us.add(hierarchy[reach_id])
return hierarchy
def get_paths(h, start_node):
def go_up(n):
if not h[n].us:
paths.append(current_path[:])
for us in h[n].us:
current_path.append(us)
go_up(us.name)
if current_path:
current_path.pop()
paths = []
current_path = []
go_up(start_node)
return paths
test_tree = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
h = build_hierarchy(test_tree)
p = get_paths(h, 1)
编辑： 几周前，我问了一个关于在网络中寻找 "ALL" 上游范围的类似问题，并很快得到了一个很好的答案：
class Node(object):
def __init__(self):
self.name = None
self.parent = None
self.children = set()
self._upstream = set()
def __repr__(self):
return "Node({})".format(self.name)
@property
def upstream(self):
if self._upstream:
return self._upstream
else:
for child in self.children:
self._upstream.add(child)
self._upstream |= child.upstream
return self._upstream
import collections
edges = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)}
nodes = collections.defaultdict(lambda: Node())
for node, parent in edges:
nodes[node].name = node
nodes[parent].name = parent
nodes[node].parent = nodes[parent]
nodes[parent].children.add(nodes[node])
我注意到这段代码的 def upstream(): 部分按顺序添加了上游节点，但是因为它是一个迭代功能 我找不到将它们附加到单个列表的好方法。也许有一种方法可以修改保留顺序的代码。
是的，你可以做到。我不完全确定你的限制是什么；但是，这应该会让您走上正轨。最坏情况 运行 的时间是 O(|E|+|V|)，唯一的区别是在 p.dfsh 中，我们正在缓存先前评估的路径，而不是 p.dfs，我们不是。
这将增加额外的 space 开销，因此请注意这种权衡 - 您将节省许多迭代（取决于您的数据集），但无论如何都会占用更多内存。不幸的是，缓存并没有提高增长的顺序，只有实用的 运行 时间：
points = set([
(11, 9),
(10, 9),
(9, 6),
(6, 2),
(8, 5),
(5, 4),
(4, 2),
(2, 1),
(3, 1),
(7, 3),
])
class PathFinder(object):
def __init__(self, points):
self.graph = self._make_graph(points)
self.hierarchy = {}
def _make_graph(self, points):
graph = {}
for p in points:
p0, p1 = p[0], p[1]
less, more = min(p), max(p)
if less not in graph:
graph[less] = set([more])
else:
graph[less].add(more)
return graph
def dfs(self, start):
visited = set()
stack = [start]
_count = 0
while stack:
_count += 1
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
if vertex in self.graph:
stack.extend(v for v in self.graph[vertex])
print "Start: {s} | Count: {c} |".format(c=_count, s=start),
return visited
def dfsh(self, start):
visited = set()
stack = [start]
_count = 0
while stack:
_count += 1
vertex = stack.pop()
if vertex not in visited:
if vertex in self.hierarchy:
visited.update(self.hierarchy[vertex])
else:
visited.add(vertex)
if vertex in self.graph:
stack.extend([v for v in self.graph[vertex]])
self.hierarchy[start] = visited
print "Start: {s} | Count: {c} |".format(c=_count, s=start),
return visited
p = PathFinder(points)
print p.dfsh(1)
print p.dfsh(2)
print p.dfsh(9)
print p.dfsh(6)
print p.dfsh(2)
print
print p.dfs(1)
print p.dfs(2)
print p.dfs(9)
print p.dfs(6)
print p.dfs(2)
p.dfsh 的输出如下：
Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
Start: 9 | Count: 3 | set([9, 10, 11])
Start: 6 | Count: 2 | set([9, 10, 11, 6])
Start: 2 | Count: 1 | set([2, 4, 5, 6, 8, 9, 10, 11])
常规 p.dfs 的输出是：
Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
Start: 9 | Count: 3 | set([9, 10, 11])
Start: 6 | Count: 4 | set([9, 10, 11, 6])
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11])
如您所见，我进行了 DFS，但我会在合理范围内跟踪之前的迭代。我不想跟踪所有可能的先前路径，因为如果您在大型数据集上使用它，它会占用大量内存。
在输出中，您可以看到 p.dfsh(2) 的迭代计数从 8 变为 1。同样，由于先前计算 [=]，p.dfsh(6) 的计数也下降到 2 19=]。这是标准 DFS 的适度 运行 时间改进，尤其是在非常大的数据集上。
当然，假设您有足够的内存来存储来自每个节点的所有路径，您可以直接修改您在该答案中收到的代码：
class Reach(object):
def __init__(self):
self.name = None
self.ds = None
self.us = set()
self._paths = []
def __repr__(self):
return "Reach({})".format(self.name)
@property
def paths(self):
if not self._paths:
for child in self.us:
if child.paths:
self._paths.extend([child] + path for path in child.paths)
else:
self._paths.append([child])
return self._paths
请注意，对于大约 20,000 个范围，该方法所需的内存将以千兆字节为单位。假设通常平衡的河段树，所需内存为 O(n^2)，其中 n 是河段总数。根据您的系统，20,000 次到达需要 4-8 GiB。但是，在计算了来自 h[1] 的路径之后，任何节点所需的时间都是 O(1)。