4

在 Python 中，使用 -operator 可以很容易地检查一个值是否包含在容器中in。我想知道为什么有人会in在列表上使用 -operator，但是，首先将列表转换为这样的集合会更有效：

if x in [1,2,3]:

与

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

在查看时间复杂度时，第一个具有 O(n)，而第二个在 O(1) 上更胜一筹。使用第一个的唯一原因是它更易读且写起来更短吗？或者有没有更实用的特殊情况？为什么 Python 开发人员没有通过首先将第一个转换为第二个来实现第一个？这难道不是 O(1) 复杂度吗？

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

为了将列表转换为集合，您需要遍历列表的元素，这O(n)最多需要时间。我相信 Python 集由哈希映射支持，这意味着它们实际上也具有O(n)查找操作的最坏情况时间复杂度。

他们的维基似乎同意这一点。

于 2013-01-26T13:10:04.590 回答
0

因为将列表转换为集合需要遍历整个列表，这与测试列表是否包含值的复杂性相当。

所以测试一个值是否在一个集合中会更快，只有这个集合已经被构造了。

于 2013-01-26T13:10:36.020 回答
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 回答