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 <[email protected]> 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 [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
