[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Will guile support R7RS terminating "equal?" in the presence of cycl

From: Stefan Israelsson Tampe
Subject: Re: Will guile support R7RS terminating "equal?" in the presence of cycle?
Date: Sun, 9 Sep 2012 19:14:55 +0200

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?


On Sun, Sep 9, 2012 at 3:35 AM, Alex Shinn <address@hidden> wrote:
On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson Tampe
<address@hidden> 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!

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]