python逻辑讲解_python10set详解

集 set

约定

set 翻译为集

collection 翻译集合类型&＃xff0c;是一个大概念

set

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

但是也有顺序集合&＃xff0c;比如java当中的treeset&＃xff0c;有排序的

集当中的元素是散放的&＃xff0c;是一个散列值&＃xff0c;是个哈希。

python当中所有数据结构&＃xff0c;在其他语言当中都能够找到。

列表更适合尾部追加&＃xff0c;两头要操作就要用queue。

前面学过的可变的&＃xff0c;就是bytearray,list。

可变不可变&＃xff0c;指的就是能不能就地修改。

集合当中的元素&＃xff0c;本身就是不能重复的。

集合最大的一个用处&＃xff0c;就是去重。

set定义 初始化

set() -> new empty set object

set(iterable) -> new set object

s1 &＃61; set()

s2 &＃61; set(range(5))

s3 &＃61; set(list(range(10)))

s4 &＃61; {} # dict

s5 &＃61; {9,10,11} # set

s6 &＃61; {(1,2),3,&＃39;a&＃39;}

s7 &＃61; {[1],(1,)1} # ?

s &＃61; set(enumerate(range(10)))

s &＃61; set(range(10))

s &＃61; {}

type(s) # dict&＃xff0c;集合当中什么都不写&＃xff0c;这个就是字典了

s &＃61; {1}

type(s) # set

s1 &＃61; set() # 这个才是定义一个空的字典。

s &＃61; {(1,2),2,None}

s &＃61; {(1,2),2,None,&＃39;abc&＃39;,b&＃39;abc&＃39;,[1]} # unhashable type : &＃39;list&＃39;

# list是一个不可哈希类型的。

# set当中的元素&＃xff0c;要么都是不可变类型&＃xff0c;要么就是一个单值。

s &＃61; {(1,2),2,None,&＃39;abc&＃39;,b&＃39;abc&＃39;,bytearray(b&＃39;abc&＃39;)}

集合很重要的一个特点&＃xff0c;就是无序、去重。

在python当中有可变不可变的区别。

set的元素

set的元素必须可以hash

目前学过的不可hash的类型有list,set

元素不可以索引

set可以迭代

hash(&＃39;abc&＃39;)

hash(b&＃39;abc&＃39;)

上面两个哈希值一样

hash(10000000)

hash(1)

s &＃61; set([&＃39;abc&＃39;,b&＃39;abc&＃39;]) # &＃39;abc&＃39;,b&＃39;abc&＃39;两个哈希值一样&＃xff0c;但是可以存进去的。

set??

set(s)

无序是迭代的&＃xff0c;不可以索引&＃xff0c;成员运算符&＃xff0c;是可以的。

set增加

add(element)

增加一个元素到set当中

如果元素存在&＃xff0c;什么都不做

