“TreeDict”(或Treemap)在实践中可以用于什么?

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

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

需要一种方法来生成“狼”的概率为42/100(因为100是给出的相对频率的总和),“羊”的概率为15/100,依此类推;不同值的数量可能相当大,相对频率也是如此。

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

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 方法)。

保持元素按排序顺序的原因是为了更快地检索。假设我希望字典中的所有值都在一个排序范围内。使用TreeDict要比使用常规hashmap快得多。它基本上可以让你把字典里的所有东西按顺序排列。我知道,在我目前正在开发的应用程序中,使用这样一个类来基本查询数据结构。

我经常遇到的一种情况是,对象由特定的名称标识,并且您希望打印出根据名称排序的对象;说一个从目录名到目录中文件数的映射。

我使用过的另一个地方是excel电子表格包装中;从行编号映射到行对象。这使您可以快速找到最后一行索引,而无需遍历每一行。

此外,当您可以轻松定义键上的比较关系,但不一定是HashMaps所需的哈希函数时,它也很有用。我能想到的最好的(尽管很弱)例子是不区分大小写的字符串键。

我经常使用 Dict<DateTime, someClassOrValue> 阀门开启/关闭、机械启动/停止等。

当我需要在相当长的时间内比较启动/停止或打开/关闭事件之间的时间间隔时,对键进行排序特别有用。

然而,由于我能够在C#中使用linq,我发现只使用IEnumerables并使用IQueryable扩展方法来获取我需要的信息通常更容易。

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

这在数据仓库应用程序中非常常见,因此很难表达其重要性。

sorted

你有没有看到: http://code.activestate.com/recipes/576998/ ?

它们可以使各种算法更容易实现。