68

合理的に一般的な操作はlist、別のものに基づいて1 つをフィ​​ルタリングすること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)]

あっ！Python は 1回だけでなくset(list_2) 毎回ビルドするため、これも O(n*m)です。

私はそれが話の終わりだと思った-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()おそらく aLOAD_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.xはセットリテラルを最適化して1回だけビルドすることができset(list_2)ますか?

4

5 に答える 5

51

を最適化するために、インタープリターは(およびそのすべての要素) が反復間で変化しないことset(list_2)を証明する必要があります。list_2これは一般的なケースでは難しい問題であり、通訳者がそれに取り組もうとさえしなくても、私は驚かないでしょう。

一方、集合リテラルは反復間で値を変更できないため、最適化は安全であることが知られています。

于 2013-11-18T19:52:58.760 に答える
39

Python 3.2 の新機能から:

Python のピープホール オプティマイザーx in {1, 2, 3}は、一連の定数のメンバーシップのテストなどのパターンを認識するようになりました。オプティマイザーは、セットをfrozensetとして再キャストし、事前に構築された定数を保存します。

于 2013-11-18T19:54:34.317 に答える
13

コメントが長すぎる

これは、最適化の詳細や 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:
    # ...
于 2013-11-18T20:22:22.233 に答える
10

基本的な理由は、リテラルは実際には変更できないためですが、 のような式の場合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 ...]式であっても、理論的にはcouldの__iter__メソッドによって変更される可能性があります。blahlist_2

最適化の余地があると思いますが、現在の動作は物事をよりシンプルに保ちます。「ターゲット式が単一の裸の名前であり、イテラブルが組み込みのリストまたは辞書である場合、一度だけ評価される...」などの最適化を追加し始めると、与えられた状況。

于 2013-11-18T19:54:12.173 に答える