Le Fri, 12 Oct 2012 16:39:33 +0000, [email protected] a écrit : > Please review this at http://codereview.tryton.org/558002/ >
I have made an alternative implementation, that is IMO a bit simpler but a bit slower: http://codereview.tryton.org/562002/ The original implementation fixed by the codereview 558002 start by a set containing all the locations leafs and update this set at each iteration (the new leafs being the parent of the leafs at the previous iteration). The other implementation start from each node of the tree (not only the leafs) and carry up the quantities by "bubbling"-up. So at each location start a bubble that will move up to the root, so it means that all the location will be traversed several time (to the contrary of the "leaf" implementation). So I made a benchmark that allows to compare both implementation: http://dpaste.com/813597/ The benchmark build a tree and launch the two algorithms. For a tree with a depth of 4 and a number of 8 children per node (total of 37448 nodes) it takes 0.12 (leaf) and 0.13 (bubble) seconds. For a tree with a depth of 4 and a number of 8 children per node (total of 349524 nodes) it takes 1.13 (leaf) and 1.19 (bubble) seconds. So the leaf implementation is quicker but the code is a bit more complex to understand. So to my eyes they are both good. Who thinks one algo must be preferred and why ? Thanks, Bertrand -- Bertrand Chenal B2CK SPRL Rue de Rotterdam, 4 4000 Liège Belgium Email: [email protected] Website: http://www.b2ck.com/ -- [email protected] mailing list
