RE: bad generator performance

From: Jimmy Retzlaff (jimmy_at_retzlaff.com)
Date: 02/06/05 

Date: Sun, 6 Feb 2005 06:57:03 -0800
To: <python-list@python.org>

Johannes Ahl-mann wrote:
> i just wondered if there was a concise, clean way of doing this with
> generators which i had overlooked, or whether there was some blatant
> mistake in my code.

Aside from the recursion question...

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.

Below is a test where each of your 2 methods calls itself recursively.
To make it work I had to build a data tree - I used the files and
folders in my C:\Python23 directory. 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.

Jimmy

import os
import time

class Node:
    def __init__(self, pathname):
        self.thisIsAFolder = os.path.isdir(pathname)
        self.children = []
        if self.isFolder():
            for filename in os.listdir(pathname):
                childpathname = os.path.join(pathname, filename)
                self.children.append(Node(childpathname))

    def isFolder(self):
        return self.thisIsAFolder

    def depthFirstIterator1(self, depth = 0):
        ret = [[self, True, depth]]

        if self.isFolder():
          for c in self.children:
            ret = ret + c.depthFirstIterator1(depth = depth + 1)

        return ret + [[self, False, depth]]

    def depthFirstIterator2(self, depth = 0):
        yield [self, True, depth]

        if self.isFolder():
          for c in self.children:
            for y in c.depthFirstIterator2(depth = depth + 1):
              yield y

        yield [self, False, depth]

x = Node(r'C:\Python23')
for iterator in (x.depthFirstIterator1, x.depthFirstIterator2):
    print iterator.__name__,
    start = time.time()
    for item in iterator():
        pass
    print round(time.time()-start, 2)

Relevant Pages

  • 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)
  • Re: bad generator performance
    ... I would assume the recursion is ... good idea to represent the bookmarks as a tree (with folders as internal ... the generator version takes about 1/4 of the time that the ...
    (comp.lang.python)
  • Re: What is the "functional" way of doing this?
    ... grand conclusions about the general speed of recursion etc. in Python from ... As soon as the size of the list increases the generator function ... Not especially surprising. ... naturally more expensive than a single function call. ...
    (comp.lang.python)
  • RE: Simple Recursive Generator Question
    ... but one of the things you're missing is ... The generator saves you having to pass the "index" param recursively. ... > Changing yield to print, shows that the recursion works correctly. ...
    (comp.lang.python)
  • Re: need help on need help on generator...
    ... A generator function, ... way to make sure you have an iterator is to call iteron something; ... > there's such a thing in Python (... ... My prediction is that even Python 3000 will be strict. ...
    (comp.lang.python)