Recursion Performance Question

B execrable at gmail.com
Thu Jul 24 05:02:03 CEST 2008


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.



More information about the Python-list mailing list