Каков наиболее эффективный алгоритм / структура данных для поиска наименьшего диапазона, содержащего точку?
Учитывая набор данных из нескольких миллионов ценовых диапазонов, нам нужно найти наименьший диапазон, который содержит данную цену.
Применяются следующие правила:
- Диапазоны могут быть полностью вложенными (то есть 1-10 и 5-10 действительны)
- Диапазоны не могут быть частично вложенными (то есть 1-10 и 5-15 недопустимы)
Пример:
Учитывая следующие ценовые диапазоны:
- 1-100
- 50-100
- 100-120
- 5-10
- 5-20
Результат поиска цены 7 должен быть 5-10
Результат поиска цены 100 должен быть 100-120 (наименьший диапазон, содержащий 100).
Какой алгоритм / структура данных наиболее эффективен для реализации этого?
Ища в Интернете, я нашел только решения для поиска диапазонов в пределах диапазонов.
Я смотрел на счет Мортона и кривую Гильберта, но не могу понять, как их использовать для этого случая.
Благодарю.
4 ответа
Поскольку вы не упомянули этот специальный алгоритм, я предложу это в качестве простого ответа на ваш вопрос:
Это функция Python, но ее довольно легко понять и преобразовать на другом языке.
def min_range(ranges, value):
# ranges = [(1, 100), (50, 100), (100, 120), (5, 10), (5, 20)]
# value = 100
# INIT
import math
best_range = None
best_range_len = math.inf
# LOOP THROUGH ALL RANGES
for b, e in ranges:
# PICK THE SMALLEST
if b <= value <= e and e - b < best_range_len:
best_range = (b, e)
best_range_len = e - b
print(f'Minimal range containing {value} = {best_range}')
Я считаю, что есть более эффективные и сложные решения (если вы можете сделать некоторые предварительные вычисления, например), но это первый шаг, который вы должны сделать.
РЕДАКТИРОВАТЬ: Вот лучшее решение, вероятно, в O(log (n)), но это не тривиально. Это дерево, где каждый узел является интервалом и имеет дочерний список всех строго не перекрывающихся интервалов, которые содержатся внутри него. Предварительная обработка выполняется за время O(n log (n)), а в худшем случае запросы O(n) (когда вы не можете найти 2 диапазона, которые не перекрываются) и, возможно, в среднем O(log (n)).
2 класса: Дерево, которое содержит дерево и может запрашивать:
class tree:
def __init__(self, ranges):
# sort the ranges by lowest starting and then greatest ending
ranges = sorted(ranges, key=lambda i: (i[0], -i[1]))
# recursive building -> might want to optimize that in python
self.node = node( (-float('inf'), float('inf')) , ranges)
def __str__(self):
return str(self.node)
def query(self, value):
# bisect is for binary search
import bisect
curr_sol = self.node.inter
node_list = self.node.child_list
while True:
# which of the child ranges can include our value ?
i = bisect.bisect_left(node_list, (value, float('inf'))) - 1
# does it includes it ?
if i < 0 or i == len(node_list):
return curr_sol
if value > node_list[i].inter[1]:
return curr_sol
else:
# if it does then go deeper
curr_sol = node_list[i].inter
node_list = node_list[i].child_list
Узел, который содержит структуру и информацию:
class node:
def __init__(self, inter, ranges):
# all elements in ranges will be descendant of this node !
import bisect
self.inter = inter
self.child_list = []
for i, r in enumerate(ranges):
if len(self.child_list) == 0:
# append a new child when list is empty
self.child_list.append(node(r, ranges[i + 1:bisect.bisect_left(ranges, (r[1], r[1] - 1))]))
else:
# the current range r is included in a previous range
# r is not a child of self but a descendant !
if r[0] < self.child_list[-1].inter[1]:
continue
# else -> this is a new child
self.child_list.append(node(r, ranges[i + 1:bisect.bisect_left(ranges, (r[1], r[1] - 1))]))
def __str__(self):
# fancy
return f'{self.inter} : [{", ".join([str(n) for n in self.child_list])}]'
def __lt__(self, other):
# this is '<' operator -> for bisect to compare our items
return self.inter < other
и проверить это:
ranges = [(1, 100), (50, 100), (100, 120), (5, 10), (5, 20), (50, 51)]
t = tree(ranges)
print(t)
print(t.query(10))
print(t.query(5))
print(t.query(40))
print(t.query(50))
Предварительная обработка, которая генерирует разделенные интервалы
(Я называю исходные сегменты как диапазоны, а результирующие сегменты - как интервалы)
Для любой границы диапазона (как начала, так и конца) сделайте кортеж: (значение, начальное / конечное поля, длина диапазона, идентификатор), поместите их в массив / список
Сортируйте эти кортежи по первому полю. В случае ничьей увеличьте диапазон влево для начала и вправо для конца.
Make a stack
Make StartValue variable.
Walk through the list:
if current tuple contains start:
if interval is opened: //we close it
if current value > StartValue: //interval is not empty
make interval with //note id remains in stack
(start=StartValue, end = current value, id = stack.peek)
add interval to result list
StartValue = current value //we open new interval
push id from current tuple onto stack
else: //end of range
if current value > StartValue: //interval is not empty
make interval with //note id is removed from stack
(start=StartValue, end = current value, id = stack.pop)
add interval to result list
if stack is not empty:
StartValue = current value //we open new interval
После этого мы отсортировали список разделенных интервалов, содержащих начальное / конечное значение и идентификатор диапазона источника (обратите внимание, что многие интервалы могут соответствовать одному и тому же диапазону источника), поэтому мы можем легко использовать бинарный поиск.
Если мы добавим исходные диапазоны по одному во вложенном порядке (вложенные после родительского), мы увидим, что каждый новый диапазон может генерировать не более двух новых интервалов, поэтому общее количество интервалов M <= 2*N и общая сложность O(Nlog N + Q * logN) где Q - количество запросов
Редактировать: Добавлено if stack is not empty раздел
Результат для вашего примера 1-100, 50-100, 100-120, 5-10, 5-20:
1-5(0), 5-10(3), 10-20(4), 20-50(0), 50-100(1), 100-120(2)
Как насчет такого подхода? Так как мы допускаем только вложенные, а не частичные. Это выглядит выполнимым подходом.
- Разделить сегменты на
(left,val)а также(right,val)пар. - Заказать их по отношению к их
valsи левое / правое отношение. - Поиск в списке с помощью бинарного поиска. Мы получаем два результата, которые не найдены и не найдены.
- Если найдено, проверьте, левое или правое. Если это левый, идите направо, пока не найдете право, не найдя налево. Если это право, идите налево, пока не найдете левое, не найдя правое. Выберите самый маленький.
- Если не найдено, остановитесь, когда
high-lowравен 1 или 0. Затем сравните запрашиваемое значение со значением узла, в котором вы находитесь, и затем в соответствии с этим поиском направо и налево, как и прежде.
В качестве примера;
Мы бы хотели иметь (l,10) (l,20) (l,30) (r,45) (r,60) (r,100) при поиске, скажем, 65 вы падаете на (r,100) так что вы идете налево и не можете найти место с (l,x) такой, что x>=65 так что вы идете налево, пока не получите сбалансированные левые и права, а первый правый и последний левый - ваш интервал. Часть повторной обработки будет длинной, но так как вы будете продолжать в том же духе. Это все еще O(n) в худшем случае. Но этот худший случай требует, чтобы вы вложили все друг в друга и искали самое внешнее.
Поскольку pLOPeGG уже рассмотрел специальный случай, я отвечу на вопрос, исходя из того, что предварительная обработка выполняется для эффективной поддержки нескольких запросов.
Общими структурами данных для эффективных запросов по интервалам являются дерево интервалов и дерево сегментов