Fluent Python 笔记 —— 字典与集合

微信扫一扫,分享到朋友圈

Fluent Python 笔记 —— 字典与集合

标准库里的所有映射类型都是利用 dict 实现的,它们有个共同的限制:其中的 键必须是可散列的数据类型

关于可散列的数据类型的定义:

若某对象是可散列的,则它的散列值在其整个生命周期中是保持不变的。该对象需要实现 __hash__
方法和 __qe__
方法(跟其他键做比较)。如果两个可散列对象是相等的,那么他们的散列值一定相等。

不可变数据类型中的 str
bytes
和数字都是可散列类型。

虽然元组本身是不可变序列,但元组中的元素有可能是其他可变类型的引用。只有当一个元组中包含的所有元素都是可散列类型的情况下,该元组才是可散列的。

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
-3907003130834322577
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

一般用户自定义类型的对象都是可散列的,因此这些对象在比较时都是不相等的。

若某个对象实现了 __eq__
方法,并且在方法中用到了该对象的内部状态,则只有当这些内部状态都是不可变类型的情况下,该对象才是可散列的。

二、字典推导

>>> DIAL_CODES = [
...     (86, 'China'),
...     (91, 'India'),
...     (1, 'America'),
...     (55, 'Brazil'),
...     (7, 'Russia')
... ]
>>> country_code = {country: code for code, country in DIAL_CODES}
>>> country_code
{'China': 86, 'India': 91, 'America': 1, 'Brazil': 55, 'Russia': 7}
>>> {code: country.upper() for country, code in country_code.items() if code < 66}
{1: 'AMERICA', 55: 'BRAZIL', 7: 'RUSSIA'}

三、setdefault 处理找不到的键

以下代码的写法:

my_dict.setdefault(key, []).append(new_value)

其效果等同于如下代码:

if key not in my_dict:
my_dict[key] = []
my_dict[key].append(new_value)

都是获取 my_dict 中 key 键对应的值(如果该 key 不存在,则新增 key 并令其值为 []
),然后向 key 对应的值(列表)中添加新元素。

只不过后者至少要进行两次键查询(如果键不存在,则执行三次键查询),而使用 setdefault
只需要一次键查询就可以完成整个操作。 setdefault
在获取 key 键对应的值时,如果该 key 不存在,则把 key 和空列表直接放进映射并返回空列表,因而不需要执行第二次键值查找。

四、弹性键查询

defaultdict

collections.defaultdict
可以做到即便某个键在映射里不存在,也能够在读取这个键的时候得到一个默认值。只需要用户在初始化 defaultdict
对象时,为其指定一个创建默认值的方法。

即在实例化 defaultdict
的时候,向构造方法提供一个可调用对象,该对象会在 __getitem__
碰到找不到的键的时候被调用,让 __getitem__
返回某种默认值。

dd = defaultdict(list)
。若键 new-key
在 dd 中不存在,表达式 dd['new-key']
会执行以下操作:

list()
new-key

这个用来生成默认值得可调用对象( list()
)存放在名为 default_factory
的实例属性里。若创建 defaultdict 的时候没有指定 default_factory,则查询不存在的键会触发 KeyError。

这些特性背后依赖的是 __missing__
特殊方法,这个特殊方法是所有映射类型都可以选择性地去支持的。

missing

所有的映射类型处理找不到的键的时候,都会涉及到 __missing__
方法。虽然基类 dict 并没有定义这个方法,但如果有一个类继承了 dict,该类提供 __missing__
方法,则 __getitem__
找不到键的时候,会自动调用 __missing__
而不会抛出 KeyError 异常。

__missing__
方法只会被 __getitem__
调用(比如在表达式 d[k]
中)。提供 __missing__
方法对 get
__contains__
方法的使用没有影响。

如需要实现一种自定义的映射类型,在查询的时候将映射里的键都转换成 str。示例代码如下:

class StrKeyDict(dict):
def __missing__(self, key):
if isinstance(key, str):
raise KeyError(key)
return self[str(key)]
def get(self, key, default=None):
try:
return self[key]
except KeyError:
return default
def __contains__(self, key):
return key in self.keys() or str(key) in self.keys()

运行结果如下:

>>> from strkeydict import StrKeyDict
>>> d = StrKeyDict([('2', 'two'), ('4', 'four')])
>>> d['2']
'two'
>>> d[4]
'four'
>>> d[1]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/home/starky/program/python/algorithm/strkeydict.py", line 5, in __missing__
return self[str(key)]
File "/home/starky/program/python/algorithm/strkeydict.py", line 4, in __missing__
raise KeyError(key)
KeyError: '1'
>>> d.get('2')
'two'
>>> d.get(4)
'four'
>>> d.get(1, 'N/A')
'N/A'
>>> 2 in d
True
>>> 1 in d
False

StrKeyDict 继承自 dict,如果找不到的键本身是字符串,抛出 KeyError 异常;如果找不到的键不是字符串,则将其转换成字符串后再进行查找。

get
方法把查找工作用 self[key]
的形式委托给 __getitem__
,这样在确定查找失败之前,还能通过 __missing__
在给某个键一个机会。

