There is another interesting option that uses a hash to mark objects. Keep a counter and for each new object check the counter, if it's 0 then check to see if the object have been visited before else register it! then initiate the counter with (random N) elements.
If N equals 10 in guile scheme, then equal-with-cycle-detection is about twice as slow as an ordinary equal? on two equal? 1000 times long list. The drawback is that for cyclic structures you get a positive probability to wait for a very long time but typically the expected waiting time should be less then (N / 2) ** 2 = 25 in my test case. By increasing the N you will cause less overhead on the normal behavior but increase the cost for structures with cycles. Anything unsound with this approach? /Stefan On Sun, Sep 9, 2012 at 3:35 AM, Alex Shinn <alexsh...@gmail.com> wrote: > 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 >
