在字典中使用范围作为键值，最有效的方法是什么？

Question

我一直在想是否有一种数据结构或聪明的方法可以使用字典（O(1)查找）来返回一个值，如果已定义的范围有不重叠的给定值。目前为止，我一直认为如果范围有一些常量差异（0-2、2-4、4-6等），或者可以进行二进制搜索以在O(log(n))的时间内完成这个任务。

例如，给定一个字典：

d = {[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"
d[random.random()] # this should also work

有没有任何方式可以实现这样的东西？感谢任何回复或关于此的答案。

- NightShade

---

是的，既然您的范围本来就是任意的，您可以编写一个将范围映射到整数的函数。然后在列表中查找该整数（如果范围数量固定），或者在字典中查找。如果范围更加系统化，则该函数甚至可以成为简单的lambda函数。 - Silver

我假设这个解决方案需要进行某种搜索来检查值是否在范围内，那么在这种情况下至少为O(log(n))？没关系，我只是想知道是否有一些传统的方法或数据结构可以在O(1)时间内完成它。 - NightShade

这实际上是一个非常有趣的问题。我从未阅读过将连续范围的值映射到相同索引的哈希函数，这可能是一个非常好的研究问题。 - Silver

Answer 1

如果您接受范围边界的低（一些）分辨率并牺牲了内存以提高查找速度，那么您可以实现O(1)的查找时间。

字典可以在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模块; 只需在一个列表中存储每个范围的下限或上限，另一个列表中存储相应的值，并使用bisection将第一个列表中的位置映射到第二个列表中的结果。

如果您的范围有间隙，那么您需要保留第三个列表与其他边界一起，并先验证该点是否在范围内，或者使用interval tree。对于不重叠的范围，一个简单的二叉树就可以了，但是还有更专业的实现支持重叠的范围。PyPI上有一个intervaltree project支持完整的区间树操作。

一个基于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)

- Martijn Pieters

Answer 2

首先，将您的数据分成两个数组：

limits = [0.1, 0.3, 0.55, 0.7, 1.0]
values = ["a", "b", "c", "d", "e"]

limits已排序，因此您可以在其中进行二分搜索：

import bisect

def value_at(n):
    index = bisect.bisect_left(limits, n)
    return values[index]

- John Zwinck

---

虽然这个答案解决了OP提出的问题，但它并没有以任何方式使用dict。因此，作为一个答案，它只部分涵盖了所问的问题。 - JohanL

@JohanL：如果你有更好的解决方案，请发表出来。问题标题要求“最有效的方法”。 - John Zwinck

我不知道。不过，如果有的话，我会很感兴趣去看看。 - JohanL

@JohanL 有时候答案是：不要使用字典。在Python中很少会听到我这样说... - juanpa.arrivillaga

@juanpa.arrivillaga 嗯，是的，我认为那是一个有效的答案。这样的问题偶尔会出现在更或多或少类似的情况中，然后看到它被陈述也是很好的：不要那样做 :-) - JohanL