On Feb 15, 12:32 pm, Grant Edwards <[EMAIL PROTECTED]> wrote: > On 2008-02-15, Ivan Van Laningham <[EMAIL PROTECTED]> 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? -- http://mail.python.org/mailman/listinfo/python-list