Set builtin lookups

[Steve Holden]

Marc 'BlackJack' Rintsch wrote:
> In <mailman.109.1182926621.22759.python-list at python.org>, Evan Klitzke
> wrote:
> 
>> I have a question about the internal representation of sets in Python.
>> If I write some code like
>>
>> if x in some_list:
>>     do_something()
>>
>> the lookup for the in statement is O(n), where n is the number of
>> elements in the list. Is this also true if I am using a set or are
>> sets represented by a hash table?
> 
> Sets are implemented as hash tables.
> 
> Ciao,
> 	Marc 'BlackJack' Rintsch

More importantly, no, neither sets nor dictionaries have O(N) lookup 
costs. As an experiment or two can show.

regards
  Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC/Ltd           http://www.holdenweb.com
Skype: holdenweb      http://del.icio.us/steve.holden
--------------- Asciimercial ------------------
Get on the web: Blog, lens and tag the Internet
Many services currently offer free registration
----------- Thank You for Reading -------------