月度归档： 2022年3月

1、以一个例子开始：统计一个列表里各单词重复次数

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    counter[kw] += 1

这样写肯定会报错的，因为各词的个数都没有初始值，引发KeyError

2、改进一下：加入if判断

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    if kw in words:
        counter[kw] += 1
    else:
        counter[kw] = 0

3、再改进：使用setdefault()方法设置默认值

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    counter.setdefault(kw, 0)
    counter[kw] += 1

setdefault()，需提供两个参数，第一个参数是键值，第二个参数是默认值，每次调用都有一个返回值，如果字典中不存在该键则返回默认值，如果存在该键则返回该值，利用返回值可再次修改代码。

4、接着改进
一种特殊类型的字典本身就保存了默认值defaultdict()，defaultdict类的初始化函数接受一个类型作为参数，当所访问的键不存在的时候，可以实例化一个值作为默认值。

from collections import defaultdict
dd = defaultdict(list)
defaultdict(<type 'list'>, {})
#给它赋值，同时也是读取
dd['hh']
defaultdict(<type 'list'>, {'hh': []})
dd['hh'].append('haha')
defaultdict(<type 'list'>, {'hh': ['haha']})

该类除了接受类型名称作为初始化函数的参数之外，还可以使用任何不带参数的可调用函数，到时该函数的返回结果作为默认值，这样使得默认值的取值更加灵活。

>>> from collections import defaultdict
>>> def zero():
...     return 0
...
>>> dd = defaultdict(zero)
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {})
>>> dd['foo']
0
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {'foo': 0})

最终代码：

from collections import defaultdict
words = ['hello', 'world', 'nice', 'world']
#使用lambda来定义简单的函数：函数返回值就是默认key的value值
counter = defaultdict(lambda: 0) 
for kw in words:
    counter[kw] += 1

在python中可以用字典来实现字典树这一结构。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.isEnd = '#'

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}  #如果没有这一字母则新建一个字典
            node = node[char]
        node[self.isEnd] = '#'   #加上结束符

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.isEnd in node  #如果没有# 说明只是前缀


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

2.采用defaultdict创建trie

from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word):
        reduce(dict.__getitem__, word, self.trie)['end'] = True
    def search(self, word):
        return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
    def startsWith(self, word):
        return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())

collections，解释是数据类型容器模块。这里面有一个collections.defaultdict()经常被用到

这里的defaultdict(function_factory)构建的是一个类似dictionary的对象，其中keys的值，自行确定赋值，但是values的类型，是function_factory的类实例，而且具有默认值。比如default(int)则创建一个类似dictionary对象，里面任何的values都是int的实例，而且就算是一个不存在的key, d[key] 也有一个默认值，这个默认值是int()的默认值0.