专栏首页小白的技术客栈Python内置数据结构之集合

Python内置数据结构之集合

今天给大家介绍内置数据结构集合的用法。

看一下集合的思维导图:

集合的特点

  1. 元素是唯一的
  2. 元素是无序的,不是线性结构
  3. 集合元素是可hash的
  4. 聚合的含义和数学上的含义相同

集合的操作

  1. 增:addupdate
  2. 删:remove,discard,clear,pop
  3. 集合运算:union,intersection,difference, symmetric_difference
  4. 集合判断:issubset,issupperset,isdisjoint

具体实例

在Python中怎么定义一个集合呢?

s = set()  # 使用内置的set方法
>>> s = set()
>>> s
set()
>>> type(s)
<class 'set'>
# 可以给集合赋初值
s = {1, 2, 3} # 使用大括号

# 但不能使用如下形式的定义集合
s = {} # 不能这么定义集合,使用type方法查看s的类型
>>> s = {}
>>> type(s)
<class 'dict'>
s = {1, 2, 3}
type(s)
set

add方法,

s = {1, 2, 3}
s
s.add(4)
s
s.add(4)
>>> s.add('a')
>>> s
{'a', 1, 2, 3, 4}

# add一个列表
>>> s.add([4, 5, 6])
TypeError: unhashable type: 'list'
# 为什么不能增加一个列表呢?由于集合使用hash来判断元素是否重复;
# 由于列表是不能hash的,所以,集合的add方法不能增加一个列表到
# 已有的集合中

# add一个字符串
>>> s.add('abcde')
>>> s
{1, 2, 3, 4, 'a', 'abcde'}

# add一个元组
>>> s.add((1, 2, 3))
>>> s
{1, 2, 3, 4, (1, 2, 3), 'a', 'abcde'}

# add一个类的实例
class A:
    pass

a = A()
hash(a)

当add一个已经存在的元素时,不会发生任何改变。

重要 为什么不能增加一个列表呢?由于集合使用hash来判断元素是否重复;由于列表是不能hash的,所以,集合的add方法不能增加一个列表到已有的集合中。内置数据类型中,可变的都是不可哈希的,而不可变的类型是可哈希的。list,set,bytearray,dict是不可hash的,所以不能作为set的元素;通常来说,内置类型,不可变类型是可hash的,可变类型是不可hash的。

update方法,

s = {1, 2, 3, 4}
s.update([3, 4, 5, 6])
s # 已经把重复的元素去重了
set([1, 2, 3, 4])

# 使用set去重一个list
list(set([1, 3, 2, 1, 2, 4]))

删除的方法,

# remove方法,但要移除的元素必须存在
s = {1, 2, 3, 4}
s.remove(1)  # 移除一个存在的
s.remove(10) # 移除一个不存在的

# discard方法,不要求要删除的元素是否存在于集合中
s.discard(2)  # 移除一个存在的
s.discard(20) # 移除一个不存在的

# pop方法,会随机移除一个元素,但要求集合为非空
s = {3, 4, 5, 6}
s.pop()
s

# clear方法,清除集合中的所有元素
s.clear()

删除集合元素总结:

  1. remove删除指定的元素,元素不存在抛出KeyError
  2. discard删除指定的元素,元素不存在,什么也不做
  3. pop随机删除一个元素并返回,集合为空,抛出KeyError
  4. clear清空集合

集合的修改和查找,

没有一个方法可以直接的修改集合中的某个具体元素;因为没有一个方法,可以定位
其中的某个具体元素。

集合不能通过索引访问。集合没有访问单个元素的方法。集合不是线性结构,集合元素没有顺序。

集合也是可迭代的对象,

for x in set('lavenliu'):
    print(x)

集合可以用成员运算法,线性结构的成员运算,时间复杂度是O(n),集合的成员运算,时间复杂度是O(1)。

'l' in set('lavenliu')

集合的成员运算和其他线性结构的时间复杂度不同。做成员运算的时候,集合的效率远高于列表。集合的效率和集合的规模无关。

In[7]: lst = list(range(1000000))

In[8]: %%timeit
   ...: -1 in lst
   ...: 
100 loops, best of 3: 13.7 ms per loop

In[9]: lst = list(range(100000))

In[10]: %%timeit
    ...: -1 in lst
    ...: 
1000 loops, best of 3: 1.39 ms per loop

In[11]: s2 = set(range(1000000))

In[12]: %%timeit
    ...: -1 in s2
    ...: 
10000000 loops, best of 3: 57.5 ns per loop

In[13]: s2 = set(range(100))

In[14]: %%timeit
    ...: -1 in s2
    ...: 

10000000 loops, best of 3: 58.4 ns per loop

In[15]: 

时间复杂度:

O(1)    常数复杂度
O(logn) 对数复杂度
O(n)    线性复杂度
O(n^2)  平方复杂度
O(n^3)  立方复杂度
O(2^n)  指数复杂度
O(n!)   阶乘复杂度

集合的集合运算

集合的运算:

  1. 并集union
  2. 交集intersection
  3. 差集difference
  4. 对称差集symmetric_difference

存在集合A和B,对于集合C,如果C的每个元素既是A的元素,又是B的元素,并且A和B所有相同的元素都在C找到,那么C是A和B的交集。

集合A和B,当集合C的元素仅存在A中,但不存在B中,并且A中存在B中不存在的元素全部存在C中,那么C是A和B的差集。

