python之在 Python 中的一组许多 "range"对象中搜索值的最快方法是什么

我有一个像这样的许多 Python 对象的列表:

class RangeClass(object): 
 
    def __init__(self,address,size): 
        self.address=address 
        self.size=size 
        #other attributes and methods... 

然后，我有一个 RangeClass 对象的列表(范围列表)。

我需要找到给定值在哪个范围内。

我可以使用这样的代码:

for r in ragelist: 
    if(value>=r.address and value<(r.address+r.size)): 
        return r 
return None 

但我认为有更快的方法。范围具有任意大小，但我们可以假设它们不重叠。

谢谢。

请您参考如下方法:

如果您有很多值要测试，那么您可以使用 bisect module以更快地找到值所在的范围。

如果

• m = 要测试的值的数量，以及
• n = len(rangelist)

然后按照您的建议遍历值和范围列表需要 O(m*n)时间。

如果你使用二分法，那么你必须先对起始地址O(nlogn)进行排序并在范围列表中找到每个值的位置 O(m*logn) . 所以如果

O(nlogn + m*logn) < O(m*n) 

然后平分获胜。对于大n , O(m*logn)与 O(m*n) 相比微不足道. 所以如果

O(nlogn) < O(m*n) 

或等效地，当

C log(n) < m 

对于一些常量 C。

因此，当n很大而且C log(n) < m , 你可以尝试类似的东西

import bisect 
 
class RangeClass(object): 
 
    def __init__(self,address,size): 
        self.address=address 
        self.size=size 
    def __str__(self): 
        return '[{0},{1})'.format(self.address,self.address+self.size) 
    def __lt__(self,other): 
        return self.address<other.address 
 
rangelist=sorted([RangeClass(i,1) for i in (1,3,4,5,7.5)]) 
starts=[r.address for r in rangelist] 
 
def find_range(value): 
    start_idx=bisect.bisect(starts,value)-1 
    try: 
        r=rangelist[start_idx] 
    except IndexError: 
        return None 
    start=r.address 
    end=r.address+r.size 
    if start<=value<end: 
        return rangelist[start_idx] 
    return None     
 
print(','.join(str(r) for r in rangelist)) 
 
for value in (0,1,1.5,2,3,4,5,6,7,8,9,10): 
    r=find_range(value) 
    if r: 
        print('{v} in {r}'.format(v=value,r=str(r))) 
    else: 
        print('{v} not in any range'.format(v=value))