Set builtin lookups

[Evan Klitzke]

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?

--
Evan Klitzke <ev**@yelp.com>

[Marc 'BlackJack' Rintsch]

In <ma**************************************@python.o rg>, 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

[Steve Holden]

Marc 'BlackJack' Rintsch wrote:

In <ma**************************************@python.o rg>, 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 [phone] [phone]
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 -------------

[Alex Martelli]

Steve Holden <st***@holdenweb.comwrote:

Marc 'BlackJack' Rintsch wrote:

In <ma**************************************@python.o rg>, 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.

The exception would be for objects with a bad or unlucky __hash__ that
happens to return the same value for every object:

class oops(object):
def __hash__(self): return 123456

this one you might expect to produce O(N) behavior:-).
Alex