En Wed, 16 May 2007 00:39:20 -0300, Hugo Ferreira <[EMAIL PROTECTED]> escribió:
> While trying to optimize this: > > http://aspn.activestate.com/ASPN/Cookbook/Python/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 -- http://mail.python.org/mailman/listinfo/python-list