Rev 4412: A new recursive gdfo processing method. in file:///home/vila/src/bzr/reviews/vila-better-heads/

[Vincent Ladeuil]

At file:///home/vila/src/bzr/reviews/vila-better-heads/

------------------------------------------------------------
revno: 4412
revision-id: v.ladeuil+lp at free.fr-20090616093753-ihx32neot2jqhqqn
parent: john at arbash-meinel.com-20090612202108-blsyks1kdxod0lsk
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Tue 2009-06-16 11:37:53 +0200
message:
  A new recursive gdfo processing method.
  
  * bzrlib/_known_graph_py.py:
  (KnownGraph._find_gdfo): A new version in O(n) processing each
  node only once.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-06-12 20:21:08 +0000
+++ b/bzrlib/_known_graph_py.py	2009-06-16 09:37:53 +0000
@@ -147,6 +147,28 @@
                 node = next_node
 
     def _find_gdfo(self):
+        nodes = self._nodes
+        pending = []
+        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
+
+        def update_childs(node):
+            for child_key in node.child_keys:
+                child = nodes[child_key]
+                known_parent_gdfos[child_key] += 1
+                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
+                    child.gdfo = node.gdfo + 1
+                if known_parent_gdfos[child_key] == len(child.parent_keys):
+                    # We are the last parent updating that node, we can
+                    # continue from there
+                    update_childs(child)
+
+        for node in self._nodes.itervalues():
+            if not node.parent_keys:
+                node.gdfo = 1
+                known_parent_gdfos[node.key] = 0
+                update_childs(node)
+
+    def x_find_gdfo(self):
         def find_tails():
             return [node for node in self._nodes.itervalues()
                        if not node.parent_keys]

=== modified file 'tools/time_graph.py'
--- a/tools/time_graph.py	2009-06-12 18:05:15 +0000
+++ b/tools/time_graph.py	2009-06-16 09:37:53 +0000
@@ -84,14 +84,14 @@
     h_known = all_heads_comp(known_g, combinations)
 t2 = time.clock()
 print "Known (pyx): %.3fs" % (t2-t1,)
-print "  %s" % (graph._counters,)
+#print "  %s" % (graph._counters,)
 simple_g = graph.Graph(graph.DictParentsProvider(parent_map))
 graph._counters[1] = 0
 graph._counters[2] = 0
 h_simple = all_heads_comp(simple_g, combinations)
 t3 = time.clock()
 print "Orig: %.3fs" % (t3-t2,)
-print "  %s" % (graph._counters,)
+#print "  %s" % (graph._counters,)
 if h_simple != h_known:
     import pdb; pdb.set_trace()
 print 'ratio: %.3fs' % ((t2-t1) / (t3-t2))