1.基础

1.1 概念

集合，简称集。由任意个元素构成的集体。高级语言都实现了这个非常重要的数据结构模型类型。Python中，它是 可变的、无序的、不重复的元素的集合。

1.2 初始化

set()-> new empty set object
set(iterable) -> new set object

1
2
3
4
5
6
7
8
9
s1 = set()
s2 = set(range(5))
s3 = set([1,2,3])
s4 = set('abcdefg')

s5 = {}
s6 = {1,2,3}
s7 = {1,(1,)}
s8 = {1,(1,),[1]}

1.3 元素性质

去重: 在集合中，所有元素必须想异
无需：因为无需，所以 不可索引
可哈希：Python集合中的元素必须可以hash，即元素都可以使用内建函数hash(不可hash类型: list、set、bytearray)

1.4 增删

add(elem)

  • 增加一个元素到set中，如果元素存在，则不写入(去重)
    update(*others)
  • 合并其他元素到set中，参数others必须为 可迭代对象
    就地修改
1
2
3
s = set()
s.add(1)
s.update((1,2,3),[2,3,4])

remove(elem)

  • 从set中移除一个元素
  • 元素不存在，抛出KeyError非ValueError

discard(elem)

  • 从set中移除一个元素
  • 元素不存在，不抛出异常

clear()

  • 移除所有元素(将set引用计数清零)

1.5 检索时间复杂度

list与set都可以实现检索，那么谁的速度更快，时间复杂度如何？
list是一个线性数据结构，搜索元素的时间复杂度是O(n),随着时间规模增加耗时增大
示例对比检索速度

1
2
3
4
5
6
7
8
9
10
11
import timeit

setup_code = """
b = list(range(1000000))
"""
code_to_test = """
-1 in b
"""

timer = timeit.timeit(stmt=code_to_test, setup=setup_code,number=100)
print("执行时间：", timer)

执行后，耗时：0.7413969000335783

1
2
3
4
5
6
7
8
9
10
11
import timeit

setup_code = """
b = set(range(1000000))
"""
code_to_test = """
-1 in b
"""

timer = timeit.timeit(stmt=code_to_test, setup=setup_code,number=100)
print("执行：", timer)

执行后，耗时：8.09994526207447e-06

通过上面的实例，可以看出set的耗时小的多，这是因为set是一个非线性数据结构，set使用hash表实现，内部使用hash值作为key，时间复杂度为O(1),查询时间和数据规模无关，并不会随着数据规模增大而降低搜索性能

2.集合运算

2.1 并集

1
2
3
4
5
a = {1,2,3}
b = {2,3,4,5}
s = a.union(b) # a | b
a.update({15,20}) # a |= {10,15}
print(s,a)
1
2
3
4
a = {1,2,3}
b = {2,3,4,5}
s = a.intersection(a,b) # a & b
print(s)

注: 为空集时，python表达为 set()

1
2
3
4
a = {1,2,3}
b = {2,3,4,5}
s = a.difference(b) # a - b
print(s)

集合A与B，由所有不属于A和B交集元素组成(A-B)U(B-A)

1
2
3
4
a = {1,2,3}
b = {2,3,4,5}
s = a.symmetric_difference(b) # a ^ b
print(s)
1
2
3
4
5
6
7
a = {1,2,3}
b = {1,2,3,4,5}
c = {1,2,3,4,5}
print(f'a是b的子集吗？:{a<=b}')
print(f'b是c的真子集吗？:{b<c}')
print(f'a是b的超集吗？:{a>=b}')
print(f'c是a的真超集吗？:{c>=a}')

3.练习

1.共同好友

  • 你的好友A、B、C，他的好友C、B、D，求共同好友
1
2
3
friend1 = {'A', 'B', 'C'}
friend2 = {'C', 'B', 'D'}
print(friend1 & friend2)

2.权限判断

  • 有一个API，:要求权限同时具备A、B、C才能访问，用户权限是B、C、D，判断用户是否能够访问该API
1
2
3
4
5
6
api = {'A', 'B', 'C'}
user = {'B', 'C', 'D'}
if api <= user: 
  print('用户有权限访问')
else:
  print('用户无权限访问')
  • 有一个API，要求权限具备A、B、C任意一项就可访问，用户权限是B、C、D，判断用户是否0能够访问该API
1
2
3
4
5
6
api = {'A', 'B', 'C'}
user = {'B', 'C', 'D'}
if api & user != set():
  print('用户有权限访问')
else:
  print('用户无权限访问')

3.一个总任务列表，存储所有任务。一个已完成的任务列表。找出为未完成的任务

1
2
3
ALL = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
completed = {2, 4, 6, 8, 10}
print(f'未完成任务： {ALL - completed}')

5.随机产生2组各10个数字的列表，如下要求:.

  • 每个数字取值范围[10,20]
  • 统计20个数字中，一共有多少个不同的数字?0
  • 2组之间进行比较，不重复的数字有几个？分别是什么
  • 2组之间进行比较，重复的数字有几个？跟别是什么
1
2
3
4
5
6
7
8
9
10
import random
g1, g2 = [], []
for i in range(10):
  g1.append(random.randint(10, 20))
  g2.append(random.randint(10, 20))
s1, s2 = set(g1), set(g2)
print(s1, s2)
print(f'一共有{len(s1 | s2)}个不同的数字，分别是{s1 | s2}')
print(f'2组之间比较，不重复的数字有{len(s1 ^ s2)}，分别是{s1 ^ s2}')
print(f'2组之间比较,重复的数字有{len(s1 & s2)},分别是{s1 & s2}')