记录博客 ZH-BLOG

Python 字典与集合(二)

时间:2018-08-03 15:36:41分类:python

集合:set 和 frozenset

集合中的元素必须是可散列的, set 类型本身是不可散列的, 但是frozenset 可以。集合中不允许有重复的对象,所以集合可以用来去重。

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

>>> s = {(1,2,3), 4, 5}
>>> s = {[1,2,3], 4, 5}
Traceback (most recent call last):
  ...
TypeError: unhashable type: 'list'
>>> s = {frozenset([1,2,3]), 4, 5} # set 可以包含不同的 frozenset
>>> s
{5, frozenset({1, 2, 3}), 4}

集合字面量

除空集之外, 集合的字面量——{1}、 {1, 2},如果是空集, 那么必须写成 set() 的形式。

>>> s = {1}
>>> type(s)
<class 'set'>
>>> s
{1}
>>> s.pop()
1>
>> s
set()


像 {1, 2, 3} 这种字面量句法相比于构造方法(set([1, 2, 3]))要更快。

frozenset 没有字面量句法,只能采用构造方法。

>>> frozenset(range(10))
frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

集合推导

>>> from unicodedata import name
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')}
{'<', 'µ', '£', '=', '¥', '§', '>', '°', '¢', '+', '$', '¶', '¤', '¬', '÷', '%', '±', '#', '×', '®', '©'}

unicodedata.name(chr[, default]):

返回 chr 字符的名称,如果没有找到,返回默认值。默认值未指定,找不到则抛出 ValueError。

集合的操作

集合的中缀运算符需要两侧的被操作对象都是集合类型,但是其它的方法则只要求所传入的参数是可迭代对象。

>>> a = {1,2}
>>> b = [2,3]
>>> c = (3,4)
>>> d = frozenset([4,5])
>>> a.union(b,c,d)
{1, 2, 3, 4, 5}
>>> from array import array
>>> e = array('h', [5,6])
>>> a.union(b,c,d,e)
{1, 2, 3, 4, 5, 6}

1. 交集

>>> s = {1,2,3}
>>> z = {2,3,4}
>>> s & z # 必须都是集合
{2, 3}
>>> s.__and__(z) # 正向 & 操作
{2, 3}
>>> s.__rand__(z) # 反向 & 操作
{2, 3}
>>> s.intersection(z) # 交集方法,不要 z 必须是集合,迭代对象即可
{2, 3}
>>> s.intersection(range(10))
{1, 2, 3}
>>> s
{1, 2, 3}
>>> z
{2, 3, 4} # 以上操作都不会修改原数据
>>> s &= z # 取交集并赋值 s 
>>> s
{2, 3}
>>> z
{2, 3, 4}
>>> z.__iand__(s) # &= 操作
{2, 3}
>>> z
{2, 3}
>>> s.intersection_update(range(2)) # &= ,不要求参数必须是集合,迭代对象即可
>>> s
set()

2. 并集

>>> s = {1,2,3}
>>> z = {2,3,4}
>>> s | z # 并集
{1, 2, 3, 4}
>>> s.__or__(z) # | 操作
{1, 2, 3, 4}
>>> s.__ror__(z) # 反向 | 操作
{1, 2, 3, 4}
>>> s.union(range(10)) # | 操作,不要求参数必须是集合,迭代对象即可
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> s |= z # 取并集并赋值 s
>>> s
{1, 2, 3, 4}
>>> s.__ior__(z) # |= 操作
{1, 2, 3, 4}
>>> s.update(range(10)) # |= 操作,不要求参数必须是集合,迭代对象即可
>>> s
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

3. 差集

>>> s = {1,2,3}
>>> z = {2,3,4}
>>> s - z # s 与 z 的差集
{1}
>>> z - s # z 与 s 的差集
{4}
>>> s.__sub__(z) # s - z
{1}
>>> s.__rsub__(z) # z - s
{4}
>>> s.difference(range(2)) # 差集,不要求参数必须是集合,迭代对象即可
{2, 3}
>>> s -= z # 求差集并赋值给 s
>>> s
{1}
>>> s.__isub__(z) # -= 操作
{1}
>>> s.difference_update(range(10)) # -= 操作,不要求参数必须是集合,迭代对象即可
>>> s
set()

