Re: bad generator performance

From: Johannes Ahl-mann (softpro_at_gmx.net)
Date: 02/06/05 

Date: Sun, 6 Feb 2005 16:58:31 +0100

> You don't really give the complete story so it's hard to tell what
> exactly is going on. For example, I would assume the recursion is
> calling the same method (i.e., depthFirstIterator1 or
> depthFirstIterator2), but then you posted separate timing information
> for a "recursive helper function" so I'm not so sure. Also there is not
> much of a hint as to the nature of your data.

yeah, sorry. i'm not myself lately ;-))
forget about the helper function, that was nonsense! i used a helper
function to build a huge tree as test data, but that is the same
function for both cases!

the program is supposed to manage bookmarks and i thought it would be a
good idea to represent the bookmarks as a tree (with folders as internal
nodes and bookmarks as leaves).
so, a tree is never going to hold more than say 2000 nodes and is going
to be rather wide than deep!

> In my testing (on Python 2.3.4 on
> Windows XP), the generator version takes about 1/4 of the time that the
> list version takes. If both versions call the list version of the method
> recursively (i.e., you're only getting the benefit of the generator at
> the top level of the recursion), the generator version is still about
> 20% faster.
>
> Timing differences could potentially depend on your data also - things
> like how deep vs. wide your tree is.

thx a lot and sorry for not supplying my data type and test data!
hmm, that totally contradicts my profiling results... on my machine the
generator version is repeatedly 10 times slower than the list version as
well with python2.3 as with python2.4.
i don't want to spam the list with hundreds of lines of source code, so
i'll just cry a little and try to do something else than prematurely
optimising my bookmark script *gg*

thx,

Johannes

Relevant Pages

  • Re: Count all nodes in a treeview
    ... Which suggests that the TTreeNodes type exposes the entire tree as a flat hierarchy via its "Item" member. ... Pedro's code does this via recursion, returning for each node the sum of the number of direct descendants and the calculated value of nodes from each of those descendants. ... child I traverse the childnode and get all of it's settings too. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Searching "Binary Search Trees" using recursion.
    ... >every single leaf on the tree. ... it's hard *not* to use recursion. ... >statements, and if i use return statements, i cant call iself twice. ... int countNodes(BstNode subtreeRoot) { ...
    (comp.lang.java.help)
  • Re: Binary Tree reposted
    ... > linked lists at all the tree nodes. ... //but I feel this is "look ahead recursion" and inferior to the above. ... If it's not clear, maybe your instructor ...
    (comp.lang.pascal.delphi.misc)
  • Re: iterative copying of binary expression trees
    ... to solve this problem of copying in a functional iterative way a binary tree. ... I have already a two-phase algorithm. ... Tree walkers belong to a class of functions that are fundamentally ... requires doing things via multiple recursion along different branches of ...
    (comp.lang.lisp)
  • Re: Help- Recursion v. Iter Speed comparison
    ... Recursion is usually slower than ... >> Would using a generator be faster than recursion? ... > def f1: ... list comprehension approach ...
    (comp.lang.python)