You can have O(1) lookup time if you accept a low(er) resolution of range boundaries and sacrifice memory for lookup speed.
A dictionary can do a lookup in O(1) average time because there is a simple arithmetic relationship between key and location in a fixed-size data structure (hash(key) % tablesize, for the average case). Your ranges are effectively of a variable size with floating-point boundaries, so there is no fixed tablesize to map a search value to.
Unless, that is, you limit the absolute lower and upper boundaries of the ranges, and let range boundaries fall on a fixed step size. Your example uses values from 0.0 through to 1.0, and the ranges can be quantized to 0.05 steps. That can be turned into a fixed table:
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)
The above implements the full mapping interface, and accepts both points and ranges (as a tuple modelling a [start, stop) interval) when indexing or testing for containment (supporting ranges made it easier to reuse the default keys, values and items dictionary view implementations, which all work from the __iter__ implementation).
Demo:
>>> 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'
If you can't limit the step size and boundaries so readily, then your next best option is to use some kind of binary search algorithm; you keep the ranges in sorted order and pick a point in the middle of the data structure; based on your search key being higher or lower than that mid point you continue the search in either half of the data structure until you find a match.
If your ranges cover the full interval from lowest to highest boundary, then you can use the bisect module for this; just store either the lower or upper boundaries of each range in one list, the corresponding values in another, and use bisection to map a position in the first list to a result in the second.
If your ranges have gaps, then you either need to keep a third list with the other boundary and first validate that the point falls in the range, or use an interval tree. For non-overlapping ranges a simple binary tree would do, but there are more specialised implementations that support overlapping ranges too. There is a intervaltree project on PyPI that supports full interval tree operations.
A bisect-based mapping that matches behaviour to the fixed-table implementation would look like:
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)
