4

In Python one can very easily check if a value is contained in a container by using the in-operator. I was wondering why anyone would ever use the in-operator on a list, though, when it's much more efficient to first transform the list to a set as such:

if x in [1,2,3]:

as opposed to

if x in set([1,2,3]):

When looking at the time complexity, the first one has O(n) while the second one is superior at O(1). Is the only reason to use the first one the fact that it's more readable and shorter to write? Or is there a special case in which it's more practical to use? Why did the Python devs not implement the first one by first translating it to the second one? Would this not grand both of them the O(1) complexity?

4

6 に答える 6

17 
if x in set([1,2,3]):

より速くない

if x in [1,2,3]:

リストをセットに変換するには、リストを反復処理する必要があるため、少なくともO(n)時間がかかります*。

セットを使用すると、セットが一度変換されてから複数回チェックされる場合に効率的です。500実際、リストでを検索してこれを試してみるとrange(1000)、少なくとも 3 回チェックするとトレードオフが発生することがわかります。

import timeit

def time_list(x, lst, num):
    for n in xrange(num):
        x in lst

def time_turn_set(x, lst, num):
    s = set(lst)
    for n in xrange(num):
        x in s

for num in range(1, 10):
    size = 1000
    setup_str = "lst = range(%d); from __main__ import %s"
    print num,
    print timeit.timeit("time_list(%d, lst, %d)" % (size / 2, num),
                        setup=setup_str % (size, "time_list"), number=10000),
    print timeit.timeit("time_turn_set(%d, lst, %d)" % (size / 2, num),
                        setup=setup_str % (size, "time_turn_set"), number=10000)

私に与えます：

1 0.124024152756 0.334127902985
2 0.250166893005 0.343378067017
3 0.359009981155 0.356444835663
4 0.464100837708 0.38081407547
5 0.600295066833 0.34722495079
6 0.692923069 0.358560085297
7 0.787877082825 0.338326931
8 0.877299070358 0.344762086868
9 1.00078821182 0.339591026306

500 から 50000 までの範囲のリスト サイズを使用したテストでは、ほぼ同じ結果が得られます。

* 確かに、真の漸近的な意味では、ハッシュ テーブルへの挿入 (さらに言えば、値のチェック) はO(1)時間ではなく、線形時間の一定のスピードアップですO(n)(リストが大きくなりすぎると衝突が発生するため)。これにより、set([1,2,3])操作O(n^2)は ではなく時間内に行われO(n)ます。ただし、実際には、適切な実装を備えた妥当なサイズのリストを使用すると、基本的に常にハッシュ テーブルの挿入と検索をO(1)操作と見なすことができます。

于 2013-01-26T13:10:11.697 に答える
3

あなたの仮定をテストしましょう：

In [19]: %timeit 1 in [1, 2, 3]
10000000 loops, best of 3: 52.3 ns per loop

In [20]: %timeit 4 in [1, 2, 3]
10000000 loops, best of 3: 118 ns per loop

In [21]: %timeit 1 in set([1, 2, 3])
1000000 loops, best of 3: 552 ns per loop

In [22]: %timeit 4 in set([1, 2, 3])
1000000 loops, best of 3: 558 ns per loop

したがって、あなたの正確な例でset()は、リストを使用するよりも 5 倍から 10 倍遅くなります。

セットを作成するだけで 517 ns かかります。

In [23]: %timeit set([1, 2, 3])
1000000 loops, best of 3: 517 ns per loop

チェックからセットの作成を因数分解しましょう。

In [26]: s = set([1, 2, 3])

In [27]: %timeit 1 in s
10000000 loops, best of 3: 72.5 ns per loop

In [28]: %timeit 4 in s
10000000 loops, best of 3: 71.4 ns per loop

これにより、パフォーマンスの違いが明確ではなくなります。と の相対的なパフォーマンスはlist、setに提示される正確な値に依存しますin。それらがリストに存在し、リストの先頭に近い場合、listおそらく勝ちます。そうでなければ、setおそらく勝つでしょう。

もちろん、 の右辺inが大きければ、結論は大きく異なります。

結論:

  1. 時期尚早に最適化しないでください。
  2. 最適化する前に、常に現実的な入力をプロファイリングしてください。
于 2013-01-26T13:15:25.373 に答える
2

マイクロ最適化を行う場合は、以下を測定する必要があります。

l.py:
for x in range(1000000):
    3 in [1, 2, 3]

s.py:
for x in range(1000000):
    3 in set([1, 2, 3])

~/py $ time python l.py

real    0m0.314s
user    0m0.275s
sys 0m0.030s

~/py $ time python s.py

real    0m1.055s
user    0m1.006s
sys 0m0.029s
于 2013-01-26T13:14:02.193 に答える
0

試してみましょう…</p> 

import cProfile

実際に何かを測定できるように、十分に大きなテスト範囲を選択します。2**13は単なるランダムな値です。

test = range(2**13)
runs = len(test)
wcn  = runs - 1 # worst case n

テスト実行の量はリスト内の数値の量と同じであるため、最終的に適切な平均値を得ることができます。 wcnこれはリストの最後のエントリであり、アルゴリズムがチェックする最後のエントリであるため、最悪のケースです。

def simple():
    for n in range(runs):
        if n in test:
            pass

def simpleWorstCase():
    for n in range(runs):
        if wcn in test:
            pass

def slow():
    for n in range(runs):
        if n in set(test):
            pass

簡単なテストの結果:

cProfile.run('simple()')
"""
         4 function calls in 0.794 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.794    0.794 <string>:1(<module>)
        1    0.794    0.794    0.794    0.794 profile.py:6(simple)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}
"""

単純な最悪のケースのテストの結果:

cProfile.run('simpleWorstCase()')
"""
         4 function calls in 1.462 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.462    1.462 <string>:1(<module>)
        1    1.462    1.462    1.462    1.462 profile.py:12(simpleWorstCase)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}
"""

最初にセットに変換するテストの結果:

cProfile.run('slow()')
"""
         4 function calls in 2.227 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    2.227    2.227 <string>:1(<module>)
        1    2.227    2.227    2.227    2.227 profile.py:11(slow)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {range}
"""
于 2013-01-26T13:22:23.653 に答える
0

リストをセットに変換するには、リストの要素を繰り返し処理する必要がありますが、これにはO(n)せいぜい時間がかかります。Python セットはハッシュ マップに支えられていると思います。つまり、実際にはO(n)ルックアップ操作の最悪の場合の時間の複雑さもあるということです。

彼らのウィキはこれに同意しているようです。

于 2013-01-26T13:10:04.590 に答える
0

リストをセットに変換するには、リスト全体をループする必要があるため、リストに値が含まれているかどうかをテストするのと同じくらい複雑です。

したがって、値がセット内にあるかどうかをテストする方が、セットが既に構築されているだけで高速です。

于 2013-01-26T13:10:36.020 に答える