我有一本字典,它的键是以一组相同的前缀出现的,就像这样:
d = { "key1":"valA", "key123":"valB", "key1XY":"valC",
"key2":"valD", "key2-22":"valE" }
给定一个查询字符串,我需要查找与以该前缀开头的键相关联的所有值,例如,对于query="key1"
,我需要得到["valA", "valB", "valC"]
我下面的实现可以工作,但是对于大量查询来说太慢了,因为字典d
有大约30000个键,并且大多数键的长度超过20个字符:
有没有更快/更有效的方法来实现这一点?在
sortedContainers
lib有一个SortedDict实现,一旦对dict进行了排序,就可以左等分查找起始位置,右等分查找最后一个位置,然后使用irange获取范围内的键:一旦您维护了一个Sortedict,使用Sortedict会更有效:
^{pr2}$您可以避免生成
dict.keys()
(在python2.x中)生成的中间列表:但是您很可能希望使用trie而不是字典,这样您就可以找到与具有公共前缀的键相关联的所有值(trie类似于基于前缀的树)。在
Here您可以找到一些不同的尝试实现。在
让我们比较一下不同解决方案的时间安排:
^{pr2}$您可以使用suffix tree:
输出
^{pr2}$相关问题 更多 >
编程相关推荐