473,324 Members | 2,456 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Recursion Performance Question

B
Hey I found some (VERY) old C++ code of mine that recursively built a
tree of the desktop window handles (on windows) using: (they are stored
in an STL vector)

void FWL(HWND hwnd, int nFlag) // Recursive Function
{
hwnd = GetWindow(hwnd, nFlag);
if(hwnd == NULL)
return;
AddWnd(hwnd);
nLevel++;
FWL(hwnd, GW_CHILD);
nLevel--;
FWL(hwnd, GW_HWNDNEXT);
return;
}

int FillWindowList(bool bReset) // Build Window List
{
WLI wli;

if(bReset)
ResetWindowList();

nLevel = 0;
FWL(ui.hWnd, GW_HWNDFIRST);

return nCount;
}

Now the interface on this program is really ugly (i hate UI coding), so
I was thinking about re-writing it in python to use PyQt for an easy
GUI. So far I have (they are stored in a 'tree' class):

# 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
def generateTree(self):
t = time.clock()
if self is not None:
self.children = []

for nd, wnd in Wnd.gwl(self, GetWindow(self.hwnd, GW_CHILD)):
nd.addChild(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. What I'm
wondering is am I doing it in a really inefficient way, or is it just
python?

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 can post more of the code if it's unclear, I just didn't want to write
a really long post.
Jul 24 '08 #1
2 1297
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
Jul 24 '08 #2
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
Jul 24 '08 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Peri | last post by:
I'm trying to create Python parser/interpreter using ANTLR. Reading grammar from language refference I found: or_expr::= xor_expr | or_expr "|" xor_expr For me it looks like infinite recursion....
12
by: da Vinci | last post by:
Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted...
10
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... ...
75
by: Sathyaish | last post by:
Can every problem that has an iterative solution also be expressed in terms of a recursive solution? I tried one example, and am in the process of trying out more examples, increasing their...
19
by: Kay Schluehr | last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
10
by: MakeMineScotch | last post by:
What's the secret to writing recursive functions that won't crash the computer?
14
by: =?ISO-8859-1?Q?S=E9bastien_de_Mapias?= | last post by:
Hello, Hopefully I'm asking my question on the proper forum, but it's some kind of low-level computer language issue and I guess here, many people are likely to give me fine enlightenments (and I...
6
by: globalrev | last post by:
i received an error maximum recursion depth when processing large amounts of data. i dont know exactly how many recursive calls i made but id assume 50000 or so. is there a definitie limit...
35
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.