in和index函数的列表[Python]

Question

我试图了解in命令和index()列表数据结构的内部工作.

当我说:

if something not in some_list :
    print "do something"

它是在内部遍历整个列表,类似于for循环还是它使用,更好的方法,如hashtables等.

index()如果项目不在列表中,则in列表中也会出错.既是工作in和index()一样的吗？如果index()更好,那么当项目不存在时是否可以捕获错误,如果可能的话,它是否是良好的编程？

Answer 1

好问题!是的,你提到的两种方法都必须迭代列表. Python不对列表使用哈希表,因为列表元素没有限制可以清除.

如果您了解"Big O"表示法,则list数据结构是通过查找已知索引来设计O(1)访问的,例如my_list[13].对于成员资格测试,它是O(n).

有其为O(1)速度的成员资格测试(即优化其它数据结构__contains__),即set和dict.这些都是用哈希表实现的.

下面是一个示例,说明如何使用它IPython来验证集合和列表的时间复杂度,以确认这些声明:

In [1]: short_list, long_list = range(1000), range(10000)

In [2]: timeit 'potato' not in short_list
10000 loops, best of 3: 40.9 µs per loop

In [3]: timeit 'potato' not in long_list
1000 loops, best of 3: 440 µs per loop

In [4]: small_set, big_set = set(short_list), set(long_list)

In [5]: timeit 'potato' not in small_set
10000000 loops, best of 3: 72.9 ns per loop

In [6]: timeit 'potato' not in big_set
10000000 loops, best of 3: 84.5 ns per loop