什么可以在实践中使用'TreeDict'(或树图)？

Question

我正在用Python开发一个'TreeDict'类.这基本上是一个dict,允许您按排序顺序检索其键值对,就像Java中的Treemap集合类一样.

我已经基于关系数据库中的唯一索引的方式实现了一些功能,例如,允许您检索与一系列键相对应的值,大于,小于或等于按排序顺序的特定值的键,字符串或按排序顺序具有特定前缀的元组等.

不幸的是,我想不出任何需要像这样的课程的现实生活问题.我怀疑我们在Python中没有排序的原因是,在实践中它们并不经常被要求得到它,但我想被证明是错误的.

你能想到'TreeDict'的任何具体应用吗？这个数据结构最能解决的任何现实问题？我只是想知道这是否值得.

Answer 1

我已经看到几个答案指向"走进有序序列"功能,这确实很重要,但没有突出显示另一个重要功能,即"找到第一个带有键> =这个".即使没有真正需要从那里"行走",这也有很多用途.

例如(这出现在最近的SO回答中),假设您想要生成具有给定相对频率的伪随机值 - 即,您给出了一个dict d:

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

并且需要一种方法来产生'狼',概率为百分之42(因为100是给定的相对频率的总和),'羊'中有15分,等等; 并且不同值的数量可以非常大,相对频率也可以.

然后,将给定值(以任何顺序)存储为树图中的值,相应的键是直到该点的"总累积频率".即:

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属性,在该假设的例子)用钥匙>给定的参数.我已经将这种方法用于存储为B树的大文件(例如bsddb.bt_open,使用例如和set_location方法).