与列表搜索和设置搜索相比,为什么字符串搜索速度最快？

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)

OUTPUT

List search : 1.0873670578
Set search 1.0083398819
String search 0.0997061729431

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

我发现字符串搜索速度非常快.我用谷歌搜索,但没有找到一个令人满意的推理.请帮我理解为什么字符串搜索最快？

Answer 1

您的测试有失偏颇,您需要使用setup参数忽视的时间创建的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

话虽如此,in对str和的操作list是线性的O(N)并且set是恒定的O(1)(忽略了大量的哈希冲突).因此,对于一个更大的例子,set它将是最快的,str并且list将非常相似.