list index()

[Alex Martelli]

Marc 'BlackJack' Rintsch <bj_666 at gmx.net> 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