У меня есть список интервалов, и мне нужно вернуть те, которые перекрываются с интервалом, переданным в запросе. Что примечательно, так это то, что в типичном запросе около трети или даже половины интервалов перекрываются с интервалом, указанным в запросе. Также соотношение самого короткого интервала к самому длинному не более 1: 5. Я реализовал свое собственное дерево интервалов (расширенное красно-черное дерево) - я не хотел использовать существующие реализации, потому что мне нужна была поддержка закрытых интервалов и некоторые специальные функции. Я проверил скорость запроса с 6000 запросов в дереве с 6000 интервалами (таким образом, n = 6000 и m = 3000 (приложение)). Оказалось, что брутфорс ничем не хуже использования дерева:
Computation time - loop: 125.220461 s
Tree setup: 0.05064 s
Tree Queries: 123.167337 s
Позвольте мне воспользоваться асимптотическим анализом. n: количество запросов; n: количество интервалов; приложение. n / 2: количество интервалов, возвращаемых в запросе:
временная сложность грубой силы: n * n
дерево временной сложности: n * (log (n) + n / 2) -> 1/2 n n + n log (n) -> n * n
Таким образом, результат говорит о том, что эти два значения должны быть примерно одинаковыми для большого n. Тем не менее можно было бы ожидать, что дерево будет заметно быстрее, учитывая константу 1/2 перед n * n. Итак, я могу представить себе три возможных причины полученных результатов:
а) Моя реализация неверна. (Следует ли мне использовать BFS, как показано ниже?) Б) Моя реализация правильная, но я сделал вещи громоздкими для Python, поэтому ему нужно больше времени для работы с деревом, чем для работы с грубой силой. в) все в порядке - так и должно быть при большом n
Моя функция запроса выглядит так:
from collections import deque
def query(self,low,high):
result = []
q = deque([self.root]) # this is the root node in the tree
append_result = result.append
append_q = q.append
pop_left = q.popleft
while q:
node = pop_left() # look at the next node
if node.overlap(low,high): # some overlap?
append_result(node.interval)
if node.low != None and low <= node.get_low_max(): # en-q left node
append_q(node.low)
if node.high != None and node.get_high_min() <= high: # en-q right node
append_q(node.high)
Я строю дерево так:
def build(self, intervals):
"""
Function which is recursively called to build the tree.
"""
if intervals is None:
return None
if len(intervals) > 2: # intervals is always sorted in increasing order
mid = len(intervals)//2
# split intervals into three parts:
# central element (median)
center = intervals[mid]
# left half (<= median)
new_low = intervals[:mid]
#right half (>= median)
new_high = intervals[mid+1:]
#compute max on the lower side (left):
max_low = max([n.get_high() for n in new_low])
#store min on the higher side (right):
min_high = new_high[0].get_low()
elif len(intervals) == 2:
center = intervals[1]
new_low = [intervals[0]]
new_high = None
max_low = intervals[0].get_high()
min_high = None
elif len(intervals) == 1:
center = intervals[0]
new_low = None
new_high = None
max_low = None
min_high = None
else:
raise Exception('The tree is not behaving as it should...')
return(Node(center, self.build(new_low),self.build(new_high),
max_low, min_high))
РЕДАКТИРОВАТЬ:
Узел представлен так:
class Node:
def __init__(self, interval, low, high, max_low, min_high):
self.interval = interval # pointer to corresponding interval object
self.low = low # pointer to node containing intervals to the left
self.high = high # pointer to node containing intervals to the right
self.max_low = max_low # maxiumum value on the left side
self.min_high = min_high # minimum value on the right side
Все узлы в поддереве можно получить следующим образом:
def subtree(current):
node_list = []
if current.low != None:
node_list += subtree(current.low)
node_list += [current]
if current.high != None:
node_list += subtree(current.high)
return node_list
p.s. обратите внимание, что, эксплуатируя то, что существует такое большое перекрытие и что все интервалы имеют сопоставимую длину, мне удалось реализовать простой метод, основанный на сортировке и делении пополам, который завершился за 80 с, но я бы сказал, что это перебор ... Забавно, Используя асимптотический анализ, я обнаружил, что он должен иметь app. та же среда выполнения, что и при использовании дерева ...
