[PEAK] naming.lookup() vs config.lookupComponent()

[Phillip J. Eby]

At 12:11 AM 6/22/04 -0500, Doug Quale wrote:

>If you haven't seen the tortoise and hare algorithm, it's an idea that
>is well known in the Lisp world where circular lists are fairly
>common.  The key idea is that you can detect circular structures
>without keeping an entire path history -- all you need is one extra
>pointer.  It uses a slow pointer and a fast pointer.  At each step,
>the slow pointer advances one and the fast pointer advances two.  If
>the structure is circular the fast and slow pointers will eventually
>meet.

That is awesome; I've never heard of that algorithm but it makes perfect sense.

I won't be using it here, though, as it'd be approximately three times 
slower than the current 'iterParents()' routine.  :(

You see, more often than not, the performance of a Python algorithm is 
directly proportional to the number of function calls occurring, and the 
tortoise-hare approach will call 'getParentComponent()' three times as 
often as the recursion counting approach.

I suppose it'd be possible to do something like use a list as a queue to 
keep track of the 'fast' pointer's results, and have the 'slow' pointer 
remove items from the tail end of the queue, as that would only invoke 
primitive calls like append() and pop().

Another variation that occurs to me is that you could simply advance the 
slow pointer once out of every N fast advances, for some N, while using the 
'fast' pointer as the yielded value.  That is, the fast pointer advances 1 
each time, and the slow pointer effectively advances 1/N.  If N is as high 
or higher than the average component tree depth, the amortized cost 
wouldn't be much different than that of the "recursion limit" approach 
(i.e. decrementing a counter and checking it on each iteration).

So it's still somewhat interesting, although I don't feel intuitively 
positive that the algorithm is guaranteed to terminate, and don't see that 
it really adds anything over a recursion limit, since as a practical matter 
having super-deep component hierarchies requiring lots of iteration over to 
perform operations is probably something you want to know is happening, and 
do something about.  So, "Simplest Thing That Could Possibly Work" here 
seems to favor the counting approach.