set 是 Python 非常重要的一种数据结构, 不能包含相同的元素, 几乎所有用过 Python 的人都知道, set 有进行列表去重的功能.
但是鲜有人意识到了 set 在数学概念上的意义, 那就是集合, 能进行交集, 并集这些操作. 很多时候使用 set 把问题抽象成一个集合问题, 能使问题既简单又高效.
来看一下不同语言对于 set 的支持情况: Python,.Net,Ruby 都很好地支持了 set 数据结构.
image
0x00 Set 基础知识
set comprehension
image
image
in 查询
时间复杂度为 O(1) , 应该 set 内部使用的是 hash table, 所以判断元素在不在集合里面速度非常快. in 操作在底层实际上调用的是 set 的 contains 方法.
早期的 Python 事实上也是没有 set 的, 那时候用的是 dict 来模拟 set.
集合操作
python 内置了很多 operators, 能让你像运算数学公式一样操作操作集合.
image
image
image
第 20 行是德摩根定律.
methods
上述的 operators 底层是 set 定义的很多实用方法, 下图在《流畅的 Python》里面有:
image
image
image
非数学相关的方法:
image
ABC
collections.abc 定义了 Set 数据结构, set 和 mutable set 都实现了 Set interface.
image
0x01 Case 1
需求: 查询所有满足这种需求的商品: 商品的描述信息中保护 query 中出现过的所有单词.(display product if all words in the query appear in the product description.)
go 语言中是没有 set 这种数据结构的, 判断语句如下: found flag 用来判断是不是要结束循环. 嵌套循环很不优雅!
image
事实上这是一个集合问题, 假设商品的描述为集合 D, 查询语句为集合 Q, 问题就变成了判断是否满足 Q D.
image
0x02 Case 2
需求: 标记所有 favorited 且不在购物车的商品.
事先让你写一个方法, 你第一反应是和我一样, 用循环来解决吗? 比如这种:
- chart_list = []
- def filter_goods(goods_list):
- ret = []
- for goods in goods_list:
- if goods.favorited and goods not in charts_list:
- ret.append(goods)
- return ret
这其实可以有更优雅的方法, 可以把这个问题抽象成一个数学集合问题, 设所有标记为喜欢的商品为集合 F, 在购物车的商品为集合 C, 那么要求的就是 F 和 非 C 的交集∩.
image
如果你对 Python 编程感兴趣, 那么记得来小编的 Python 学习扣群: 556370268, 这里有资源共享, 技术解答, 大家可以在一起交流 Python 编程经验, 还有小编整理的一份 Python 学习教程, 希望能帮助大家更好的学习 python.
来源: http://www.jianshu.com/p/ca8fc1eb9b05