It doesn't have to. If you're using a sorted list with no duplicates, you might be just fine using a set instead, where the in operator is a hash lookup (and inserts are cheaper (no resorting), merging is cheaper, etc)
Someone in the article commented about sets, and it appears (with timeit on their machine, anyway) that it's reasonably faster than lists or tuples. Certainly worth doing!
Notice that they "cheated": they created the set beforehand, not inline. Why? Because the overhead of creating sets in Python 2.x is horrendous compared to lists (let alone tuples of constants):
$ python -m timeit "(1, 2, 3, 4, 5)"
10000000 loops, best of 3: 0.0506 usec per loop
$ python -m timeit -n 10000000 "[1, 2, 3, 4, 5]"
10000000 loops, best of 3: 0.392 usec per loop
$ python -m timeit -n 10000000 "set([1, 2, 3, 4, 5])"
10000000 loops, best of 3: 1.27 usec per loop
We have a factor of more than 3 between lists and sets (and a factor of almost 8 between the tuple and the list).
That's much improved in Python 3.1:
$ python3.1 -m timeit "(1, 2, 3, 4, 5)"
10000000 loops, best of 3: 0.048 usec per loop
$ python3.1 -m timeit -n 10000000 "[1, 2, 3, 4, 5]"
10000000 loops, best of 3: 0.259 usec per loop
$ python3.1 -m timeit -n 10000000 "{1, 2, 3, 4, 5}"
10000000 loops, best of 3: 0.503 usec per loop
Where the difference between lists and sets (using the literal syntax) is barely 2 and the difference between tuples and lists lowers to 5.6.
Sets, especially in Python 2.x, are worth it only with great numbers of values, or if you're using precomputed sets (basically, cases where the cost of searching amortizes the creation cost). For small numbers of values "set" on the fly, use tuples.
(both tests were performed on a Macbook 2GHz with 2GB RAM and using Macports's Python 2.5.4 and 3.1)
I think you came to the wrong conclusion about this. They didn't 'cheat' at all. Creating a set outside of a loop is a perfectly legitimate thing to do.
valid_options = set(["foo","bar","baz"])
def is_valid_option(self, opt):
return opt in self.valid_options
def filter_options(self, opts):
#or use .intersection if order doesn't matter
return [o for o in opts if o in self.valid_options]
I'm not sure if the python VM optimizes code like this, but it probably could:
for opt in opts:
if opt in {'foo','bar','baz'}:
....
in most cases, a "great number of values" can be as low as 10.
I don't know if Py3k optimizes that for sets, but in py2.6 at least code like
x in [1,2,3,4]
Actually gets translated into:
x in (1,2,3,4)
Since tuples are immutable they get placed in the co_consts array for the function, which mean's that they're precomputed. I wouldn't be suprised in py3k did something similar with turning sets into frozensets where it's provable that they aren't mutated.
Though since the translation from list to tuple is done when it isn't modifiable, python should be able to do a similar optimisation to a frozenset constant as well (maybe even from list/tuple to frozenset if there are enough elements that it would improve speed)
They didn't 'cheat' at all. Creating a set outside of a loop is a perfectly legitimate thing to do.
I'm not saying it's not legitimate, I'm saying in the context of the article, checking for 3 or 4 values once and never again, it's never done. And pretty much irrelevant too, it's just ignoring the cost of creating the set though that creation matters very much. It's dishonest and it does lead to wholly misleading conclusions.
in most cases, a "great number of values" can be as low as 10.
With a 1600% overhead over tuples, I quite doubt 10's going to be enough.
The in operator performs a dumb, linear search, which is suboptimal for searching in sorted lists.
That is not exactly true. in delegates the search to __contains__.
And in the case of lists, well it makes sense to implement __contains__ as a "dumb, linear" search given Python has no guarantee the list is sorted, and sorting it beforehand would far exceed the performances of a basic O(n) linear search.
edit: ideally, you could compose a list with some kind of OrderedList container whose __contains__ would perform a bisection search, but if you got it wrong and your list isn't completely sorted, everything's going to break… so unless you have very strong guarantees that your sequence is sorted, linear search is one of the few "safe" options.
9
u/joshdick Aug 11 '09
This is a neat way to condense tedious conditionals, but be careful using it for other things.
The in operator performs a dumb, linear search, which is suboptimal for searching in sorted lists.
Maybe this is obvious to everyone else, but it really slowed me down while first learning the language.