为什么会有人检查'x in list'？

Question

在Python中，可以使用in-operator非常容易地检查值是否包含在容器中。我想知道为什么有人会在列表上使用in-operator，而首先将列表转换成这样的集合要高效得多：

if x in [1,2,3]:

而不是

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

在查看time complexity时，第一个具有O(n)，而第二个优于O(1)。使用第一种方法的唯一原因是它的可读性更好，编写起来也更简短吗？或者有没有特殊的情况下使用它更实用？为什么Python开发人员不先将第一个实现为第二个？这不是大大提高了它们的O(1)复杂度吗？

Answer 1

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

不会比

if x in [1,2,3]:

将列表转换为集合需要迭代列表，因此至少需要O(n)时间。*在实践中，它比搜索项花费的时间要长得多，因为它涉及散列，然后插入每一项。

当集合被转换一次，然后多次检查时，使用集合是有效的。实际上，通过在列表range(1000)中搜索500来尝试这一点表明，您至少检查了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)操作。

Answer 2

让我们来测试一下你的假设：

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()比使用list慢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的右侧更大，则结论将非常不同。

底线：

在优化之前，不要在实际输入上优化prematurely.

• Always配置文件。

1. 。

Answer 3

如果你想做微优化，你必须衡量：

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