在Python中，在一组“range”对象中搜索值的最快方法是什么

Question

我有许多Python对象的列表，如下所示：

class RangeClass(object):

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

然后，我有一个RangeClass对象的列表（rangelist）。在

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

我可以用这样的代码：

^{pr2}$

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

谢谢。在

Answer 1

在Range中实现比较运算符，对范围列表进行排序，并使用bisect搜索值所属的范围：

import bisect
def find_range(value):
    index = bisect.bisect(rangelist, value)
    if index not in (0, len(rangelist)):
        index -= 1
    return rangelist[index]

Answer 2

不是真的。您所能做的就是利用Python的关系运算符链接。在

if r.address <= value < (r.address + r.size):

您还可以在RangeClass上定义__contains__，以允许您使用in来查找它。在

^{pr2}$

Answer 3

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

如果

• m=要测试的值的数目，以及
• ^{{cd2>}

然后按照您的建议在值和范围列表中循环将花费O(m*n)时间。在

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

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

然后平分获胜。对于大的n，与O(m*n)相比，O(m*logn)很小。 因此，如果

^{pr2}$

或者等效地，当

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))