在长排序列表中搜索数字(例如12.31)并在找不到“精确”值(例如列表中的11.12和12.03)之前和之后的“搜索”值之前获取一个值的最快方法是什么以下)?
提前谢谢了。
long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67]
最佳答案
最快的可能是在python中使用内置支持。在这里,我正在考虑bisect模块。下面,我使用字典快速检查O(1)是否在列表中;如果不是,则使用bisect
查找小于和大于搜索值的值。
#!/usr/bin/env python
import bisect
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect.bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect.bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
# First create a test-list (49996 items)
i=1.0
R=[1.0]
D={}
while i < 10000:
i+=0.2
i=round(i,2)
D[i]=True
R.append(i)
# Locate a value, in this case 100.3 which is not in the list
x=100.3
if D.has_key(x):
print "found", x
else:
print find_lt(R, x)
print find_gt(R, x)
x=100.3
的输出:100.2
100.4
关于python - 在长排序列表中搜索值之前和之后,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/6628744/