Recursion Performance Question

Tim Golden mail at timgolden.me.uk
Thu Jul 24 04:57:53 EDT 2008


B wrote:
> Now it works, but it runs quite slow (compared to the c++ app).  I 
> changed gwl from strait recursion to use a generator and that helped, 
> but it still takes 0.5-1.0 seconds to populate the tree.  What I'm 
> wondering is am I doing it in a really inefficient way, or is it just 
> python?

Well I did just enough to get your code to work and ran
it through timeit on my respectable but hardly bleeding-edge
desktop PC.

<dump>
C:\temp>python -m timeit "import get_windows; get_windows.run ()"
100 loops, best of 3: 17.1 msec per loop
</dump>

So it's not that slow. Full code is posted below; uncomment
the "print_tree" bit to see the results to confirm that it's
doing what you think. I did this really quickly so it's
possibly I've misunderstood what your code's up to.

I'm not saying there aren't other ways to do this, but
your code (at least inside my guessed-at wrapper) seems
to do an adequate job in a reasonable time.

<get_windows.py>
import time
from win32gui import GetWindow, GetWindowText, GetDesktopWindow
from win32con import GW_CHILD, GW_HWNDNEXT

class Node (object):
  def __init__ (self, hwnd):
    self.hwnd = hwnd
    self.children = []
  def addChild (self, hwnd):
    self.children.append (Node (hwnd))

def gwl(node, hwnd):
    if hwnd:
        yield node, hwnd
        for nd, wnd in gwl(node.children[-1], GetWindow(hwnd, GW_CHILD)):
            yield nd, wnd
        for nd, wnd in gwl(node, GetWindow(hwnd, GW_HWNDNEXT)):
            yield nd, wnd


def generateTree(self):
    t = time.clock()
    if self is not None:
        self.children = []

        for nd, wnd in gwl(self, GetWindow(self.hwnd, GW_CHILD)):
            nd.addChild(wnd) 

def print_tree (root, level=0):
  print level * " ", GetWindowText (root.hwnd) or hex (root.hwnd)
  for child in root.children:
    print_tree (child, level + 1)

def run ():
  desktop = Node (GetDesktopWindow ())
  generateTree (desktop)
  #~ print_tree (desktop)

</get_windows.py>


> The second problem is reseting the list.  In C++ I would use the STL 
> Vector's clear() method.  In python, I can't think of a good way to free 
>  all the nodes, so there is a large memory leak.


I'm not clear here what you're getting at. Memory handling in Python
is usually best left to Python unless you've got a very specific
case -- and they do crop up occasionally. Just to be clear on something:
Python does its own internal memory management, alloc-ing and free-ing
with a variety of policies broadly managed by an internal pool. You're
unlikely to see much memory released back to the system while Python's
running. But this isn't a memory leak as such. You don't need to (and,
in effect, can't) release the memory explicitly.

But I'd be surprised if you had enough windows open for this to be
even noticeable.

TJG



More information about the Python-list mailing list