Filtering list concepts - "set () trap"

Question

A fairly general operation is to filter one list based on another list . People quickly find that it is:

 [x for x in list_1 if x in list_2] 

slow for large inputs is O (n * m). Ugh. How do we speed it up? Use set to search for O (1) filters:

 s = set(list_2) [x for x in list_1 if x in s] 

This gives good overall O (n) behavior. I often see that even veteran coders get into The Trap ™:

 [x for x in list_1 if x in set(list_2)] 

Ack! This is O (n * m) again, since python creates set(list_2) every time, not just once.

---

I thought this was the end of the story - python cannot optimize it to only create set once. Just know about the trap. Gotta live with that. Hm.

 #python 3.3.2+ list_2 = list(range(20)) #small for demonstration purposes s = set(list_2) list_1 = list(range(100000)) def f(): return [x for x in list_1 if x in s] def g(): return [x for x in list_1 if x in set(list_2)] def h(): return [x for x in list_1 if x in {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}] %timeit f() 100 loops, best of 3: 7.31 ms per loop %timeit g() 10 loops, best of 3: 77.4 ms per loop %timeit h() 100 loops, best of 3: 6.66 ms per loop 

Yes, python (3.3) can optimize a given literal. It is even faster than f() in this case, apparently because it replaces a LOAD_GLOBAL with LOAD_FAST .

 #python 2.7.5+ %timeit h() 10 loops, best of 3: 72.5 ms per loop 

Python 2 in particular does not do this optimization. I tried again to examine what python3 does, but unfortunately dis.dis cannot examine the insides of understanding expressions. Basically, everything interesting turns into MAKE_FUNCTION .

So now I'm wondering - why does python 3.x optimize the given literal only for assembly once, but not set(list_2) ?

Answer 1

To optimize set(list_2) , the interpreter must prove that list_2 (and all its elements) does not change between iterations. This is a difficult problem in the general case, and it won’t surprise me if the interpreter doesn’t even try to solve it.

On the other hand, a set of literals cannot change its meaning between iterations, therefore optimization is known to be safe.

Answer 2

From What's New in Python 3.2 :

The Pythons peephole optimizer now recognizes patterns such as x in {1, 2, 3} as a test for membership in a set of constants. The optimizer reinstalls the set as a freezonet and saves a pre-created constant.

Answer 3

So now I am wondering - why can python 3.x optimize literal setup only for assembly once but not installed (list_2)?

No one has mentioned this problem yet: how do you know that set([1,2,3]) and {1, 2, 3} are the same thing?

 >>> import random >>> def set(arg): ... return [random.choice(range(5))] ... >>> list1 = list(range(5)) >>> [x for x in list1 if x in set(list1)] [0, 4] >>> [x for x in list1 if x in set(list1)] [0] 

You cannot obscure a literal; you can shadow set . Therefore, before you can consider the climb, you need to know not only that list1 not affected, you must be sure that set is what you think. Sometimes you can do this, either under limited conditions at compile time, or more conveniently at runtime, but it is definitely non-trivial.

This is ridiculous: often, when there is a proposal to make such optimizations, one pushback is as good as them, it makes it difficult to discuss how Python performance will look, even algorithmically. Your question provides some evidence for this objection.

Answer 4

Too long to comment

This does not mean optimization details or differences between v2 vs. v3. But when I come across this in some situations, I find that creating a context manager from a data object is useful:

 class context_set(set): def __enter__(self): return self def __exit__(self, *args): pass def context_version(): with context_set(list_2) as s: return [x for x in list_1 if x in s] 

Using this, I see:

 In [180]: %timeit context_version() 100 loops, best of 3: 17.8 ms per loop 

and in some cases, it provides a good gap between creating an object before understanding and creating it within the framework of understanding and allows you to use a special break code if you want to.

A more general version can be done using contextlib.contextmanager . Here is a quick and dirty version of what I mean.

 def context(some_type): from contextlib import contextmanager generator_apply_type = lambda x: (some_type(y) for y in (x,)) return contextmanager(generator_apply_type) 

Then you can do:

 with context(set)(list_2) as s: # ... 

or just as easy

 with context(tuple)(list_2) as t: # ... 

Answer 5

The main reason is that the literal cannot really change, whereas if it is an expression of type set(list_2) , it is possible that evaluating the target expression or iterability of understanding can change the value of set(list_2) . For example, if you have

 [f(x) for x in list_1 if x in set(list_2)] 

It is possible that f modifies list_2 .

Even for a simple expression [x for x in blah ...] theoretically possible that the __iter__ blah method can change list_2 .

I would suggest that there are some possibilities for optimization, but the current behavior simplifies the job. If you start adding optimization for things like “it is evaluated only once, if the target expression is the only voice, and the iterable one is the built-in list or dict ...”, you make it very difficult to figure out what will happen in any given situation.