时间戳

首页 > 解决方案 > 澄清行为：collections.defaultdict vs dict.setdefault

python - 澄清行为：collections.defaultdict vs dict.setdefault

问题描述

dict提供.setdefault()，这将允许您动态分配任何类型的值到缺少的键：

>>> d = dict()
>>> d.setdefault('missing_key', [])
[]
>>> d
{'missing_key': []}

然而，如果您用于defaultdict完成相同的任务，则每当您尝试访问或修改缺少的键时，都会按需生成默认值：

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d['missing_key']
[]
>>> d
defaultdict(<class 'list'>, {'missing_key': []})

但是，使用以下实现的代码defaultdict会引发 aKeyError而不是使用默认值创建项目{}：

trie = collections.defaultdict(dict)
for word in words:
    t = trie
    for c in word:
        t = t[c]
    t["*"] = word

使用.setdefault()正常：

trie = {}
for word in words:
    t = trie
    for c in word:
        t = t.setdefault(c, {})
    t["*"] = word

访问前检查，也可以：

trie = {}
for word in words:
    t = trie
    for c in word:
        if c not in t:
           t[c] = {}
        t = t[c]
    t["*"] = word

使用时我缺少什么collections.defaultdict()？

注意 我正在尝试从单词列表中构建一个Trie结构。例如：

words = ["oath", "pea", "eat", "rain"]
trie = {'o': {'a': {'t': {'h': {'*': 'oath'}}}}, 'p': {'e': {'a': {'*': 'pea'}}}, 'e': {'a': {'t': {'*': 'eat'}}}, 'r': {'a': {'i': {'n': {'*': 'rain'}}}}}

标签： pythonpython-3.xdictionarydefaultdict

解决方案

在您的第一个示例中，当您执行 t = t[c] 时，t 变为常规空dict（因为这是您defaultdict在 的定义中告诉生成的内容trie）。

让我们用您的示例单词遍历循环"oath"：

1) t = trie, word = "oath"
2) c = "o"
3) t = t[c]
  3.1) evaluation of t[c] # "o" is not in trie, so trie generates an empty dict at key "o" and returns it to you
  3.2) assignment to t -> t is now the empty dict. If you were to run (t is trie["o"]), it would evaluate to True after this line
4) c = "a"
5) t = t[c]
  5.1) Evaluation of t[c] -> "a" is not in the dict t. This is a regular dict, raise KeyError.

不幸的是，由于 Trie 的任意嵌套，我想不出在defaultdict这里使用的方法（但 Marius 可以，看到这个答案）。您需要将 trie 定义为 defaultdict ，在缺少 key 的情况下，生成一个默认 dict ，它本身在缺少 key 的情况下生成一个默认 dict，递归直到最大深度（原则上是未知的）。

IMO，实现这一点的最佳方法是使用setdefault您在第二个示例中所做的。

推荐阅读