isinstance(key, str)
__missing__
中是必须的,若 str(k)
不是一个存在的键,代码就会陷入无限递归。因为 __missing__
最后一行中的 self[str(key)]
会调用 __getitem__
,而 str(key)
又不存在,则 __missing__
又会被调用。

__contains__
方法也是必须的,因为从 dict
继承到的 __contians__
方法不会在找不到键时调用 __missing__
方法。

不可变 Map

标准库里所有的映射类型都是可变的。从 Python 3.3 开始, types
模块引入了一个名为 MappingProxyType
的封装类,可以从普通映射创建一个只读的映射视图。

>>> from types import MappingProxyType
>>> d = {1: 'A'}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: 'A'})
>>> d_proxy[1]
'A'
>>> d_proxy[2] = 'x'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> d[2] = 'B'
>>> d_proxy
mappingproxy({1: 'A', 2: 'B'})
>>> d_proxy[2]
'B'

集合

集合的本质是许多 唯一对象
的聚集,可用于去重:

>>> l = ['spam', 'spam', 'eggs', 'spam']
>>> set(l)
{'spam', 'eggs'}

除了保证唯一性,集合还实现了很多基础的中缀运算符。比如 a | b
求并集, a & b
求交集, a - b
求差集等。合理使用这些运算符可以省去不必要的循环和逻辑操作,使代码行数更少且更易读。

比如有一个电子邮件地址的集合 haystack,还要维护一个较小的电子邮件集合 needles,然后求出 needles 中有多少地址同时也出现在了 heystack 里。

求 needles 的元素在 heystack 中出现的次数,两个变量都是集合类型,则只用一行代码即可实现:

found = len(needles & haystack)

若不使用交集操作的话,则需要通过以下代码实现:

for n in needles:
if n in haystack:
found += 1

散列表

散列表( Hash Map
)是一种稀疏数组(即总是有空白元素的数组),散列表中的单元通常叫做表元( bucket
)。在 dict 背后的散列表中,每个键值对都占用一个表元,每个表元都包含两个部分,对键的引用和对值的引用。因为所有表元的大小一致,可以通过偏移量来读取某个表元。

Python 会保证大概三分之一的表元是空的,当快要达到这个阈值时,原有的散列表会被复制到一个更大的空间里。把对象存入散列表中之前,需要先计算该元素键的散列值。

内置的 hash()
函数可用于计算所有内置类型对象的散列值。若自定义对象调用 hash()
,实际上运行的是自定义的 __hash__
方法。若两个对象比较时大小相等,则它们的散列值也必须相等。即 1 == 1.0
为真,则 hash(1) == hash(1.0)
也必须为真。

为了让散列值能够作为散列表索引使用,这些散列值必须在索引空间内尽量分散开。意味着在理想状态下,越是相似但不相等的对象,其散列值差别也越大。

>>> hash(1.0001)
230584300921345
>>> hash(1.0002)
461168601842689
>>> hash(1.0003)
691752902764033

散列表算法

为了获取 my_dict[search_key]
背后的值,Python 首先会调用 hash(search_key)
来计算 search_key 的散列值,将该值最低的几位数字作为偏移量(具体几位作为偏移量,需依据当前散列表的大小),在散列表里查找表元。若查找出的表元为空,则抛出 KeyError 异常。若表元非空,该表元中会有一对 found_key: found_value
。Python 会检查 search_key == found_key
是否为真,若为真则返回 found_value。

若 search_key 与 found_key 不匹配,这种情况称为 散列冲突
。算法会在散列值中另外再取几位数字,用特殊方法处理一下,把新得到的数字作为索引继续寻找表元并重复以上步骤。

字典的特性

键必须是可散列的

可散列对象满足以下三个要求:

  • 支持 hash()
    函数,且通过 __hash__()
    得到的散列值是不变的
  • 支持通过 __eq__()
    方法检测相等性
  • a == b
    为真,则 hash(a) == hash(b)
    也为真

所有用户自定义对象默认都是可散列的,其散列值有 id()
获取,且都不相等。

字典在内存上开销巨大

字典使用了散列表,散列表又必须是稀疏的,从而导致字典在空间的使用上效率低下。

若需要存放数量巨大的记录,放在由元组或具名元组构成的列表中会是比较好的选择。

用元组取代字典存储记录,一是避免了散列表所耗费的空间,二是无需把记录中字段的名字在每个元素里都存一遍,从而节省空间。

在用户自定义类型中, __slots__
属性可以改变实例属性的存储方式,由 dict 变为 tuple。

字典的键查询很快

dict 的实现是典型的空间换时间。字典类型有着巨大的内存开销,但是它提供了无视数据量大小的快速访问。

键的次序取决于添加顺序

集合的特性

集合里的元素必须是可散列的

集合很消耗内存

可以很高效地判断元素是否存在于某个集合中

元素的次序取决于被添加到集合里的次序

微信扫一扫,分享到朋友圈

Fluent Python 笔记 —— 字典与集合

日本天桥下长出“超坚强”萝卜引网友争相围观 结果被拔掉了

上一篇

Fluent Python 笔记 —— 使用一等函数实现设计模式

下一篇

你也可能喜欢

Fluent Python 笔记 —— 字典与集合

长按储存图像,分享给朋友