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.


Cheers,
michael
brundageQipac.caltech.edu

---

Follow-Ups:

• Re: hash & balanced trees
• From: "Robert J. Brown" <rj@eli.wariat.org>

References:

• re:hash & balanced trees
• From: Richard Godard <janus@cam.org>

---

• Prev by Subject: re:hash & balanced trees
• Next by Subject: Re: hash & balanced trees
• Prev by thread: Re: hash & balanced trees
• Next by thread: Re: hash & balanced trees
• Index(es):
  • Subject
  • Thread

Home |
Subject Index |
Thread Index