Вы можете иметь O (1) время поиска, если вы принимаете низкое (er) разрешение границ диапазона и жертвуете памятью для скорости поиска.
Словарь может выполнять поиск за среднее время O (1), поскольку существует простая арифметическая связь между ключом и местоположением в структуре данных фиксированного размера (hash(key) % tablesize, для среднего случая). Ваши диапазоны по сути имеют переменный размер с границами с плавающей точкой, поэтому нет фиксированного размера таблицы для сопоставления поискового значения.
Если вы не ограничиваете абсолютные нижнюю и верхнюю границы диапазонов и позволяете границам диапазонов находиться на фиксированном размере шага. В вашем примере используются значения от 0,0 до 1,0, а диапазоны можно квантовать с шагом 0,05. Это можно превратить в фиксированный стол:
import math
from collections import MutableMapping
# empty slot marker
_EMPTY = object()
class RangeMap(MutableMapping):
"""Map points to values, and find values for points in O(1) constant time
The map requires a fixed minimum lower and maximum upper bound for
the ranges. Range boundaries are quantized to a fixed step size. Gaps
are permitted, when setting overlapping ranges last range set wins.
"""
def __init__(self, map=None, lower=0.0, upper=1.0, step=0.05):
self._mag = 10 ** -round(math.log10(step) - 1) # shift to integers
self._lower, self._upper = round(lower * self._mag), round(upper * self._mag)
self._step = round(step * self._mag)
self._steps = (self._upper - self._lower) // self._step
self._table = [_EMPTY] * self._steps
self._len = 0
if map is not None:
self.update(map)
def __len__(self):
return self._len
def _map_range(self, r):
low, high = r
start = round(low * self._mag) // self._step
stop = round(high * self._mag) // self._step
if not self._lower <= start < stop <= self._upper:
raise IndexError('Range outside of map boundaries')
return range(start - self._lower, stop - self._lower)
def __setitem__(self, r, value):
for i in self._map_range(r):
self._len += int(self._table[i] is _EMPTY)
self._table[i] = value
def __delitem__(self, r):
for i in self._map_range(r):
self._len -= int(self._table[i] is not _EMPTY)
self._table[i] = _EMPTY
def _point_to_index(self, point):
point = round(point * self._mag)
if not self._lower <= point <= self._upper:
raise IndexError('Point outside of map boundaries')
return (point - self._lower) // self._step
def __getitem__(self, point_or_range):
if isinstance(point_or_range, tuple):
low, high = point_or_range
r = self._map_range(point_or_range)
# all points in the range must point to the same value
value = self._table[r[0]]
if value is _EMPTY or any(self._table[i] != value for i in r):
raise IndexError('Not a range for a single value')
else:
value = self._table[self._point_to_index(point_or_range)]
if value is _EMPTY:
raise IndexError('Point not in map')
return value
def __iter__(self):
low = None
value = _EMPTY
for i, v in enumerate(self._table):
pos = (self._lower + (i * self._step)) / self._mag
if v is _EMPTY:
if low is not None:
yield (low, pos)
low = None
elif v != value:
if low is not None:
yield (low, pos)
low = pos
value = v
if low is not None:
yield (low, self._upper / self._mag)
Вышеприведенный реализует полный интерфейс отображения и принимает как точки, так и диапазоны (как кортеж, моделирующий интервал [start, stop)) при индексировании или проверке на содержание (поддержка диапазонов облегчает повторное использование словаря ключей, значений и элементов по умолчанию) просмотреть реализации, которые все работают из реализации __iter__).
Демо-версия:
>>> d = RangeMap({
... (0.0, 0.1): "a",
... (0.1, 0.3): "b",
... (0.3, 0.55): "c",
... (0.55, 0.7): "d",
... (0.7, 1.0): "e",
... })
>>> print(*d.items(), sep='\n')
((0.0, 0.1), 'a')
((0.1, 0.3), 'b')
((0.3, 0.55), 'c')
((0.55, 0.7), 'd')
((0.7, 1.0), 'e')
>>> d[0.05]
'a'
>>> d[0.8]
'e'
>>> d[0.9]
'e'
>>> import random
>>> d[random.random()]
'c'
>>> d[random.random()]
'a'
Если вы не можете так легко ограничить размер шага и границы, то ваш следующий лучший вариант - использовать какой-то алгоритм двоичного поиска ; вы сохраняете диапазоны в отсортированном порядке и выбираете точку в середине структуры данных; основываясь на том, что ваш ключ поиска выше или ниже этой средней точки, вы продолжаете поиск в любой половине структуры данных, пока не найдете совпадение.
Если ваши диапазоны охватывают полный интервал от самой низкой до самой высокой границы, то вы можете использовать для этого модуль bisect ; просто сохраните нижнюю или верхнюю границы каждого диапазона в одном списке, соответствующие значения в другом, и используйте разделение пополам, чтобы сопоставить позицию в первом списке с результатом во втором.
Если ваши диапазоны имеют пробелов , то вам нужно либо сохранить третий список с другой границей и сначала подтвердить, что точка попадает в диапазон, либо использовать дерево интервалов, Для неперекрывающихся диапазонов подойдет простое двоичное дерево, но есть и более специализированные реализации, которые также поддерживают перекрывающиеся диапазоны. Существует intervaltree проект на PyPI, который поддерживает операции с полными интервалами дерева.
Отображение на основе bisect, которое соответствует поведению реализации фиксированной таблицы, будет выглядеть следующим образом:
from bisect import bisect_left
from collections.abc import MutableMapping
class RangeBisection(MutableMapping):
"""Map ranges to values
Lookups are done in O(logN) time. There are no limits set on the upper or
lower bounds of the ranges, but ranges must not overlap.
"""
def __init__(self, map=None):
self._upper = []
self._lower = []
self._values = []
if map is not None:
self.update(map)
def __len__(self):
return len(self._values)
def __getitem__(self, point_or_range):
if isinstance(point_or_range, tuple):
low, high = point_or_range
i = bisect_left(self._upper, high)
point = low
else:
point = point_or_range
i = bisect_left(self._upper, point)
if i >= len(self._values) or self._lower[i] > point:
raise IndexError(point_or_range)
return self._values[i]
def __setitem__(self, r, value):
lower, upper = r
i = bisect_left(self._upper, upper)
if i < len(self._values) and self._lower[i] < upper:
raise IndexError('No overlaps permitted')
self._upper.insert(i, upper)
self._lower.insert(i, lower)
self._values.insert(i, value)
def __delitem__(self, r):
lower, upper = r
i = bisect_left(self._upper, upper)
if self._upper[i] != upper or self._lower[i] != lower:
raise IndexError('Range not in map')
del self._upper[i]
del self._lower[i]
del self._values[i]
def __iter__(self):
yield from zip(self._lower, self._upper)