首页 / 问题 / 正文

TreeDict'（或树图）在实践中有什么用途？

1 投票
6 回答
3520 浏览
提问于 2025-04-15 12:20

我正在用Python开发一个叫做'TreeDict'的类。这个类基本上就是一个字典，不过它可以让你按顺序获取键值对，就像Java里的Treemap集合类一样。

我已经实现了一些功能，灵感来自于关系数据库中独特索引的用法，比如可以让你根据一系列键来获取对应的值，或者获取大于、小于或等于某个特定值的键，并且都是按顺序排列的，还有可以获取以特定前缀开头的字符串或元组，都是按顺序的等等。

不过，遗憾的是，我想不出有什么实际问题需要这样一个类。我怀疑Python中没有排序字典的原因是，它们在实际使用中并不常见，所以不值得去实现，但我希望我错了。

你能想到'TreeDict'的具体应用吗？有没有什么实际问题用这个数据结构解决会更好？我只是想确认一下，这个东西是否真的有用。

数据结构 数据存储 键值对 关系数据库 应用场景 treedict 排序字典 唯一索引

6 个回答

2

把元素保持在有序状态的原因是为了更快地获取数据。比如说，我想要字典中所有在某个范围内的值。如果用TreeDict，这样做会比用普通的哈希表快得多。TreeDict基本上可以让你把字典里的所有东西都保持有序。我知道我现在正在做的应用程序就用了一种这样的类来查询数据结构。

回答于 2025-04-15 由 Python大师
分享 举报
6

我看到有几个回答提到了“按顺序遍历”的功能，这确实很重要，但没有人强调另一个大功能，那就是“找到第一个键大于等于这个值的条目”。这个功能有很多用途，即使在不需要“遍历”的情况下也很有用。

举个例子（这个在最近的一个回答中提到过），假设你想生成一些伪随机值，并且这些值有给定的相对频率。也就是说，你有一个字典 d：

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

你需要以42%的概率生成“狼”，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 方法。

回答于 2025-04-15 由 Python大师
分享 举报
2

当你需要按照键的顺序遍历一个字典时，这个功能就很有用；这种情况偶尔会出现。我发现它在某些编程比赛中比其他地方更常见（比如ACM等）。

TreeMap最有用的功能是当你想快速找到最小或最大键时；使用一个排序过的字典，这通常只需要调用一个方法；而在算法上，这可以在O(log(n))的时间内完成，相比之下，如果集合没有排序，你就得一个一个地遍历每个键来找最小或最大值。总的来说，它提供了一个更友好的使用界面。

我常常遇到这种情况，比如对象是通过特定名称来识别的，而你想按照名称的顺序打印出这些对象；比如说从目录名称到目录中文件数量的映射。

我还用过它在一个Excel表格的封装中；从行号到行对象的映射。这让你可以快速找到最后一行的索引，而不需要逐行遍历。

另外，当你可以轻松定义键之间的比较关系，但不一定能定义哈希函数（这是HashMap需要的）时，它也很有用。我能想到的一个比较弱的例子就是不区分大小写的字符串键。

回答于 2025-04-15 由 Python大师
分享 举报

撰写回答