MOO-cows Mailing List Archive

[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

re:hash & balanced trees

On Tue, 1 Jul 1997, Richard Godard wrote:
> Beside be carefull with the O() there are some constants that disapears and
> they can't always be neglected... beside in theory hash table have O(1)
> search/delete/add/etc., in practice... :) :) :)
> Welcome to the marvelous world of data structures and algorithms :)

And perhaps more to the point, those O() proofs assume a certain model of 
computing, which may or may not apply to the world of MOO.  In 
Mathematica, for example, most list operations are slow 
because Mathematica makes a copy of the list each time; other 
operations are very fast thanks to lazy evaluation; etc.
(Similar things happen in MOO; compare the various insertion methods
listappend(somelist, some element), somelist = {@somelist, someelement},
somelist = {@somelist, some elements, several, at, a time}, etc.  )
Consequently the fastest algorithms in theory (which assumes the RAM 
model) are not always the fastest in a program such as Mathematica or MOO.
Steven Skiena's book on Combinatorics in Mathematica (sorry, I don't 
recall the exact title) gives a nice explanation of all this.


Follow-Ups: References:
Home | Subject Index | Thread Index