字典和集合

发表于 | 分类于 | 阅读次数: | 本文被阅读 次
字数统计: 819 | 阅读时长 ≈ 3

paste image

这是一个关于学习《Fluent Python》这本书第三章的学习笔记


字典

散列表的概念

可散列对象:

  1. 有__hash__()方法，且散列值不变
  2. 有__eq__()方法，能跟其他键比较

可散列类型:

  • str
  • bytes
  • 数值类型
  • frozenset
  • tuple(全部元素为可散列数据类型)

字典推导

字典推导的例子：

1
country_code = {country :code for code, country in DIAL_CODES}

DIAL_CODES是元组对的列表

处理找不到的键

d.__getitem__() –> d[k]操作
d.__contain__() –> k in d操作
d.__missing__() –> 当d.__getitem__()找不到对应的键时，会被调用
d.update(m, [**kargs])
m参数:

  1. 检测是否有keys方法
  2. 检测是否是（key，value）的迭代器
  • dict
  • setdefault
  • defaultdict

dict:

dict.get(k, [default])
返回k键对应的值，如果k不存在，则返回None或default

setdefault:

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

等效于

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

后者至少要2次查询，不存在要查询3次；而setdefault只需1次

defaultdict

1
2
dd = collections.defaultdict(list)
dd[new_key] # 如果new_key不存在

执行步骤为：

  1. 调用list()生成一个[]
  2. 以new_key为键，[]为值，添加入dd中
  3. 返回这个[]的引用

集合

集合的本质是许多唯一对象的聚集
集合里的元素必须是可散列的
set类型是不可散列的
但frozenset是可散列的
即set(frozenset(),…)是成立的

集合推导

集合推导的例子：

1
2
from unicodedata import name
{chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), ' ')}

一个关于效率的实验

1
2
3
4
5
# haystack分别以1000为基础，每次变为上一次的10倍，进行5次实验
found = 0
for n in  needles:
	if n in haystack: 
    	found += 1

这个代码分别用类型dict、set、list
效率排序为：dict$\approx$set>>list
dict、set对于数据量的变化，所有时间变化不大
list与数据量的增长几乎成正比关系

而以下代码，运用集合交集&运算

1
found = len(needles & haystack)

这个的效率又比以上类型更快一点点

字典（集合）的散列表

散列表

  • 散列表其实是一个稀疏数组（总是有空白元素的数组）
  • 散列表的单元叫表元；字典里的表元（键的索引 | 值的索引）的方式储存
  • 字典的表元大小相等，通过偏移量读取表元

散列表算法

paste image
对于以下代码：

1
my_dict[search_key]

  1. 先调用hash(search_key)得到散列值，然后利用这个值的最低几位的偏移值去匹配表元
  2. 如果表元为空，抛出KeyError
  3. 如果不为空，表元里有（found_key: found_value），验证search_key == found_key
    • 为真，返回found_value
    • 为假，这种情况叫散列冲突，然后再在散列值里再取几位，重复步骤2,3

一般来说，散列冲突平均可能出现1~2次

字典的实现导致的结果

  • 字典对内存的开销巨大，以换取键搜索时的效率
  • 添加新元素时，可能使字典扩容，导致元素原有顺序的变化
    • 所以更新字典最好分2步：
      1. 迭代字典，查找到需要更新的键，把键复制到列表中
      2. 迭代词列表，对原字典进行更新
0%