фильтрация понимания списка - " ловушка набора() "

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

[x for x in list_1 if x in list_2]

медленно для больших входов-Это 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) время, а не только один раз.

я думал, что это конец истории-python не может оптимизировать его, чтобы только построить 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

да, в Python (3.3) можете оптимизируйте литерал набора. Это даже быстрее, чем f() в этом случае, по-видимому, потому, что он получает, чтобы заменить LOAD_GLOBAL С a 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.х оптимизировать набор литералов, чтобы построить только один раз, но не set(list_2)?

5 62
python python-3.x python-internals

5 ответов:

для оптимизации set(list_2), интерпретатор должен доказать, что list_2 (и все его элементы) не изменяется между итерациями. Это сложная проблема в общем случае, и меня не удивит, если переводчик даже не попытается ее решить.

48

С Что нового в Python 3.2:

оптимизатор глазка Python теперь распознает такие шаблоны x in {1, 2, 3} как тест на принадлежность к набору констант. Оптимизатор преобразует набор в замороженный и сохраняет предварительно построенную константу.

38

так что теперь мне интересно-почему python 3.х оптимизировать набор литерал построить только один раз, но не установить(list_2)?

никто еще не упоминал об этом вопросе: как вы знаете set([1,2,3]) и {1, 2, 3} это одно и то же?

>>> 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]

вы не можете затенять литерал; вы можете затенять set. Поэтому, прежде чем вы сможете рассмотреть вопрос о подъеме, вам нужно знать не только это list1 не влияет, вы должны быть уверены, что set - это то, что ты думаешь. Иногда вы можете сделать это либо в ограничительных условиях во время компиляции, либо более удобно во время выполнения, но это определенно нетривиально.

это забавно: часто, когда появляется предложение сделать оптимизацию, как это, один откат-это то, что так же хорошо, как и они, это затрудняет рассуждение о том, что производительность Python будет похожа, даже алгоритмически. Ваш вопрос дает некоторые доказательства этого возражения.

18

слишком долго для комментария

это не будет говорить об оптимизации деталей или V2 против V3 различия. Но когда я сталкиваюсь с этим в некоторых ситуациях, я считаю, что создание контекстного менеджера из объекта данных полезно:

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]

используя это я вижу:

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

и в некоторых случаях он обеспечивает хороший стоп-зазор между созданием объекта до понимания и созданием его в рамках понимания, а также позволяет пользовательский код разрыва, если ты хочешь этого.

более общая версия может быть сделано с помощью contextlib.contextmanager. Вот быстрая и грязная версия того, что я имею в виду.

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)

тогда можно сделать:

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

и

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

основная причина заключается в том, что литерал действительно не может измениться, тогда как если это выражение типа set(list_2), возможно, что оценка целевого выражения или итерации понимания может изменить значение set(list_2). Например, если у вас есть

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

возможно, что f изменение list_2.

даже для простого [x for x in blah ...] выражение, теоретически возможно, что __iter__ метод blah изменить list_2.

Я бы предположил, что есть некоторые возможности для оптимизации, но текущее поведение делает вещи проще. Если вы начинаете добавлять оптимизации для таких вещей, как "он вычисляется только один раз, если целевое выражение представляет собой одно голое имя, а iterable-это встроенный список или dict..."вы значительно усложняете понимание того, что произойдет в той или иной ситуации.

10