Recursion Performance Question

Anders J. Munch 2007 at jmunch.dk
Thu Jul 24 14:24:38 CEST 2008


B wrote:
 >
 > # pass in window handle and parent node
 >     def gwl(node, hwnd):
 >         if hwnd:
 >             yield node, hwnd
 >             for nd, wnd in Wnd.gwl(node.children[-1], GetWindow(hwnd,
 > GW_CHILD)):
 >                 yield nd, wnd
 >             for nd, wnd in Wnd.gwl(node, GetWindow(hwnd, GW_HWNDNEXT)):
 >                 yield nd, wnd
[...]
 >
 > 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.

Actually the generator could well be the problem here, because of time
spent on yield propagation: gwl has worst-case quadratic
performance, the worst case being if the tree is unbalanced and deep,
because every yielded value must pass through a chain of propagation
for-loops.

Straight recursion should be faster; I don't know what you did to make
it slow, but try something along these lines:

def gwl_helper(node, hwnd, collect):
     if hwnd:
         collect((node,hwnd))
         gwl_helper(node.children[-1], GetWindow(hwnd, GW_CHILD), collect)
         gwl_helper(node, GetWindow(hwnd, GW_HWNDNEXT), collect)

def gwl(node, hwnd):
     result = []
     gwl_helper(node, hwnd, result.append)
     return result

- Anders



More information about the Python-list mailing list