Racjonalnie powszechną operacją jest filtrowanie jednegolist oparty na innymlist. Ludzie szybko odkrywają, że to:

[x for x in list_1 if x in list_2]

jest wolny dla dużych wejść - to O (n * m). Fuj. Jak to przyspieszyć? Użyćset aby wyszukać filtrowanie O (1):

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

Daje to dobre ogólne zachowanie O (n). Często jednak widzę, że wpadają nawet weterani koderówPułapka™:

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

Ack! Ponownie jest to O (n * m), ponieważ buduje się pythonset(list_2) każdy czas, nie tylko raz.

Myślałem, że to koniec historii - python nie może go zoptymalizować, aby zbudować tylkoset pewnego razu. Po prostu bądź świadomy pułapki. Muszę z tym żyć. 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)mogą zoptymalizuj dosłowny zestaw. Jest nawet szybszy niżf() w tym przypadku prawdopodobnie dlatego, że zastępujeLOAD_GLOBAL zLOAD_FAST.

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

Python 2 w szczególności nie wykonuje tej optymalizacji. Próbowałem dalej badać, co robi Python, ale niestetydis.dis nie może badać wnętrzności wyrażeń rozumienia. W zasadzie wszystko, co ciekawe, zamienia się wMAKE_FUNCTION.

Teraz zastanawiam się - dlaczego python 3.x może zoptymalizować dosłowny zestaw, aby budować tylko raz, ale nieset(list_2)?