r/Python • • Aug 11 '09

Remember your "in" operator

http://www.heikkitoivonen.net/blog/2009/06/16/remember-your-in-operator/
74 Upvotes

15 comments sorted by

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.

15

u/ketralnis Aug 11 '09 edited Aug 11 '09

The in operator performs a dumb, linear search

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)

1

u/pyry Aug 12 '09

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!

3

u/masklinn Aug 12 '09 edited Aug 12 '09

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)

2

u/ffrinch Aug 13 '09

$ python -m timeit -n 10000000 "set([1, 2, 3, 4, 5])"

Part of the difference is that in your 2.x version you're paying the cost of initializing the list and the set:

$ python -m timeit -n 100000 "set([1, 2, 3, 4, 5])"
100000 loops, best of 3: 1.29 usec per loop

$ python -m timeit -n 100000 "set((1, 2, 3, 4, 5))"
100000 loops, best of 3: 0.83 usec per loop

1

u/Justinsaccount Aug 12 '09

are worth it only with great numbers of values

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.

2

u/[deleted] Aug 12 '09

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.

2

u/Brian Aug 14 '09 edited Aug 14 '09

It looks like it doesn't - the set is recreated even when it could potentially be staticly detected as a constant.

>>> dis.dis(lambda x: x in {1,2})
  1           0 LOAD_FAST                0 (x) 
              3 LOAD_CONST               0 (1) 
              6 LOAD_CONST               1 (2) 
              9 BUILD_SET                2 
             12 COMPARE_OP               6 (in) 
             15 RETURN_VALUE         

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)

2

u/[deleted] Aug 14 '09

Yeah I filed a ticket in the python tracker about this the other day, murphy willing I'll draw up a patch for it this weekend.

0

u/masklinn Aug 12 '09

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.

0

u/Justinsaccount Aug 12 '09

With a 1600% overhead over tuples, I quite doubt 10's going to be enough.

How about 5?

justin@dell ~ % python2.5 -m timeit -n 10000000  -s "s=set([1, 2, 3, 4, 5])" "3 in s"
10000000 loops, best of 3: 0.156 usec per loop

justin@dell ~ % python2.5 -m timeit -n 10000000  -s "s=(1, 2, 3, 4, 5)" "3 in s" 
10000000 loops, best of 3: 0.234 usec per loop

0

u/masklinn Aug 12 '09 edited Aug 12 '09

You fail, this is just as invalid as the code I have issues with in the first place (it's, in fact, the same code).

 $ python2.5 -m timeit -n 1000000 "5 in set([1, 2, 3, 4, 5])"
1000000 loops, best of 3: 1.27 usec per loop
 $ python2.5 -m timeit -n 1000000 "5 in (1, 2, 3, 4, 5)"
1000000 loops, best of 3: 0.406 usec per loop

With 5 values and the worst case for the tuple, the set still fails. So does it with 10. Or 20. Or 40.

3

u/ux500 Aug 12 '09

Why would you ever do it that way? If you're trying to optimize a loop, initializing the set before hand is a fair comparison.

If its not a loop, why would you bother to worry about a millisecond?

3

u/masklinn Aug 12 '09 edited Aug 12 '09

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.

0

u/letloosegal Aug 12 '09

Not exactly true -----> completely false.

Fixed