«

En Wed, 16 May 2007 00:39:20 -0300, Hugo Ferreira <>
escribió:

> While trying to optimize this:
>
> http://aspn.activestate.com/ASPN/Coo.../Recipe/119466
>
> ... and still have a fast edge lookup, I've done the following tweaks:

I've replaced that strange deeply nested list with an old-fashioned tuple
and got about a 10% improvement (over a small graph, 60 nodes). But you
really should try the effect with larger objects.

def findPath(self, start, end):
q = [(0, start, ())] # Heap of (cost, path_head, path_rest).
visited = set() # Visited vertices.

# Eliminate the dots pattern
push, pop, add = heapq.heappush, heapq.heappop, visited.add
G, E = self.G, self.E

while True:
(cost, v1, path) = pop(q)
if v1 not in visited:
add(v1)
path += (v1,)

if v1 == end: return path

for (v2, e) in G[v1].iteritems():
if v2 not in visited:
push(q, (cost + E[e], v2, path))

--
Gabriel Genellina