Recursive Algorithm getting stuck (because of Python Limits?)

Duncan Booth duncan at NOSPAMrcp.co.uk
Mon Apr 28 16:46:31 CEST 2003


gildemere at hotmail.com (Marc Floessel) wrote in 
news:236da4ed.0304280616.349e8bdd at posting.google.com:

> This works. However increasing the Depth or Breadth to 8 seems to
> break Python. Python rises to about 100 MB memory consumption (as
> indicated by the Windows Task Manager) and then seems to drop and rise
> randomly. The algorithm never finishes. Am I breaking the stack?

7 wide and deep you are trying to create 137,257 nodes. 8 wide and deep you 
are trying to create 2,396,745 nodes so it should take 17 times as much 
memory. It will take much more than 17 times longer if you are using Python 
2.2.x as Microsoft's memory allocation routines grind to a halt when you 
have that many objects. Also you are probably running out of memory. When 
the memory figure in task manager starts fluctuating it is because youre 
process is thrashing. My machine started thrashing like that around 400Mb 
used. 

Adding a __slots__ member to the Node class removes the need to create a 
dictionary for each instance. On Python 2.3 this reduces the total memory 
requirement for 8 deep to about 170Mb, and the runtime to a couple of 
minutes.

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?




More information about the Python-list mailing list