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. 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 ------------- -- http://mail.python.org/mailman/listinfo/python-list