Aaron W. Hsu scripsit:

> > Less tendentiously, write/small-fast.
>
> Have we done any benchmarks to see how fast this really is in practice?
> It seems like we are assuming it is faster, but I do not remember seeing
> anything indicating that it was really significantly faster than
> WRITE/SAFE. IMO, the lack of safety of WRITE/SMALL-FAST is hard to justify.

You can make it as fast as you want if you are willing to spend enough
space.  But the algorithm has to do *some* kind of bookkeeping to see if
it's visited this node before (the two-pointer algorithm used for length
won't work), and that bookkeeping must cost either space or time or both.

Alternatively, you can traverse the whole graph using the length algorithm
before you start to print anything, but that necessarily costs time.

Lastly, write/small-fast is perfectly safe if you know you don't construct
cycles, and lots of programs do know that (if they don't use set-car! or
set-cdr!, for example).

--
John Cowan  <cowan@ccil.org>  http://ccil.org/~cowan
Micropayment advocates mistakenly believe that efficient allocation of
resources is the purpose of markets.  Efficiency is a byproduct of market
systems, not their goal.  The reasons markets work are not because users
have embraced efficiency but because markets are the best place to allow
users to maximize their preferences, and very often their preferences are
not for conservation of cheap resources.  --Clay Shirky

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