Uma operação razoavelmente comum é filtrar umlist baseado em outrolist. As pessoas rapidamente acham que isso:

[x for x in list_1 if x in list_2]

é lento para grandes entradas - é O (n * m). Que nojo. Como aceleramos isso? Use umset para fazer pesquisas de filtragem O (1):

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

Isso fornece um bom comportamento geral de O (n). No entanto, muitas vezes vejo até mesmo codificadores veteranos cair ema Armadilha™:

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

Ack! Isso é novamente O (n * m), já que o python constróiset(list_2) cada tempo, não apenas uma vez.

Eu pensei que era o fim da história - python não pode otimizá-lo para apenas construir oset uma vez. Apenas esteja ciente da armadilha. Tenho que viver com isso. Hmm.

#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

Huh, python (3.3)posso otimizar um literal conjunto. É ainda mais rápido quef() neste caso, presumivelmente porque ele substitui umLOAD_GLOBAL com umLOAD_FAST.

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

O Python 2 notavelmente não faz essa otimização. Eu tentei investigar mais o que python3 está fazendo, mas infelizmentedis.dis não pode sondar as vísceras das expressões de compreensão. Basicamente tudo interessante se transforma emMAKE_FUNCTION.

Então, agora eu estou querendo saber - por que o python 3.x pode otimizar o literal do conjunto para construir apenas uma vez, mas nãoset(list_2)?