如果把两个集合A和B看成是一个全集,对称差集是交集的补集。

实例演示,

a = {1, 2, 3}
b = {2, 3, 4}

# 并集
a.union(b)
# 集合重载了按位或运算符,用于集合的并集运算
a | b
# 并集的update版本
a.update(b)
a # {1, 2, 3, 4}

# 交集,不修改原来的集合,会返回新的集合
# 集合的交集运算,重载按位与运算符为交集运算。
# a.intersection(b) 等效于 a & b
a.intersection(b)
a & b # {2, 3}

a.instersection_update(b) # instersection_update版本会原地修改,返回None
# a = a.insertsection(b)
# a = {2, 3}
# b = {2, 3, 4}

# 差集
# 差集没有交换律
a.difference(b)
a - b # {1}

# 差集也有update版本
a.difference_update(b) # 相当于a = a.difference(b)
a # {1}

# 集合的差集运算,重载减法运算符为交集运算。
# a.difference(b) 等效于 a - b
a - b # {1}

# 对称差集
# 对称差集具有交换律
a.symmetric_difference(b)
# 集合的差集运算,重载异或运算符为对称差集运算。
a ^ b # {1, 4} # 得到的结果是a和b的非相同元素,(a | b) - (a & b)

# 对称差集也有update版本
a.symmetric_difference_update(b) # 原地修改,返回None。相当于a = a.symmetric_difference(b)


# 其他一些特性
a.union(b) == b.union(a)
a.intersection(b) == b.intersection(a)
a.difference(b) == b.difference(a)
a.symmetric_difference == b.symmetric_difference(a)

集合相关的判断。超集与子集,isuperset,issubset

a = {1, 2, 3, 4}
b = {3, 4}
a.issuperset(b)
b.issubset(a)
a.issuperset(a)
b.issubset(a)

isdisjoint方法判断两个集合是否不相交,如果有交集返回False,没有交集返回True。

a.isdisjoint(b)
a.isdisjoint({5, 6})

一个例子:

def issubset(s1, s2):
    for x in s1:
        if x not in s2:
            return False
    return True

def issuperset(s1, s2):
    for x in s2:
        if x not in s1:
            return False
    return True

集合的应用

  1. 元素需要唯一,而对顺序没有要求
  2. 需要集合运算时

举几个具体场景的例子,

# 用户输入了一批主机,这些主机肯定不能重复,可以这样来处理
# 这样,就不会在机器上执行重复的操作了
hosts = set(user_input.splitlines())

# 得到还在集合中的机器列表
in_progress_hosts = hosts - complete_hosts

# 获得用户的所有输入的主机
hosts = input_a | input_b | input_c

# 对多个目录下的文件去重

有一个API,它要有认证,并且有一定权限才可以访问,例如,要求满足权限A,B,C中任意一项,有一个用户具有权限B,C,D,那么此用户是否有权限访问此API。(判断是否集合是否相交,返回False说明相交,说明具有访问权限)

有一个任务列表,存储全部的任务,有一个列表,存储已经完成的任务,找出未完成的任务。

集合的限制

  1. 列表不能作为集合的元素
  2. bytearray不能作为集合的元素
  3. 集合不能作为集合的元素
  4. 元组与bytes可以作为集合的元素

可变元素不能成为集合的元素。集合元素必须可hash。目前我们所知道的所有可变的数据类型是不可hash的,所有的不可变的数据类型都是可hash的。

本文分享自微信公众号 - 小白的技术客栈(XBDJSKZ),作者:lavenliu.cn

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 记一次Linux被入侵的经历

    Linux入侵经历 被入侵的一次经历 今天给大家说说一次被入侵的经历,仅供大家参考。 ? 事件起因 2017年9月7日下午测试带宽,登录到服务器。在/tmp目...

    1846122963
  • Python函数基础知多少

    函数基础 简单地说,一个函数就是一组Python语句的组合,它们可以在程序中运行一次或多次运行。Python中的函数在其他语言中也叫做过程或子例程,那么这些被...

    1846122963
  • Python内置数据结构之字符串

    字符串 今天跟大家来说一说Python中的字符串数据结构。 ? 上文回顾 让我们回顾一下可变类型及不可变类型: 不可变数据类型:str、int、tuple ...

    1846122963
  • 2018-09-21 JAVA的集合类关系总结,基础知识太不扎实了

    *面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就对对象进行存储,集合就是存储对象最常用的一种方式。

    Albert陈凯
  • Javascript[0x09] -- 集合

    实现的时候一个巧妙的点,是使用对象而不是数组表示集合,我们知道Javascript中一个键只有一个值。

    丰臣正一
  • java.util.Collection[源码解读(上)]

    本文主要介绍Collection接口的用途。接口的作用是什么呢?我的理解是四个字:制定标准。就像USB接口,尺寸、结构、排线都是统一的,只要是标准USB设备,都...

    小诸葛
  • 4.93Python数据类型之(8)集合

    py3study
  • 魔术里的集合、映射和关系(二)——集合怎么用?

    要知道,集合本身代表的是真真切切的对象的总体,而我们日常交流中又不可能真的把这些实物拿过来才能表示相应的集合,因此,我们需要用一组数学符号来代表这些真实的集合,...

    magic2728
  • HDU 2034 人见人爱A-B

    人见人爱A-B Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

    Angel_Kitty
  • NLP入门之形式语言与自动机学习(一)

    第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

    云时之间

扫码关注云+社区

领取腾讯云代金券