Marc 'BlackJack' Rintsch <[EMAIL PROTECTED]> wrote: > On Sat, 01 Sep 2007 13:44:28 -0600, Michael L Torrie wrote: > > > Alex Martelli wrote: > > > >> is the "one obvious way to do it" (the set(...) is just a simple and > >> powerful optimization -- checking membership in a set is roughly O(1), > >> while checking membership in a list of N items is O(N)...). > > > > Depending on a how a set is stored, I'd estimate any membership check in > > a set to be O(log N). > > Sets are stored as hash tables so membership check is O(1) just like Alex > said.
"Roughly" O(1), as I said, because of the usual issues with cost of hashing, potential hashing conflicts, re-hashing (which requires thinking in terms of *amortized* big-O, just like, say, list appends!), etc, just like for any hash table implementation (though Python's, long used and finely tuned in dicts then adopted for sets, is an exceedingly good implementation, it IS possible to artificially construct a "worst case" -- e.g., set(23+sys.maxint*i*2+i for i in xrange(24,199))...) Alex -- http://mail.python.org/mailman/listinfo/python-list