python - 'TreeDict'(或 TreeMap )在实践中有什么用？

Question

我正在用 Python 开发一个“TreeDict”类。这基本上是一个字典，允许您按排序顺序检索其键值对，就像 Java 中的 Treemap 集合类一样。

我已经根据关系数据库中唯一索引的使用方式实现了一些功能，例如可让您检索与一系列键对应的值的函数、大于、小于或等于排序顺序中特定值的键、具有排序顺序中特定前缀的字符串或元组等。

不幸的是，我想不出任何现实生活中的问题需要像这样的类(class)。我怀疑我们没有在 Python 中对字典进行排序的原因是在实践中它们不需要足够多的频率来值得它，但我想被证明是错误的。

您能想到“TreeDict”的任何具体应用吗？这种数据结构可以最好地解决任何现实生活中的问题吗？我只是想确定这是否值得。

Answer 1

我看过几个指向“按顺序行走”功能的答案，这确实很重要，但没有一个突出显示另一个重要功能，即“使用键 >= this 找到第一个条目”。即使没有真正需要从那里“步行”，这也有很多用途。

例如(这在最近的 SO 回答中出现)，假设您想生成具有给定相对频率的伪随机值——也就是说，给您一个字典 d :

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}

并且需要一种方法来生成概率为 100 中有 42 的“狼”(因为 100 是给定的相对频率的总和)，“羊”的概率为 100 中的 15，等等；并且不同值的数量可能非常大，相对频率也是如此。

然后，将给定值(以任何顺序)存储为 TreeMap 中的值，相应的键是到该点为止的“总累积频率”。即:

def preprocess(d):
    tot = 0
    for v in d:
        tot += d[v]
        treemap.insert(key=tot, value=v)
    return tot, treemap

现在，生成一个值可以非常快(O(log(len(d))))，如下所示:

def generate(tot, treemap, r=random):
    n = r.randrange(tot)
    return treemap.firstGTkey(n).value

其中 firstGTKey 是返回第一个条目的方法(在这个假设的示例中，具有 .key 和 .value 属性) key > 给定的参数。例如，我将这种方法用于存储为 B 树的大文件(使用例如 bsddb.bt_open 和 set_location 方法)。