[PEAK] naming.lookup() vs config.lookupComponent()
Phillip J. Eby
pje at telecommunity.com
Tue Jun 22 12:50:51 EDT 2004
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
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.
More information about the PEAK