On Thu, Aug 30, 2012 at 12:00 PM, David A. Wheeler <[email protected]> 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 [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
