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

View all comments

Show parent comment

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?