Re: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

jryan,
I am at YAPC::NA 2008 and admittedly have only skim read your code. I have a couple of depth first search (DFS) iterators at:

It doesn't matter if you are letting perl manage the call stack (recursive function) or you are managing your own queue/stack (@work) - you will run into memory problems if you have to put more items on the stack then you take off. If this is the root of your problem (and I haven't read far enough to know for sure), then you will need to take a different approach.

Cheers - L~R

Comment on Re: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams?

Replies are listed 'Best First'.
Re^2: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams? by jryan (Vicar) on Jun 16, 2008 at 21:56 UTC
Thats definitely the root of my problem. I think your approach to an iterator might help though, I think I just need to figure-out how to integrate it with my code. One question before I try it out: what is more efficient memory-wise about your second approach than your first approach?	[reply]
Re^3: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams? by Limbic~Region (Chancellor) on Jun 17, 2008 at 13:46 UTC
jryan, Again, I am at the conference so I don't have the time to give you a proper response. The second one, which is more memory efficient, only requires as many nodes on the stack as the max depth of the tree. It does this by creating an iterator (one item) for the stack instead of a list of nodes (many) to visit. You then work through that iterator before moving on. This is a poor explanation - I know, but I won't be available to explain in detail until Thursday. Cheers - L~R	[reply]
Re^4: Eliminating Recursive Tree Walking by using MJD-style Infinite Streams? by ikegami (Patriarch) on Jun 17, 2008 at 14:50 UTC
In case you're curious, only requires as many nodes on the stack as the max depth of the tree. So does mine below. It does this by creating an iterator (one item) for the stack instead of a list of nodes (many) to visit. Mine doesn't wrap the array index in an iterator. I started making a version that did, but it was complicating the ability to return the path that led to the node (like the OP's) instead of just the node (like yours).	[reply]


Perl: the Markov chain saw
	PerlMonks