4. 对称差集

>>> s = {1,2,3}
>>> z = {2,3,4}
>>> s ^ z # 对称差集
{1, 4}
>>> z ^ s
{1, 4}
>>> s.__xor__(z) # 正向操作
{1, 4}
>>> s.__rxor__(z) # 反向操作
{1, 4}
>>> s.symmetric_difference(z) # ^ 操作,不要求参数必须是集合,迭代对象即可
{1, 4}
>>> s ^= z # ^ 操作,并赋值给 s
>>> s
{1, 4}
>>> s.__ixor__(z) # ^= 操作
{1, 2, 3}
>>> s
{1, 2, 3}
>>> s.symmetric_difference_update(range(10)) # ^= 操作,不要求参数必须是集合,迭代对象即可
>>> s
{0, 4, 5, 6, 7, 8, 9}

集合的比较操作

子集就是一个集合中的全部元素是另一个集合中的元素,有可能与另一个集合相等;

真子集就是一个集合中的元素全部是另一个集合中的元素,但不存在相等。

>>> s = {1,2,3}
>>> z = {1,2,3}
>>> t = {1,2,3,4}
>>> s <= z	# s 是否为 z 的子集 s.__le__(z)
True
>>> s <= t	# s 是否为 t 的子集 s.__le__(t)
True
>>> s < z	# s 是否为 z 的真子集 s.__lt__(z)
False
>>> s < t	# s 是否为 t 的真子集 s.__lt__(t)
True
>>> s.issubset(range(10)) # 是否为子集,不要求参数必须是集合,迭代对象即可
True
>>> s > z # s 是否为 z 的真父集 s.__gt__(z)
False
>>> s > t # s 是否为 t 的真父集 s.__gt__(t)
False
>>> s >= z  # s 是否为 z 的父集 s.__ge__(z)
True
>>> s >= t # s 是否为 t 的父集 s.__ge__(t)
False
>>> s.issuperset(z) # 是否为父集,不要求参数必须是集合,迭代对象即可
True

判断元素包含关系

>>> s.isdisjoint(z) # 查看 s 和 z 是否不相交(没有共同元素)
False
>>> s.isdisjoint(set(range(10,20)))
True
>>> 1 in s
True
>>> 10 in s
False


字典与集合的总结:

1. python 中的 dict 和 set 效率非常高。

2. dict 和 set 依赖背后的散列表

散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分, 一个是对键的引用, 另一个是对值的引用。 因为所有表元的大小一致, 所以可以通过偏移量来读取某个表元。因为 Python 会设法保证大概还有三分之一的表元是空的, 所以在快要达到这个阈值的时候, 原有的散列表会被复制到一个更大的空间里面。

散列表算法:

为了获取 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 不匹配的话, 这种情况称为散列冲突。 发生这种情况是因为, 散列表所做的其实是把随机的元素映射到只有几位的数字上, 而散列表本身的索引又只依赖于这个数字的一部分。 为了解决散列冲突, 算法会在散列值中另外再取几位,然后用特殊的方法处理一下, 把新得到的数字再当作索引来寻找表元。 若这次找到的表元是空的, 则同样抛出 KeyError; 若非空, 或者键匹配, 则返回这个值; 或者又发现了散列冲突, 则重复以上的步骤。 如图:

hash.png


添加新元素和更新现有键值的操作几乎跟上面一样。 只不过对于前者, 在发现空表元的时候会放入一个新元素; 对于后者, 在找到相对应的表元后, 原表里的值对象会被替换成新值。另外在插入新值时, Python 可能会按照散列表的拥挤程度来决定是

否要重新分配内存为它扩容。 如果增加了散列表的大小, 那散列值所占的位数和用作索引的位数都会随之增加, 这样做的目的是为了减少发生散列冲突的概率。

3. dict 的限制

必须是可散列的。(字典只要求 key)

在内存上的开销巨大。

键的次序取决于添加顺序。

往字典里添加新键可能会改变已有键的顺序,因为添加有可能引起扩容操作。

4. set 的限制

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

集合很消耗内存。

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

往集合里添加元素, 可能会改变集合里已有元素的次序。