Set及操作

约定概念/叫法：

• set翻译为集合
• collection翻译为集合类型，是一个大概念

set是可变的、无序的、不重复的元素的集合

set的定义/初始化

• 创建空集合

set()   

• 构建一个新集合对象

set(iterable)

实例：

• 创建空集合

In [1]: s1 = set()

In [2]: s1
Out[2]: set()

• set()函数将一个可迭代对象变成set

In [3]: set(range(5))
Out[3]: {0, 1, 2, 3, 4}

In [4]: set(list(range(5)))
Out[4]: {0, 1, 2, 3, 4}

错误的创建空集合的方法

In [7]: s4 = {} # 生成空字典

In [8]: type(s4)
Out[8]: dict

直接表示集合

>>> s5 = {5,6,7,8}
>>> print(s5, type(s5))
{8, 5, 6, 7} <class 'set'>

set可以存储不同类型的数据

>>> s6 = {(1,2), 3, 'a'}
>>> print(s6, type(s6))  
{(1, 2), 3, 'a'} <class 'set'>

set不能存储不可哈希的数据类型，例如列表

>>> s7 = {[1], (1,), 1}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

set的元素

• set的元素要求必须可以hash

  • 目前学过不可哈希的类型有：list，set

• set的元素不可以使用索引

• set可以迭代

set操作

增加

add()

• 增加一个元素到set中；如果元素存在，则不进行添加

update(*others)

• 合并其他元素到set集合中来

• 参数others必须是可迭代对象

  • 是遍历可迭代对象others中的每一个元素，然后将每一个元素一一添加进set

    • >>> s5.update(1,(21,)) # 1不是可迭代对象
      Traceback (most recent call last):
        File "<stdin>", line 1, in <module>
      TypeError: 'int' object is not iterable
      >>> s5.update((21,),(12,122,1212,10))
      >>> s5
      {5, 6, 7, 8, 10, 12, (11,), 21, 122, 1212} # 并不是将可迭代对象充当一个整体加进来
      
      

• 就地修改（直接修改set本身）

删除

remove(elem)

• 从set中移除一个元素
• 若元素不存在，抛出KeyError异常。
  • 为什么是KeyError？-- 集合是非线性结构，内部使用hash值作为key，以此标识数据/查找数据

discard(elem)

• 从set中移除一个元素
• 元素不存在，就什么都不做
• 建议使用discard而非remove

pop() --> item

• 移除并返回任意的元素
  • 为什么是任意元素？ -- 因为集合是无序的，所以不能保证pop固定位置的元素
• 空集合返回keyerror

clear()

• 移除所有元素

• 不建议使用，因为会引起内存动荡

set修改

要么增加，要么删除，没有直接修改原本存在的元素的方法

为什么？-- 因为集合不是线性结构，对于每个元素的标识就是值本身的哈希值，所以不可能用标识符重新赋值

set查询

集合是非线性结构，无法索引

set遍历

可以遍历

set的成员运算符

可以使用 in，not in

效率怎样？-- 效率高，因为集合内部使用哈希值来标记元素

list和set成员运算符的效率比较

根本不是一个量级的对比......

# python3 -m timeit -r 5 -n 5 -s "s = set(range(10000000))" "print(-1 in s)"      
5 loops, best of 5: 9.02 usec per loop

# python3 -m timeit -r 5 -n 5 -s "lst = list(range(10000000))" "print(-1 in lst)"  
5 loops, best of 5: 117 msec per loop

set和线性结构

线性结构的查询的时间复杂度是O(n)，即随着数据规模的增大而增加耗时

set、dict等结构，内部使用hash值作为key，时间复杂度可以做到O(1)，查询时间和数据规模无关

可hash的对象有哪些

• 数值型：int、float、complex
• 布尔型
• 字符串、bytes
• tuple
• None

以上都是不可变类型，是可哈希类型（hashable）

再次强调：set的元素必须是hashable的

集合

基本概念

• 全集
  • 所有元素的集合。例如实数集，所有实数组成的集合就是实数集。
• 子集和超集
  • 一个集合A所有的元素都在另一个集合B内，则A是B的子集，B是A的超集。
• 真子集和真超集
  • A是B的子集，且A并不等B，A就是B的真子集，B是A的真超集。
• 并集
  • 多个集合合并的结果
• 交集
  • 多个集合的公共部分
• 差集
  • 集合中除去和其他集合的公共部分

集合运算

并集

将两个集合A和B的所有元素合并到一起，组成的集合称作集合A和集合B的并集。

