[Sqlalchemy-commits] [1279] sqlalchemy/trunk/test: a new batching algorithm for the topological sort
Brought to you by:
zzzeek
Menu
▾
▴
[Sqlalchemy-commits] [1279] sqlalchemy/trunk/test: a new batching algorithm for the topological sort
|
From: <co...@sq...> - 2006-04-16 23:47:36
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head><style type="text/css"><!-- #msg dl { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; } #msg dt { float: left; width: 6em; font-weight: bold; } #msg dt:after { content:':';} #msg dl, #msg dt, #msg ul, #msg li { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; } #msg dl a { font-weight: bold} #msg dl a:link { color:#fc3; } #msg dl a:active { color:#ff0; } #msg dl a:visited { color:#cc6; } h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; } #msg pre { overflow: auto; background: #ffc; border: 1px #fc0 solid; padding: 6px; } #msg ul, pre { overflow: auto; } #patch { width: 100%; } #patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;} #patch .propset h4, #patch .binary h4 {margin:0;} #patch pre {padding:0;line-height:1.2em;margin:0;} #patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;} #patch .propset .diff, #patch .binary .diff {padding:10px 0;} #patch span {display:block;padding:0 10px;} #patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;} #patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;} #patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;} #patch .lines, .info {color:#888;background:#fff;} --></style> <title>[1279] sqlalchemy/trunk/test: a new batching algorithm for the topological sort</title> </head> <body> <div id="msg"> <dl> <dt>Revision</dt> <dd>1279</dd> <dt>Author</dt> <dd>zzzeek</dd> <dt>Date</dt> <dd>2006-04-16 18:47:26 -0500 (Sun, 16 Apr 2006)</dd> </dl> <h3>Log Message</h3> <pre>a new batching algorithm for the topological sort</pre> <h3>Modified Paths</h3> <ul> <li><a href="#sqlalchemytrunklibsqlalchemymappingtopologicalpy">sqlalchemy/trunk/lib/sqlalchemy/mapping/topological.py</a></li> <li><a href="#sqlalchemytrunktestdependencypy">sqlalchemy/trunk/test/dependency.py</a></li> </ul> </div> <div id="patch"> <h3>Diff</h3> <a id="sqlalchemytrunklibsqlalchemymappingtopologicalpy"></a> <div class="modfile"><h4>Modified: sqlalchemy/trunk/lib/sqlalchemy/mapping/topological.py (1278 => 1279)</h4> <pre class="diff"><span> <span class="info">--- sqlalchemy/trunk/lib/sqlalchemy/mapping/topological.py 2006-04-14 18:11:54 UTC (rev 1278) +++ sqlalchemy/trunk/lib/sqlalchemy/mapping/topological.py 2006-04-16 23:47:26 UTC (rev 1279) </span><span class="lines">@@ -57,6 +57,16 @@ </span><span class="cx"> return "%s (idself=%s)" % (str(self.item), repr(id(self))) </span><span class="cx"> def __repr__(self): </span><span class="cx"> return self.describe() </span><ins>+ def is_dependent(self, child): + if self.cycles is not None: + for c in self.cycles: + if c.dependencies.has_key(child): + return True + if child.cycles is not None: + for c in child.cycles: + if self.dependencies.has_key(c): + return True + return self.dependencies.has_key(child) </ins><span class="cx"> </span><span class="cx"> def __init__(self, tuples, allitems): </span><span class="cx"> self.tuples = tuples </span><span class="lines">@@ -138,21 +148,46 @@ </span><span class="cx"> if len(childnode.edges) == 0: </span><span class="cx"> queue.append(childnode) </span><span class="cx"> </span><del>- #print repr(output) - head = None - node = None - # put the sorted list into a "tree". this is not much of a - # "tree" at the moment as its more of a linked list. it would be nice - # to group non-dependent nodes into sibling nodes, which allows better batching - # of SQL statements, but this algorithm has proved tricky - for o in output: - if head is None: - head = o </del><ins>+ return self._create_batched_tree(output) + + + def _create_batched_tree(self, nodes): + """given a list of nodes from a topological sort, organizes the nodes into a tree structure, + with as many non-dependent nodes set as silbings to each other as possible.""" + def sort(index=None, l=None): + if index is None: + index = 0 + + if index >= len(nodes): + return None + + node = nodes[index] + l2 = [] + sort(index + 1, l2) + for n in l2: + if l is None or search_dep(node, n): + node.children.append(n) + else: + l.append(n) + if l is not None: + l.append(node) + return node + + def search_dep(parent, child): + if child is None: + return False + elif parent.is_dependent(child): + return True </ins><span class="cx"> else: </span><del>- node.children.append(o) - node = o - return head - </del><ins>+ for c in child.children: + x = search_dep(parent, c) + if x is True: + return True + else: + return False + return sort() + + </ins><span class="cx"> def _add_edge(self, edges, edge): </span><span class="cx"> (parentnode, childnode) = edge </span><span class="cx"> edges[parentnode][childnode] = True </span></span></pre></div> <a id="sqlalchemytrunktestdependencypy"></a> <div class="modfile"><h4>Modified: sqlalchemy/trunk/test/dependency.py (1278 => 1279)</h4> <pre class="diff"><span> <span class="info">--- sqlalchemy/trunk/test/dependency.py 2006-04-14 18:11:54 UTC (rev 1278) +++ sqlalchemy/trunk/test/dependency.py 2006-04-16 23:47:26 UTC (rev 1279) </span><span class="lines">@@ -24,10 +24,10 @@ </span><span class="cx"> </span><span class="cx"> print "\n" + str(head) </span><span class="cx"> def findnode(t, n, parent=False): </span><del>- if n.item is t[0]: </del><ins>+ if n.item is t[0] or (n.cycles is not None and t[0] in [c.item for c in n.cycles]): </ins><span class="cx"> parent=True </span><span class="cx"> elif n.item is t[1]: </span><del>- if not parent and t[0] not in [c.item for c in n.cycles]: </del><ins>+ if not parent and (n.cycles is None or t[0] not in [c.item for c in n.cycles]): </ins><span class="cx"> self.assert_(False, "Node " + str(t[1]) + " not a child of " +str(t[0])) </span><span class="cx"> else: </span><span class="cx"> return </span><span class="lines">@@ -148,6 +148,7 @@ </span><span class="cx"> self._assert_sort(tuples, allitems) </span><span class="cx"> </span><span class="cx"> def testcircular(self): </span><ins>+ #print "TESTCIRCULAR" </ins><span class="cx"> node1 = thingy('node1') </span><span class="cx"> node2 = thingy('node2') </span><span class="cx"> node3 = thingy('node3') </span><span class="lines">@@ -162,6 +163,7 @@ </span><span class="cx"> (node4, node1) </span><span class="cx"> ] </span><span class="cx"> self._assert_sort(tuples, [node1,node2,node3,node4,node5], allow_all_cycles=True) </span><ins>+ #print "TESTCIRCULAR DONE" </ins><span class="cx"> </span><span class="cx"> </span><span class="cx"> if __name__ == "__main__": </span></span></pre> </div> </div> </body> </html> |
