Какой самый быстрый способ поиска значения в наборе множества объектов «range» в Python

Question

У меня есть список многих объектов Python, таких как:

class RangeClass(object):

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

Затем у меня есть список (rangelist) объектов RangeClass.

Мне нужно найти, в каком диапазоне находится данное значение.

Я могу использовать такой код:

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

Но я думаю, что есть более быстрый путь. Диапазоны имеют произвольный размер, но мы можем предположить, что они не перекрываются.

Спасибо.

Answer 1

Если у вас есть много значений для тестирования, вы можете использовать модуль bisect , чтобы быстрее определить, в каком диапазоне находятся значения.

Если

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

Answer 2

Не совсем. Все, что вы можете сделать, это воспользоваться цепочкой реляционных операторов Python.

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

Вы также можете определить __contains__ на RangeClass, чтобы позволить вам использовать in, чтобы найти его вместо этого.

class RangeClass(object):
   ...
  def __contains__(self, val):
    return self.address <= val < (self.address + self.size)

 ...
  if value in r:

Answer 3

Спасибо всем,

Я на самом деле использую метод, предложенный unutbu.

Более того, я добавляю еще одну оптимизацию:

if(value <= first_range_value or value >= last_range_value):
    return None

Где first_range_value и last_range_value были вычислены ранее, и они являются наименьшим значением r.address и наибольшим значением r.address + r.size.

Это стоит в моем приложении, но это действительно зависит от распределения диапазонов и значений.

Answer 4

Реализация оператора сравнения в 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]