|
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 |
On Sun, Sep 9, 2012 at 2:00 AM, Stefan Israelsson TampeSee http://srfi.schemers.org/srfi-85/srfi-85.html
<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.
--
Alex
[Prev in Thread] | Current Thread | [Next in Thread] |