[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: Mark H Weaver
Subject: Re: Will guile support R7RS terminating "equal?" in the presence of cycle?
Date: Sat, 08 Sep 2012 23:41:26 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.6esrpre) Gecko/20120817 Icedove/10.0.6

On 09/08/2012 09:35 PM, Alex Shinn 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.

Another option is to use the method described in "Efficient Nondestructive Equality Checking for Trees and Graphs" by Adams and Dybvig.


reply via email to

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