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

# re:hash & balanced trees

- Date: Mon, 7 Jul 1997 06:12:16 -0700 (PDT)
- From:
- cc: moo-cows@the-b.org
- Content-Type: TEXT/PLAIN; charset=US-ASCII
- In-Reply-To: <v03102800afde334441f5@[205.151.119.249]>

    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