Довольно распространенной операцией является фильтрация одногоlist основанный на другомlist, Люди быстро обнаруживают, что это:

[x for x in list_1 if x in list_2]

медленно для больших входов - этоs O (n * m). Тьфу. Как мы ускорим это? Использоватьset сделать фильтрацию поиска O (1):

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

Это дает хорошее общее O (n) поведение. Однако я часто вижу, что даже ветераныЛовушка ™:

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

Ack! Это опять O (n * m), так как Python собираетset(list_2) каждый время, а не только один раз.

Я думал, что это конец истории - Питон можетоптимизировать его, чтобы только построитьset один раз. Просто знайте о ловушке. Должен жить с этим. Хм.

#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

Да, питон (3.3)Можно оптимизировать множество литералов. Это'даже быстрее чемf() в этом случае, предположительно, потому что он может заменитьLOAD_GLOBAL с.LOAD_FAST

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

Python 2 заметно несделать эту оптимизацию. Я'мы пытались выяснить, что делает python3, но, к сожалению,dis.dis не может исследовать внутренности выражений понимания. В основном все интересное превращается в.MAKE_FUNCTION

Так что теперь яИнтересно - почему Python 3.x может оптимизировать набор литералов, чтобы он собирался только один раз, но не так?set(list_2)