我编写了一些代码来测试在搜索列表中的元素时哪种方法更快。结果表明,bisect是最快的。但我不明白bisect算法的复杂度是什么,它是否使用Van Emde Boas树?
#python inbuilt list search using 'in' took 0.0702499200317 secs
def mul3():
a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
for x in a:
if x in a:
print x, "True"
else:
print x, "False"
#using bisect took 0.0649611193601
def mul4():
a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
import bisect
for x in a:
locate = bisect.bisect_left(a, x)
if locate == len(a) or a[locate] != x:
print False
print True
#using binary search took 0.0651483638284
a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
for x in a:
lo = 0
hi = 18
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
print True
lo = hi
Reference: http://docs.python.org/library/bisect.html
dict
基本上是O(1)的。如果要求足够严格,二分查找已经不可行了(即使有数十亿个元素,O(log N)已经非常好了),难道你不想节省大量的空间和时间,而不是用Python编写它吗? - user395760list
搜索将受到元素顺序的影响,因此为了获得统计意义的结果,你需要随机化元素的顺序。 - martineau