具有有序键和键值区间选择的字典类数据结构

Question

假设我想存储有序值，其中键值表示下限。像这个例子：

d = {1: "pear", 4: "banana", 7: "orange"}

我可以通过d[1]访问第一个对象。假设我想存储它，以便我可以通过调用 [1,4) 之间的任何值来访问第一个对象 "pear"。如果我在 [4,7) 之间输入任何 "keyvalue"，我希望返回 "banana"。 python中有没有类似的数据结构？我找到了 intervalTrees，但它看起来比我要找的要高级一些。在 intervalTrees 中，作为键的间隔可以重叠，我不希望这样。或者它可能不是我想要的任何类型的字典，因为您可以将数据类型混合为一个字典中的键。你怎么看？

编辑：根据我得到的提示，这将是一个有效的代码：

import bisect

d = [(1, "pear"), (4, "banana"), (7,"orange") ]
keys = [j[0] for j in d]

for v in range(1,10):
    print("Using input ", v)
    i = bisect.bisect(keys, v) - 1
    out = d[i]
    print(out)
    print("")

# Or using SortedDict
from sortedcontainers import SortedDict

d2 = SortedDict()
d2[1] = 'pear'
d2[4] = 'banana'
d2[7] = 'orange'

for v in range(1,10):
    print("Using input ", v)
    i = bisect.bisect(d2.keys(), v) - 1
    j = d2.keys()[i]
    out = d2[j]
    print(out)
    print("")

Answer 1

您要查找的数据结构是二叉搜索树 (BST)，最好是 balanced BST。您的字典键是 BST 的键，每个节点只会有一个额外的字段来存储相应的值。那么您的查找只是键的下限/左平分。查找 Python 红黑树或 AVL 树的实现 returns 许多可能的包。

没有用于始终排序数据的内置库。如果您永远不需要添加或删除键，则可以在排序列表中使用 bisect 和 (key, value) 元组。

对于允许修改的纯 Python 实现，我建议从内存中的 the SortedContainers library. It's built to be a drop-in replacement for BST's, is very usable and tested, and claims to outperform 基于指针的 BST 检查 SortedDict，并在合理大小的数据集上速度（但没有相同的渐近线）作为 BST 的保证）。您还可以提供自定义键来比较不同类型的对象。

具有有序键和键值区间选择的字典类数据结构

dictionary like data structure with ordered keys and selection between interval of key values

python

dictionary

intervals