목록 이해 필터링-“set () 트랩”

목록 이해 필터링-“set () 트랩”

---

합리적으로 일반적인 작업은 list다른 항목을 기준으로 필터링 하는 것 list입니다. 사람들은 다음을 빠르게 발견합니다.

[x for x in list_1 if x in list_2]

큰 입력의 경우 느립니다-O (n * m)입니다. 왝. 속도를 높이려면 어떻게해야합니까? a set를 사용하여 필터링 조회 O (1) :

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

이것은 전반적으로 좋은 O (n) 동작을 제공합니다. 그러나 저는 베테랑 코더조차도 The Trap ™에 빠지는 것을 자주 봅니다 .

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

Ack! 파이썬은 한 번만이 아니라 set(list_2) 매번 빌드되기 때문에 이것은 다시 O (n * m) 입니다.

---

나는 그것이 이야기의 끝이라고 생각했습니다. 파이썬은 단 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_GLOBALa를 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.

그래서 지금 궁금합니다-왜 파이썬 3.x가 세트 리터럴을 최적화하여 한 번만 빌드 할 수 set(list_2)있습니까?

---

최적화하기 위해 set(list_2)인터프리터는 list_2(및 모든 요소) 반복 사이에 변경되지 않음 을 증명해야합니다 . 이것은 일반적인 경우에 어려운 문제이며, 통역사가 그것을 다루려고 시도조차하지 않는다고해도 놀라지 않을 것입니다.

반면에 세트 리터럴은 반복 사이에 값을 변경할 수 없으므로 최적화는 안전한 것으로 알려져 있습니다.

---

에서 의 새로운에서 파이썬 3.2 :

Python의 틈새 최적화 프로그램은 이제 x in {1, 2, 3}상수 집합의 멤버 자격 테스트 와 같은 패턴을 인식합니다 . 옵티마이 저는 세트를 frozenset으로 다시 캐스팅하고 미리 빌드 된 상수를 저장합니다.

---

그래서 지금 궁금합니다-왜 파이썬 3.x는 set (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 성능이 어떤 것인지 추론하기 어렵게 만든다는 것이다. 귀하의 질문은이 반대에 대한 몇 가지 증거를 제공합니다.

---

댓글이 너무 깁니다.

This won't speak to the optimization details or v2 vs. v3 differences. But when I encounter this in some situations, I find making a context manager out of the data object is useful:

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]

Using this I see:

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

and in some cases, it provides a nice stop-gap between creating the object before the comprehension vs. creating it within the comprehension, and allows custom tear-down code if you want it.

A more generic version can be made using contextlib.contextmanager. Here's a quick-and-dirty version of what I mean.

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)

Then one can do:

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

or just as easily

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

---

The basic reason is that a literal really can't change, whereas if it's an expression like set(list_2), it's possible that evaluating the target expression or the iterable of the comprehension could change the value of set(list_2). For instance, if you have

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

It is possible that f modifies list_2.

Even for a simple [x for x in blah ...] expression, it's theoretically possible that the __iter__ method of blah could modify list_2.

I would imagine there is some scope for optimizations, but the current behavior keeps things simpler. If you start adding optimizations for things like "it is only evaluated once if the target expression is a single bare name and the iterable is a builtin list or dict..." you make it much more complicated to figure out what will happen in any given situation.

참고URL : https://stackoverflow.com/questions/20056458/list-comprehension-filtering-the-set-trap