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

Question

在Python中,可以使用in-operator 非常容易地检查容器中是否包含值.我想知道为什么有人会in在列表中使用-operator,但是当首次将列表转换为集合时,它会更有效:

if x in [1,2,3]:

而不是

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

在查看时间复杂度时,第一个具有O(n)而第二个在O(1)处优越.使用第一个的唯一原因是它的可读性和写入时间更短吗？或者是否有一个特殊情况下使用它更实用？为什么Python开发人员没有实现第一个,首先将它转换为第二个？这不会使O(1)的复杂性变得很大吗？

Answer 1

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)操作.