A dumb question about a class

Steven Bethard steven.bethard at gmail.com
Wed Aug 15 00:41:07 CEST 2007


thattommyhallll at gmail.com wrote:
> Also, does anyone know if there is some magic that makes
> i in some_set
> loads faster than
> i in some_list

It's not magic, per se.  It's really part of the definition of the data 
type. Lists are ordered, and are slow when checking containment. Sets 
are unordered and are quick when checking containment.

When you execute ``i in some_list``, Python searches through the list 
starting at index 0, and stopping when it sees ``i`` or hits the end. In 
computational terms, this is O(n), meaning that for a list of length n, 
you'll take an amount of time proportional to n.

When you execute ``i in some_set``, Python hashes ``i``, and checks the 
set to see if it contains anything with the same hash value. On the 
average (given the Python implementation) it is probably checking at 
most one or two values. In computational terms, this is O(1), meaning 
that on the average it only takes a constant amount of time.

So if you have code doing ``if foo in bar`` more than once, you *really* 
should be using a set for ``bar``.

STeVe



More information about the Python-list mailing list