# hash & balanced trees

Michael Brundage (brundage@piaf.ipac.caltech.edu)
Mon, 7 Jul 1997 06:12:16 -0700 (PDT)

- Messages sorted by:[ date ][ thread ][ subject ][ author ]

    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