Prev: Anyone heard of Bee Lisp?
Next: Anyone willing to sell "On Lisp"?
From: Alex Mizrahi on 19 Mar 2010 03:59
??>> As I understand you can get something like O(N*M) complexity if one
??>> table is not indexed and all other tables are indexed.
??>> That is, you do a full scan on a table with N elements, doing M
??>> operations on each element. Well, you also have a (log N) somewhere
??>> there, but who cares?

RW> The lookup of the indexed element would typically be an
RW> O(log(m)) operation,

Yep, for trees.

RW> unless the lookup used a perfect hash (maybe even an identitity hash
:-)

Any sane hash table has O(1) lookups, it doesn't need to be perfect.

If you have N buckets for N keys and hashes of keys are uniformly
distributed, you have like 0..2 entries in each bucket.
Probablility of having higher number of entries in a bucket is very low, so
on average you have O(1) lookups.

First  |  Prev  | 
Pages: 1 2 3 4 5 6 7 8 9 10
Prev: Anyone heard of Bee Lisp?
Next: Anyone willing to sell "On Lisp"?