python进阶书目串烧
第三章 字典和集合
字典这个数据结构活跃在所有 Python 程序的背后,即便你的源码里并没有直接用到它。——A. M. Kuchling《代码之美》
dict 类型不但在各种程序里广泛使用,它也是 Python 语言的基石。模块的命名空间、实例的属性和函数的关键字参数中都可以看到字典的身影。跟它有关的内置函数都在 __builtins__.__dict__
模块中。
泛映射类型
collections.abc
模块中有 Mapping
和 MutableMapping
这两个抽象基类,它们的作用是为 dict 和其他类似的类型定义形式接口(在Python 2.6 到 Python 3.2 的版本中,这些类还不属于 collections.abc
模块,而是隶属于 collections 模块)
collections.abc
中的 MutableMapping
和它的超类的UML 类图(箭头从子类指向超类,抽象类和抽象方法的名称以斜体显示)
然而,非抽象映射类型一般不会直接继承这些抽象基类,它们会直接对dict
或是collections.User.Dict
进行扩展。这些抽象基类的主要作用是作为形式化的文档,它们定义了构建一个映射类型所需要的最基本的接口。然后它们还可以跟 isinstance
一起被用来判定某个数据是不是广义上的映射类型:
from collections import abc
my_dict = {}
print(isinstance(my_dict, abc.Mapping))
这里用 isinstance
而不是 type
来检查某个参数是否为 dict
类型,因为这个参数有可能不是 dict
,而是一个比较另类的映射类型。
标准库里的所有映射类型都是利用 dict
来实现的,因此它们有个共同的限制,即只有可散列的数据类型才能用作这些映射里的键(只有键有这个要求,值并不需要是可散列的数据类型)。
什么是可散列的数据类型?在Python词汇中,关于可散列类型的定义有这样一段话:
如果一个对象是可散列的,那么在这个对象的生命周期中,它的散列值是不变的,而且这个对象需要实现
__hash__()
方法。另外可散列对象还要有__qe__()
方法,这样才能跟其他键做比较。如果两个可散列对象是相等的,那么它们的散列值一定是一样的……
原子不可变数据类型(str
、bytes
和数值类型)都是可散列类型,frozenset
也是可散列的,因为根据其定义,frozenset
里只能容纳可散列类型。元组的话,只有当一个元组包含的所有元素都是可散列类型的情况下,它才是可散列的1。
来看下面的元组tt、tl 和 tf:
tt = (1, 2, (30, 40))
print(hash(tt)) # 8027212646858338501
tl = (1, 2, [30, 40])
print(hash(tl))
"""
Traceback (most recent call last):
File "<stdin>", line 15, in <module>
TypeError: unhashable type: 'list'
"""
tf = (1, 2, frozenset([30, 40]))
print(hash(tf)) # 985328935373711578
一般来讲用户自定义的类型的对象都是可散列的,散列值就是它们的 id()
函数的返回值,所以所有这些对象在比较的时候都是不相等的。如果一个对象实现了 __eq__
方法,并且在方法中用到了这个对象的内部状态的话,那么只有当所有这些内部状态都是不可变的情况下,这个对象才是可散列的。
字典提供了很多种构造方法,“Built-inTypes”这个页面上有个例子来说明创建字典的不同方式:
a = dict(one=1, two=2, three=3)
b = {'one': 1, 'two': 2, 'three': 3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('two', 2), ('one', 1), ('three', 3)])
e = dict({'three': 3, 'one': 1, 'two': 2})
print(a == b == c == d == e) # True
字典推导
自 Python 2.7 以来,列表推导和生成器表达式的概念就移植到了字典上,从而有了字典推导(后面还会看到集合推导)。字典推导(dictcomp
)可以从任何以键值对作为元素的可迭代对象中构建出字典。
字典推导的应用:
DIAL_CODES = [
(86, 'China'),
(91, 'India'),
(1, 'United States'),
(62, 'Indonesia'),
(55, 'Brazil'),
(92, 'Pakistan'),
(880, 'Bangladesh'),
(234, 'Nigeria'),
(7, 'Russia'),
(81, 'Japan'),
]
country_code = {country: code for code, country in DIAL_CODES}
print(country_code)
print({code: country.upper() for country, code in country_code.items() if code < 66})
常见的映射方法
映射类型的方法其实很丰富。表 3-1 为我们展示了dict
、defaultdict
和 OrderedDict
的常见方法,后面两个数据类型是 dict
的变种,位于 collections
模块内。
方法 | dict | defaultdict | OrderedDict | 作用 |
---|---|---|---|---|
d.clear() | • | • | • | 移除所有元素 |
d.__contains__(k) |
• | • | • | 检查 k 是否在 d 中 |
d.copy() | • | • | • | 浅复制 |
d.__copy__() |
• | 用于支持 copy.copy | ||
d.default_factory | • | 在 __missing__ 函数中被调用的函数,用以给未找到的元素设置值2
|
||
d.__delitem__(k) |
• | • | • | del d[k],移除键为 k 的元素 |
d.fromkeys(it,[initial]) | • | • | • | 将迭代器 it 里的元素设置为映射里的键,如果有 initial 参数,就把它作为这些键对应的值(默认是 None)返回键 k 对应的值,如果字典里 |
d.get(k,[default]) | • | • | • | 没有键 k,则返回 None 或者default |
d.__getitem__(k) |
• | • | • | 让字典 d 能用 d[k] 的形式返回键k 对应的值 |
d.items() | • | • | • | 返回 d 里所有的键值对 |
d.__iter__() |
• | • | • | 获取键的迭代器 |
d.keys() | • | • | • | 获取所有的键 |
d.__len__() |
• | • | • | 可以用 len(d) 的形式得到字典里键值对的数量 |
d.__missing__(k) |
• | 当 __getitem__ 找不到对应键的时候,这个方法会被调用 |
||
d.move_to_end(k,[last]) | • | 把键为 k 的元素移动到最靠前或者最靠后的位置(last 的默认值是 True) | ||
d.pop(k, [defaul] | • | • | • | 返回键 k 所对应的值,然后移除这个键值对。如果没有这个键,返回 None 或者 defaul |
d.popitem() | • | • | • | 随机返回一个键值对并从字典里移除它# |
d.__reversed__() |
• | 返回倒序的键的迭代器 | ||
d.setdefault(k,[default]) | • | • | • | 若字典里有键k,则把它对应的值设置为 default,然后返回这个值;若无,则让 d[k] =default,然后返回 default |
d.__setitem__(k,v) |
• | • | • | 实现 d[k] = v 操作,把 k 对应的值设为v |
d.update(m,[**kargs]) | • | • | • | m 可以是映射或者键值对迭代器,用来更新 d 里对应的条目3 |
d.values() | • | • | • | 返回字典里的所有值 |
用setdefault
处理找不到的键
当字典 d[k]
不能找到正确的键的时候,Python 会抛出异常,这个行为符合 Python 所信奉的“快速失败”哲学。也许每个 Python 程序员都知道可以用 d.get(k, default)
来代替 d[k]
,给找不到的键一个默认的返回值(这比处理 KeyError
要方便不少)。但是要更新某个键对应的值的时候,不管使用 __getitem__
还是 get
都会不自然,而且效率低。
从索引中获取单词出现的频率信息,并把它们写进对应的列表里(低效版):
# index0.py
"""创建一个从单词到其出现情况的映射"""
import sys
import re
WORD_RE = re.compile(r'\w+')
index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
for line_no, line in enumerate(fp, 1):
for match in WORD_RE.finditer(line):
word = match.group()
column_no = match.start() + 1
location = (line_no, column_no)
# 这其实是一种很不好的实现,这样写只是为了证明论点
occurrences = index.get(word, []) # *
occurrences.append(location) # *
index[word] = occurrences # *
# 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])
运行index0.py
$ python3 index0.py ../../data/zen.txt
每一行的列表都代表一个单词的出现情况,列表中的元素是一对值,第一个值表示出现的行,第二个表示出现的列
a [(19, 48), (20, 53)]
Although [(11, 1), (16, 1), (18, 1)]
ambiguity [(14, 16)]
and [(15, 23)]
are [(21, 12)]
aren [(10, 15)]
at [(16, 38)]
bad [(19, 50)]
be [(15, 14), (16, 27), (20, 50)]
beats [(11, 23)]
Beautiful [(3, 1)]
better [(3, 14), (4, 13), (5, 11), (6, 12), (7, 9), (8, 11),
(17, 8), (18, 25)]
...
setdefault
用一行就解决了获取和更新单词的出现情况列表(中效版):
"""创建从一个单词到其出现情况的映射"""
import sys
import re
WORD_RE = re.compile(r'\w+')
index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
for line_no, line in enumerate(fp, 1):
for match in WORD_RE.finditer(line):
word = match.group()
column_no = match.start() + 1
location = (line_no, column_no)
index.setdefault(word, []).append(location) # * 一行顶三行
# 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])
映射的弹性键查询
有时候为了方便起见,就算某个键在映射里不存在,我们也希望在通过这个键读取值的时候能得到一个默认值。有两个途径能帮我们达到这个目的,一个是通过 defaultdict
这个类型而不是普通的 dict
,另一个是给自己定义一个 dict
的子类,然后在子类中实现 __missing__
方法。下面将介绍这两种方法。
defaultdict:处理找不到的键的一个选择4
在 collections.defaultdict
的帮助下优雅地解决index0.py
里的问题。在用户创建 defaultdict
对象的时候,就需要给它配置一个为找不到的键创造默认值的方法。
具体而言,在实例化一个 defaultdict
的时候,需要给构造方法提供一个可调用对象,这个可调用对象会在 __getitem__
碰到找不到的键的时候被调用,让 __getitem__
返回某种默认值。
比如,我们新建了这样一个字典:dd = defaultdict(list)
,如果键'new-key'
在 dd
中还不存在的话,表达式 dd['new-key']
会按照以下的步骤来行事。
- 调用
list()
来建立一个新列表。 - 把这个新列表作为值,
'new-key'
作为它的键,放到dd
中。 - 返回这个列表的引用。
而这个用来生成默认值的可调用对象存放在名为 default_factory
的实例属性里。
利用 defaultdict
实例而不是setdefault
方法(高效版):
# index_default.py
"""创建一个从单词到其出现情况的映射"""
import sys
import re
import collections
WORD_RE = re.compile(r'\w+')
# 把list构造方法作为default_factory来创建一个defaultdict。
index = collections.defaultdict(list)
with open(sys.argv[1], encoding='utf-8') as fp:
for line_no, line in enumerate(fp, 1):
for match in WORD_RE.finditer(line):
word = match.group()
column_no = match.start() + 1
location = (line_no, column_no)
index[word].append(location) # *
# 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])
上方代码注释*号的一行说明:如果index
并没有word
的记录,那么default_factory
会被调用,为查询不到的键创造一个值。这个值在这里是一个空的列表,然后这个空列表被赋值给 index[word]
,继而被当作返回值返回,因此.append(location)
操作总能成功。
注意: 如果在创建 defaultdict
的时候没有指定 default_factory
,查询不存在的键会触发 KeyError
。5
所有这一切背后的功臣其实是特殊方法 __missing__
。它会在defaultdict
遇到找不到的键的时候调用 default_factory
,而实际上这个特性是所有映射类型都可以选择去支持的。
特殊方法__missing__
6
所有的映射类型在处理找不到的键的时候,都会牵扯到 __missing__
方法。这也是这个方法称作“missing”的原因。虽然基类 dict
并没有定义这个方法,但是 dict
是知道有这么个东西存在的。也就是说,如果有一个类继承了 dict
,然后这个继承类提供了 __missing__
方法,那么在 __getitem__
碰到找不到的键的时候,Python 就会自动调用它,而不是抛出一个 KeyError
异常。7
当有非字符串的键被查找的时候,StrKeyDict0
是如何在该键不存在的情况下,把它转换为字符串的:
d = StrKeyDict0([('2', 'two'), ('4', 'four')])
print(d['2']) # 'two'
print(d[4]) # 'four'
print(d[1])
"""
Traceback (most recent call last):
...
KeyError: '1'
"""
print(d.get('2')) # 'two'
print(d.get(4)) # 'four'
print(d.get(1, 'N/A')) # 'N/A'
print(2 in d) # True
print(1 in d) # False
StrKeyDict0
在查询的时候把非字符串的键转换为字符串:
class StrKeyDict0(dict): # StrKeyDict0 继承了dict
def __missing__(self, key):
if isinstance(key, str): # 找不到的键本身就是字符串,那就抛出KeyError异常
raise KeyError(key)
return self[str(key)] # 找不到的键不是字符串,把它转换成字符串再进行查找。
def get(self, key, default=None):
try:
return self[key] # 用self[key]的形式委托给 __getitem__,在查找失败之前,还能通过 __missing__ 再给某个键一个机会。
except KeyError: # 说明 __missing__ 也失败了,于是返回default。
return default
def __contains__(self, key):
return key in self.keys() or str(key) in self.keys()
为什么 isinstance(key, str)
测试在上面的__missing__
中是必需的。
如果没有这个测试,只要 str(k)
返回的是一个存在的键,那么__missing__
方法是没问题的,不管是字符串键还是非字符串键,它都能正常运行。但是如果 str(k)
不是一个存在的键,代码就会陷入无限递归。这是因为 __missing__
的最后一行中的 self[str(key)]
会调用 __getitem__
,而这个 str(key)
又不存在,于是 __missing__
又会被调用。
为了保持一致性,__contains__
方法在这里也是必需的。这是因为 k in d
这个操作会调用它,但是我们从 dict
继承到的 __contains__
方法不会在找不到键的时候调用 __missing__
方法。__contains__
里还有个细节,就是我们这里没有用更具 Python 风格的方式——k in my_dict
——来检查键是否存在8,因为那也会导致 __contains__
被递归调用。为了避免这一情况,这里采取了更显式的方法,直接在这个self.keys()
里查询。
出于对准确度的考虑,我们也需要这个按照键的原本的值来查找的操作(也就是 key in self.keys()
),因为在创建 StrKeyDict0
和为它添加新值的时候,我们并没有强制要求传入的键必须是字符串。因为这个操作没有规定死键的类型,所以让查找操作变得更加友好。
-
直到现在,Python词汇表里还在说“Python 里所有的不可变类型都是可散列的”。这个说法其实是不准确的,比如虽然元组本身是不可变序列,它里面的元素可能是其他可变类型的引用。 ↩︎
-
default_factory
并不是一个方法,而是一个可调用对象(callable),它的值在defaultdict
初始化的时候由用户设定。 ↩︎ -
update
方法处理参数m
的方式,是典型的“鸭子类型”。函数首先检查m
是否有keys
方法,如果有,那么update
函数就把它当作映射对象来处理。否则,函数会退一步,转而把 m 当作包含了键值对(key, value)
元素的迭代器。Python 里大多数映射类型的构造方法都采用了类似的逻辑,因此你既可以用一个映射对象来新建一个映射对象,也可以用包含(key, value)
元素的可迭代对象来初始化一个映射对象。 ↩︎ -
B2中涉及到
defaultdict
使用的位置:1.6 字典中的键映射多个值、1.15 通过某个字段将记录分组、4.10 序列上索引值迭代、8.18 利用 Mixins 扩展类功能、10.12 导入模块的同时修改模块、12.11 实现消息发布/订阅模型 ↩︎ -
defaultdict
里的default_factory
只会在__getitem__
里被调用,在其他的方法里完全不会发挥作用。比如,dd
是个defaultdict
,k
是个找不到的键,dd[k]
这个表达式会调用default_factory
创造某个默认值,而dd.get(k)
则会返回None
。 ↩︎ -
B2中涉及到
__missing__
使用的位置:2.15 字符串中插入变量 ↩︎ -
__missing__
方法只会被__getitem__
调用(比如在表达式d[k]
中)。提供__missing__
方法对get
或者__contains__
(in 运算符会用到这个方法)这些方法的使用没有影响。这也是在上一节最后的警告中提到,defaultdict
中的default_factory
只对__getitem__
有作用的原因。 ↩︎ -
像
k in my_dict.keys()
这种操作在 Python 3 中是很快的,而且即便映射类型对象很庞大也没关系。这是因为dict.keys()
的返回值是一个“视图”。视图就像一个集合,而且跟字典类似的是,在视图里查找一个元素的速度很快。在“Dictionary view objects”里可以找到关于这个细节的文档。Python 2 的dict.keys()
返回的是个列表,因此虽然上面的方法仍然是正确的,它在处理体积大的对象的时候效率不会太高,因为k inmy_list
操作需要扫描整个列表。 ↩︎
本文地址:https://blog.csdn.net/qq_35289736/article/details/109144128