A dumb question about a class
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``.
More information about the Python-list