Listenverständnisfilterung - „die set () - Falle“

Eine vernünftigerweise übliche Operation besteht darin, eine zu filternlist basierend auf einem anderenlist. Die Leute finden schnell, dass dies:

[x for x in list_1 if x in list_2]

ist langsam für große Eingaben - es ist O (n * m). Yuck. Wie beschleunigen wir das? Verwenden einset Filter-Lookups O (1) erstellen:

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

Dies ergibt insgesamt ein gutes O (n) -Verhalten. Ich sehe jedoch oft sogar erfahrene Programmierer hineinfallenDie Falle™:

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

Ack! Dies ist wieder O (n * m), da Python erstellt wirdset(list_2) jeden Zeit, nicht nur einmal.

Ich dachte, das wäre das Ende der Geschichte - Python kann es nicht wegoptimieren, um nur das zu bauenset Einmal. Seien Sie sich der Fallstricke bewusst. Ich muss damit leben. 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)können ein gesetztes Literal wegoptimieren. Es ist noch schneller alsf() in diesem Fall vermutlich, weil es a zu ersetzen bekommtLOAD_GLOBAL mit einerLOAD_FAST.

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

Python 2 führt diese Optimierung insbesondere nicht durch. Ich habe versucht weiter zu untersuchen, was Python3 tut, aber leiderdis.dis Ich kann die Innereien von Verständnisausdrücken nicht untersuchen. Grundsätzlich wird alles Interessante zuMAKE_FUNCTION.

Jetzt frage ich mich also, warum kann Python 3.x das Set-Literal so optimieren, dass es nur einmal erstellt wird, aber nichtset(list_2)?