On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe <stefan.ita...@gmail.com> wrote: > You are right! That will only work for one thread! > > Remain to see how much the overhed there is to linearize the search and > use tourtoues - hare, should be much less overhead then using a map to > mark the objects though!
See http://srfi.schemers.org/srfi-85/srfi-85.html for a common implementation approach. The basic idea there is just to run equal? normally, but keep a counter of how many objects have been compared. If the count gets too high, there is a decent chance you have a cycle, and only then do you switch to a more expensive approach. You could of course use a modified hare and tortoise with the same goal of just detecting when a cycle has occurred and switching algorithms. You only need to do this on one of the data structures, since if either is non-cyclic equal? will terminate naturally. This would be slightly more overhead than a counter, and probably require heap allocation to keep the search path in memory, but it removes the need to choose a good limit. Small cycles will still be detected right away, and very long straight lists won't switch to the expensive algorithm. I think trying to use two hares and two tortoises to compare directly without a fallback algorithm would be very harey. -- Alex
