Re: [Scheme-reports] Cycle detection problems: #442, #338, "equal?"

[Alex Shinn <alexshinn@x>]

On Thu, Aug 30, 2012 at 12:00 PM, David A. Wheeler
<dwheeler@x> wrote:
>
>> No it does not, this can be done essentially for free,
>> see http://www.r6rs.org/r6rs-editors/2006-February/000969.html
>
> Ah, thanks so much for the reference, I appreciate it.
>
> I read the email, and I'm even more confused.  That email doesn't seem to show "free" at all, indeed, it seems to soundly disprove it.  The equiv? operator (a terminating equal?, as proposed) appears to take 300% (3 times) as much time or much more in most cases.

I meant "free" asymptotically.  The constants don't bother me
for an operation already as expensive as equal?.

I'm also surprised that you would dislike this approach, which
is basically the same as what you were previously advocating
for write, except with much nicer behavior.  Unlike with write
you don't need to accumulate vast amounts of output anywhere.
Moreover, whereas the worst-case for write happens whenever
you have any cycle, the worst-case for equal? only happens
when you have two (non-eq?) structures, both of which have
cycles, and which are in fact equal?.

However, if the constants really bother you, I timed chibi's
equal?, with and without cycle detection, on comparing two
equal? lists of 100000 elements (which is the worst case
outside of the presence of cycles).  Unlike the comparison
in the previous link this was using the exact same code,
minus the bounds checking.  The result was an average
of 300ms for 100 repetitions with the checks, and 226ms
without.  For more common cases where the lists are
unequal or shorter, or for more primitive structures, there
would be no overhead.

Anyway, equal? was never a "fast" operation - it could
always consume very large amounts of time on large
data-structures, so was never appropriate where speed
was crucial.  Making it avoid infinite loops is definitely
the right thing.

-- 
Alex

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports