Steve Holden <[EMAIL PROTECTED]> wrote: > Marc 'BlackJack' Rintsch wrote: > > In <[EMAIL PROTECTED]>, 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 -- http://mail.python.org/mailman/listinfo/python-list
