python - 澄清行为 : collections. defaultdict 与 dict.setdefault

Question

dict 提供 .setdefault()，它允许您动态地将任何类型的值分配给缺失的键:

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

然而，如果您使用 defaultdict 来完成相同的任务，那么每当您尝试访问或修改丢失的 key 时，都会根据需要生成默认值:

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

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

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'}}}}}

Answer 1

在你的第一个例子中，当你执行 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 的方法( but Marius could, see this answer )。您需要将 trie 定义为默认字典，如果缺少键，它会生成一个默认字典，如果缺少键，它本身会生成一个默认字典，递归地直到最大深度(其中，在原理，未知)。

IMO，实现此目的的最佳方法是使用 setdefault，就像您在第二个示例中所做的那样。