Algorithm used by keyword 'in'

[Chris Connett]

"Derek Rhodes" <rhoder at worldpath.net> wrote in message news:<lYS9d.144800$Kt5.79976 at twister.nyroc.rr.com>...
> #using python 2.4a3
> 
> say there is a list:
> 
> list = range(10000)
> 
> Now randomize it.
> 
> Next, command the interpreter:
> 
> >>>  465 in list
>  True
> >>>
> 
> What algorithm is used here?

Since there are no guarantees about the list or the items it contains,
the best list can do is a linear search.  Do be aware however that
each class can implement it's own behavior for keyword ``in``, by
implementing the ``__contains__`` method.  For example, sets and dicts
use a hash table implementation for their __contains__ method, so
performance there will be O(1), but sets and dicts can only contain
hashable items.  Your classes can implement it however they want, with
whatever semantics you want.

--
Chris Connett