union(*others) # 返回和多个集合合并之后的新的集合

| # 运算符重载，等同union

update(*others) # 和多个集合合并，就地修改

|= # 等同于update

交集

集合A和B，由所有属于A且属于B的元素组成的集合。

intersection(*others) # 返回和多个集合的交集

& # 和intersection一样

intersection_update(*others) # 获取和多个集合的交集，并就地修改

&= # 和intersection_update一样

差集

集合A和B，由所有属于A且不属于B的元素组成。

difference(*others) # 返回和多个集合的差集

- # 等同difference

difference_update(*others) # 获取和多个集合的差集

-= # 等同于difference_update

对称差集

集合A和B，由所有不属于A和B的交集的元素组成。

symmetric_difference(other) # 返回和另一个集合的对称差集

^ # 和symmetric_difference一样

symmetric_difference_update(other) # 获取和另外一个集合的对称差集就地修改

^= # 等同于symmetric_difference_update

就地修改：使用函数的集合会被修改，且没有返回值

返回：调用以上方法的集合不会被修改，有返回值，返回值就是想要的结果

判断运算

issubset(other) 或者 <=

• 判断当前集合是否是另一个集合的子集

A < B

• 判断集合A是否是B的真子集

issuperset(other)、>=

• 判断当前集合是否是另一个集合的超集

A > B

• 判断集合A是不是B的真超集

isdisjiont(other)

• 当前集合和另外一个集合没有交集
• 没有交集，返回True

集合的应用场景

• 共同好友（交集）
• 微信群提醒
  • 提醒XXX与群里的其他人不是微信朋友关系
    • 并集求微信好友，然后判断XXX是否在这个并集里面
    • 群里所有其他人IDs都不在XXX的微信好友集合T中，即 T & IDs == set()
• 权限判断
  • 有一个API，需要同时具备权限A\B\C才能访问，用户的权限是B\C\D，判断用户能否访问该API
    • API集合A，用户权限集合B。要求B中包含A的所有元素。
    • 方法一：A - P = set()
      • 差集为空，说明P包含A
    • 方法二：A.issubset(B)
      • B是A的子集
    • 方法三：A & P = A
      • 合集是A，说明A包含P
  • 有一个API，需要同时具备权限A\B\C任意一项就能访问，用户的权限是B\C\D，判断用户能否访问该API
    • API集合A，用户权限集合B，要求有交集。
      • 方法一：A & P != set()
        • 交集不为空
      • 方法二：A.isdisjoint(P) == False
        • A、P是有交集的
• 一个总任务列表，存储所有任务。一个完成的任务列表。找出未完成的任务列表（差集）
  • 业务中，任务ID一般不可重复
  • 所有任务ID放到一个set中，假设为ALL
  • 所有已经完成的任务放到一个set中，假设为COMPLETED，他是ALL的子集
  • ALL - COMPLETED = UN COMPLETED，差集就是未完成的任务集合

练习

随机生成两个10个数字的列表，每个数字取值范围【10，20】，如：

​ a = [19, 15, 19, 10, 15, 13, 14, 16, 12, 13]

​ b = [10, 14, 11, 14, 10, 15, 10, 13, 10, 19]

统计20个数字之中，一共有多少不同的数字？

2组之间进行比较，不同的数字有几个，分别是什么？

2组之间进行比较，相同的数字有几个，分别是什么？

import random

lst_1 = random.choices(list(range(10, 20)), k=10)
lst_2 = random.choices(list(range(10, 20)), k=10)
print(lst_1)
print(lst_2)

set1 = set(lst_1)
set2 = set(lst_2)
print()
print('20个数字中有{}个不同的数字'.format(len(set1 | set2)))
print()
print('2组之间进行比较，不同的数字有{}个，分别是{}'.format(len(set1.symmetric_difference(set2)), set1.symmetric_difference(set2)))
print()
print('2组之间进行比较，相同的数字有{}个，分别是{}'.format(len(set1.intersection(set2)), set1.intersection(set2)))

>>> [17, 19, 19, 10, 13, 18, 18, 12, 10, 18]
>>> [14, 19, 19, 17, 12, 16, 17, 14, 13, 14]
>>> 
>>> 20个数字中有8个不同的数字
>>> 
>>> 2组之间进行比较，不同的数字有4个，分别是{16, 18, 10, 14}
>>> 
>>> 2组之间进行比较，相同的数字有4个，分别是{17, 19, 12, 13}