Solve a Debate

[castironpi at gmail.com]

On Feb 15, 12:32 pm, Grant Edwards <gra... at visi.com> wrote:
> On 2008-02-15, Ivan Van Laningham <ivanl... at gmail.com> wrote:
>
> > Lookup tables are always significantly faster than a bunch of
> > ifs.
>
> Mostly always.  It depends on what you mean by "lookup table",
> and it depends on how the language implements things.  If you
> by "lookup table" you mean a linearly indexed array, then an
> array lookup is O(1), and a series of if/then/elses is O(n).
> The indexing operation is going to be faster for all practical
> examples I can think of.
>
> If by "lookup table" you mean an arbitrary mapping (e.g. a
> "dict" in Python), then it depends on the hashing/searching
> used to implement the lookup operation. It's possible for small
> mappings using some types of keys that a series of compares
> could be faster than the hashing operation.
>
> In the general case, if the key being used consists of a lot of
> bits, you might have to hash all of the bits before you can
> start looking up the result. When doing compares, you can quite
> after the first bit doesn't match.  IOW, you might be able to
> do a lot of failed key compares in the time it takes to hash
> the key.
>
> --
> Grant Edwards                   grante             Yow! Can you MAIL a BEAN
>                                   at               CAKE?
>                                visi.com            

I forget the name, or it's not on the web.  "D-tables"-- sorry, by
example:

D= []

insert 00101110

D= [ 00101110 ]

insert 00101111

D= [ 0010111: [ 0, 1 ] ]

insert 1

D= [ [ 0: 010111: [ 0, 1 ] ], 1 ]

def insert( x ):
   for bit in x:
      if curnode.bit!= bit:
         addnode( node( curnode, x ) )
         return
   addleaf( x )

Which doesn't do it justice.  Anyway, I think it's a log-n lookup on
arbitrary data types.  How does the Python implementation handle hash
collisions?  Shoot and pray?