Recursion Performance Question
Anders J. Munch
2007 at jmunch.dk
Thu Jul 24 08:24:38 EDT 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