python - 与列表搜索和集合搜索相比，为什么字符串搜索最快？

Question

我正在解决一些竞争性编码挑战。我的解决方案在列表中搜索时超过时间限制，但在字符串中搜索时被接受。

下面是一个示例代码:

代码

import timeit

list = timeit.Timer("'A' in list('AEIOU')")
set = timeit.Timer("'A' in set('AEIOU')")
string = timeit.Timer("'A' in 'AEIOU'")

print 'List search :',list.timeit(999999)
print 'Set search',set.timeit(999999)
print 'String search',string.timeit(999999)

输出

List search : 1.0873670578
Set search 1.0083398819
String search 0.0997061729431

*此输出是在ideone.com 中获得的... http://ideone.com/5FxkX2
**输出可能因系统而异，但趋势相同。

我发现字符串搜索速度快得令人难以置信。我用谷歌搜索但没有找到令人满意的理由。请帮我理解为什么字符串搜索最快？

Answer 1

您的测试有偏差，您需要使用 setup 参数来忽略 create list 或 set< 的时间

>>> timeit.timeit("'A' in l", "l = list('AEIOU')")
0.06389708405846951
>>> timeit.timeit("'A' in s", "s = set('AEIOU')")
0.05960524183085081
>>> timeit.timeit("'A' in s", "s = 'AEIOU'")
0.05756433387793081

也就是说，str 和 list 的 in 操作是线性 O(N) 和 set 是常量 O(1)(忽略大量哈希冲突)。因此，对于更大的示例，set 将是最快的，而 str 和 list 将非常相似。