Recursive Algorithm getting stuck (because of Python Limits?)
Duncan Booth
duncan at NOSPAMrcp.co.uk
Mon Apr 28 10:46:31 EDT 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