update(*others

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

参数others必须是可迭代对象

就地修改

s &＃61; add(2)

s &＃61; update({1,2,3}) # 这个就是在做集合运算了

s &＃61; update([1,2,3],[1,3,4]) # 给了两个集合&＃xff0c;把多个集合合并到当前集合

s &＃61; update([1,2,3],[1,3,4],(11,23,45))

s &＃61; update([1,2,3],[1,3,4],[11,23,45])

set删除

remove(element)

从set中移除一个元素

元素不存在&＃xff0c;抛出来keyError异常

discard(element)

从set中移除一个元素

元素不存在&＃xff0c;什么都不做

pop() -> item

移除并返回任意的元素&＃xff0c;为什么是任意元素

空集返回KeyError异常

clear()

移除所有元素

移除的方式&＃xff0c;就是求了元素的哈希值。

顺序结构的移除&＃xff0c;就是要遍历一遍的。用索引&＃xff0c;找的过程很快。

找到这个值&＃xff0c;就是O(1)的。

但是移除这个值之后&＃xff0c;后面的元素都要向前补充一下&＃xff0c;所以速度慢。

但是集合是通过值的hash来进行移除的&＃xff0c;这个hash就是相当于值的key。

移除了之后&＃xff0c;大家也不用移动位置。

所以效率还是很高的。

pop?

help(s.pop())

s.pop()当中不要传参数

a &＃61; s.pop()

remove和pop都是要产生异常的&＃xff0c;用的时候要注意异常处理

discard是弃用的意思&＃xff0c;元素不存在&＃xff0c;什么都不做&＃xff0c;应该是比较安全的方法&＃xff0c;相对于remove

这里remove和pop都会面临到异常处理的问题&＃xff0c;discard就没有这个问题。

总结&＃xff1a;

1. remove() 有异常处理

2. pop() 有异常处理

3. discard() 无异常处理

4. clear() 无异常处理

移除元素&＃xff0c;都会面临到一个垃圾回收的问题。

set修改、查询

修改

要么删除&＃xff0c;要么加入新的元素&＃xff0c;因为没有重复的元素&＃xff0c;修改就是新的。

为什么没有修改&＃xff1f;

查询

非线性结构&＃xff0c;无法索引

遍历

可以迭代所有元素

成员运算符

in 和 not in判断元素是否在set当中

效率呢&＃xff1f;

这个效率是相当高的&＃xff0c;相当于用索引访问线性结构

非线性结构用哈希值来定位&＃xff0c;相当于用索引遍历列表

时间复杂度&＃xff0c;就是相当于O(1)

set成员运算符的比较

list和set的比较

lst1 &＃61; list(range(100))

lst2 &＃61; list(range(1000000))

-1 in lst1、-1 in lst2 看看效率&＃xff0c;随着规模的增加&＃xff0c;应该时间会很低。

set1 &＃61; set(range(100))

set2 &＃61; set(range(1000000))

-1 in set1、-1 in set2 看看效率&＃xff0c;随着规模的增加&＃xff0c;应该没有多大区别。

%%timeit lst1 &＃61; list(range(100))

-1 in lst1 # 这个就是true或者false的问题。-1必须遍历全部。

%%timeit set1 &＃61; set(range(100)) # set_up_code 不计时了

-1 in set1 # 这个就是true或者false的问题。-1必须遍历全部。

当我们判断或者迭代的时候&＃xff0c;用set效率会更高。

set和线性结构

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

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

可hash

数值型&＃xff1a;int float complex # 字面常量

布尔值&＃xff1a;True False # 整形的子类

字符串&＃xff1a;String bytes # 字面常量

tuple

None

以上都是不可变类型&＃xff0c;成为可哈希类型&＃xff0c;hashable

set的元素必须是可以hash的。

这里不要和可迭代对象搞混了&＃xff0c;只要可迭代对象当中的元素是可以哈希的&＃xff0c;那么就可以

s &＃61; set(list)这种用法

集合

基本概念

全集

所有元素的集合&＃xff0c;例如实数集&＃xff0c;所有实数组成的集合&＃xff0c;就是全集

子集subset和超集superset

一个集合A所有元素都在另外一个集合B内&＃xff0c;A是B的子集&＃xff0c;B是A的超集

真子集合真超集

A是B的子集&＃xff0c;且A不等于B&＃xff0c;A就是B的真子集&＃xff0c;B就是A的真超集

并集&＃xff1a;多个集合合并的结果

交集&＃xff1a;多个集合的公共部分

差集&＃xff1a;集合当中除去和其他集合公共部分

集合类型当中用的最多的&＃xff0c;就是list&＃xff0c;和dict。

循环和递归&＃xff0c;刚释放变量&＃xff0c;一定要释放一下&＃xff0c;

尤其是用到大数据规模的情况下&＃xff0c;一定要测试一下。

可能会出现内存被耗尽的情况。

本来是虚拟地址&＃xff0c;内存不够开了&＃xff0c;

就要将内存当中的数据&＃xff0c;不常用的&＃xff0c;导入到swap当中&＃xff0c;

windows当中叫做虚拟内存。

本来磁盘都是机械装置&＃xff0c;有一个寻道。

速度是很慢的。

所以从内存到swap&＃xff0c;从swap到内存&＃xff0c;是很慢的。

磁盘大多数都是随机访问的。

所以&＃xff0c;磁盘比磁带的好处&＃xff0c;在于把顺序变成随机的。

后来出现了电路&＃xff0c;后来出现了固态硬盘。

后来不用机械式了。

还是有寻道的问题&＃xff0c;还有生产的良品率的问题。

你还要求空间比较小。

所以磁盘还是大量应用的。

遇到磁盘的时候&＃xff0c;一定要小心&＃xff0c;一定有考虑效率。

尽量要放在内存当中用。

但是不用磁盘也不行&＃xff0c;没有副本&＃xff0c;就没办法冗余了。

一边计算一边落地&＃xff0c;有很多问题是需要考虑的。

线性结构的查询是随着规模变大就很耗时了。

所以一般规模比较大的时候&＃xff0c;就要用到排序&＃xff0c;

然后我们再进行查询&＃xff0c;这个就很好了。

就不用顺序查找了&＃xff0c;就可以折半了。

对于非线性结构&＃xff0c;列表类似于数组&＃xff0c;但是包装的要多一点。

set和dict&＃xff0c;这几个东西&＃xff0c;一定要搞清楚。

有这三个东西&＃xff0c;基本上可以走遍天下了。

但是set和dict可以理解为一种&＃xff0c;set可以理解成为特殊的字典。

内部使用hash作为key&＃xff0c;有一个hash空间的问题。

有的叫哈希桶的&＃xff0c;用来指代很大的散列空间&＃xff0c;叫做值域。

值是散列的&＃xff0c;是稀疏的。

基于hash的&＃xff0c;时间复杂度&＃xff0c;可以做到big O(1)

现在没有提空间复杂度。

空间复杂度&＃xff0c;比如冒泡法&＃xff0c;就开辟了一个temp&＃xff0c;就多了一个。

空间复杂度&＃xff0c;杨辉三角的时候&＃xff0c;就有很大差异。

算法&＃xff0c;就要空间复杂度和时间复杂度&＃xff0c;都要优化好。

append的&＃xff0c;空间复杂度就很高。

集合运算

并集

将两个集合A和B的所有的元素合并到一起&＃xff0c;组成的集合称作集合A与集合B的并集

union(*others)

返回和多个集合合并后的新的集合

| 运算符重载

等同 union

update(*others)

和多个集合合并&＃xff0c;就地修改

|&＃61;

等同update

union就是联合&＃xff0c;合并的意思&＃xff0c;可以用|符号

update&＃xff0c;多个集合的合并&＃xff0c;是就地修改的。

|&＃61;&＃xff0c;相当于&＃43;&＃61;

a |&＃61; {1,2} | {2,3}

交集

集合A和B&＃xff0c;由所有属于A且属于B的元素组成的集合

intersection(*others)

返回和多个集合的交集

&

等同于intersection

intersection_update(*others)

获取和多个集合的交集&＃xff0c;并就地修改

&&＃61;

等同intersection_update

差集

集合A和B&＃xff0c;由所有属于A且不属于B的元素组成的集合

difference(*others

返回和多个集合的差集

等同于difference

difference_update(*others)

获取和多个集合的差集&＃xff0c;并就地修改

-&＃61;

等同difference_update

对称差集

集合A和B&＃xff0c;由所有不属于A和B的交集元素组成的集合&＃xff0c;记作(A-B)U(B-A)

symmetric_differenc(other)

返回和另一个集合的差集

^

等同于symmetric_differece

symmetric_difference_update(other)

获取和另外一个集合的差集并就地修改

^&＃61;

等同symmetric_difference_update

issubset(other)、<&＃61;

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

set1

判断set1是否是set2的真子集

issuperset(other)、>&＃61;

判断当前集合是否是other的超集

set1 > set2

判断set1是否是set的真超集

isdisjoint(other)

当前集合和另一个集合没有交集

没有交集&＃xff0c;返回True

集合应用

共同好友

你的好友是ABC&＃xff0c;他的好友是CBD&＃xff0c;你们的共同好友是谁&＃xff1f; FOF算法。

有了共同好友&＃xff0c;才可以推荐

在生产过程当中基本上就是在redis当中做集合运算的。

交集问题&＃xff1a;{&＃39;A&＃39;,&＃39;B&＃39;,&＃39;C&＃39;}.intersection({&＃39;B&＃39;,&＃39;C&＃39;,&＃39;D&＃39;})

微信群提醒

XXX与群里其他人都不是微信朋友关系

你要把业务映射成为脑子当中的逻辑

每个人登录会加载自己的好友信息&＃xff0c;如果用select语句去查数据库&＃xff0c;就是相当的复杂

并集&＃xff1a;user id(A|B|C|...) &＃61;&＃61; False,A、B、C等是微信好友的并集&＃xff0c;用户ID不在这个并集当中&＃xff0c;说明他和任何人都不是朋友。

权限判断

有一个API&＃xff0c;要求权限同时具备A、B、C才能访问&＃xff0c;用户权限是B、C、D&＃xff0c;判断用户是否能够访问该API

有一个API&＃xff0c;要求权限具备A、B、C任意一项就可以访问&＃xff0c;用户权限是B、C、D&＃xff0c;判断用户是否能够访问该API

API集合A&＃xff0c;权限集合P

A-P &＃61; {}&＃xff0c;A-P为空集&＃xff0c;说明P包含A

A.issubset(P)也行&＃xff0c;A是P的子集也行

A & P &＃61; A也行

API集合A&＃xff0c;权限集合P

A & P &＃xff01;&＃61;{} 就可以

A.isdisjoint(P)&＃61;&＃61;False 表示有交集

一个总任务列表&＃xff0c;存储所有任务&＃xff0c;一个完成的任务列表&＃xff0c;找出没有完成的任务。

业务中&＃xff0c;任务ID一般不可以重复

所有任务ID放到一个set当中&＃xff0c;假设为ALL

所有已完成的任务ID放到一个set当中&＃xff0c;假设为COMPLETED&＃xff0c;它是ALL的子集。

ALL - COMPLETED &＃61; UNCOMPLETED

集合练习

随机产生2组各10个数字的列表&＃xff0c;如下要求

每个数字取值范围[10,20]

统计20个数字当中&＃xff0c;一共有多少个不同的数字&＃xff1f;

2组当中&＃xff0c;不重复的数字有几个&＃xff1f;分别是什么&＃xff1f;

2组当中&＃xff0c;重复的数字有几个&＃xff1f;分别是什么&＃xff1f;

import random

a &＃61; []

b &＃61; []

num &＃61; list(range(10,21))

for _ in range(10);

a.append(random.randrange(10,21))

b.append(random.randrange(10,21))

#a &＃61; [1,9,7,5,6,7,8,8,2,6]

#b &＃61; [1,9,0,5,6,4,8,3,2,3]

#--------------------------

s1 &＃61; set(a)

s2 &＃61; set(b)

print(s1)

print(s2)

print(s1.union(s2)) # 并集

print(s1.symmetric_differece(s2)) # 对称差集

print(s1.intersection(s2)) # 交集

集合运算做小集合&＃xff0c;问题不大的。

两个集合&＃xff0c;如果都是10万级别的&＃xff0c;求并集&＃xff0c;要么修改自身&＃xff0c;要么产生新的集合。

如果三个、四个10万的集合交集、并集、差集呢&＃xff1f;

这个时候最好就要测试一下。

内存有的情况&＃xff0c;就是可以开辟。

内存没有的时候&＃xff0c;就是要考虑垃圾回收&＃xff0c;要考虑程序效率了。

这个时候更要考虑空间复杂度。

Java、Python都要考虑这个问题&＃xff0c;虚拟机语言。

C&＃43;&＃43;就没有垃圾回收&＃xff0c;就会容易产生内存碎片。

内存空洞、碎片&＃xff0c;那么如何开辟大内存。

减少数据库负担的时候&＃xff0c;拿出来的数据就要常驻内存。

集合运算我们要用&＃xff0c;字典运算很少听到。