前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >数据类型第2篇「字典和集合的原理和应用」

数据类型第2篇「字典和集合的原理和应用」

作者头像
清菡
发布于 2021-01-04 06:34:47
发布于 2021-01-04 06:34:47
1.1K00
代码可运行
举报
文章被收录于专栏:清菡软件测试清菡软件测试
运行总次数:0
代码可运行

作者:清菡 博客:oschina、云+社区、知乎等各大平台都有。

由于微信公众号推送改为了信息流的形式,防止走丢,请给加个星标 ⭐,你就可以第一时间接收到本公众号的推送!

目录

  • 一、集合
    • 1.定义个有元素的集合
    • 2.自动去重
    • 3.集合常用的五个方法
  • 二、集合和字典都是无序的
  • 三 、字典和集合都是无序的,在内存中是怎么存储?
    • 1.为什么说字典和集合是无序的?
    • 2.字典查找值的过程
    • 3.Python 里基础数据类型分为三大类
    • 4.为什么会出现散列冲突?
  • 四、可变和不可变元素:可哈希和不可哈希
    • 1.可变类型的数据不可进行哈希运算,不可变的数据类型可进行哈希运算
    • 2.集合为什么无序?
    • 3.散列类型为什么是无序的?
  • 五、性能分析

本篇文章:重点掌握集合的用法即可。

字典,大家都用得特别多,花括号包起来的,一个键一个值构成一个元素。集合和字典的表达形式是一样的。

字典和集合在 Python 中都是使用花括号进行表示的。

一、集合

1.定义个有元素的集合

set1 = {1,2,3}

集合和字典相比,集合里面只有值,没有键。

2.自动去重

集合有个比较强大的功能:自动去重。 里面不会存在重复的元素,集合最常见的应用就是对列表去重。

2.1 把字典转换成集合,再转换回字典,它会真去重
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
set1 = {1,2,3,3,3,4,4,4,4,4}
print(set1)

打印出来是集合,重复的元素自动过滤掉了。定义的时候,不管定义多少个重复元素,都自动过滤掉了。

2.2 用集合对列表去重
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
li = [1,1,1,2,2,2,3,3,3] # 利用集合对列表去重
li2 = list(set(li))
print(li2)

首先把列表转换成一个集合,自动把里面的重复元素给去除掉了,再转换回列表。

集合在 Python 中是用得比较少的数据类型。

3.集合常用的五个方法

add()

添加元素

update()

更新元素

remove()

删除元素

clear()

清空里面所有的元素

copy()

复制元素

集合,它里面的元素是无序的。可以修改,集合是可变类型的数据。

3.1 空集合中怎么添加元素?

add()方法,每次可以往里面添加一个数据进去。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
se = set()  # 空集合
# 集合添加数据
se.add('qinghan') # 一次只能添加一个,所以只添加了一个qinghan
print(se)
3.2 删除用 remove()

集合可以添加也可以删除。删除用remove(),传入对应的元素就可以进行删除。

集合还可以做交集、并集这样的操作,这个对我们用处不大。

3.3update() 更新元素

跟字典的update()一样的。它是将一个集合更新到这个集合里面,可以往里面一次加入多个元素。

通过这个方法:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
se = set()  # 空集合
se.update({111,22,33,44})
print(se)

可以一次更新进去多个元素。

update的源码:

接收的是不定量参数,可以传一个也可以传多个。

可以往里面加元组、列表、字符串,但是一般用的时候选择用集合,将一个集合更新到原来的集合里面。

3.4clear()清空元素

还有个常用的方法:clear()清空里面所有的元素。

3.5 copy()复制元素

copy() # 做一个复制的

二、集合和字典都是无序的

Python 里面把它称作散列类型。

Python 更新到 3.7 之后,字典出现一个新的特性:3.7 之前的字典是无序的。3.7 之后字典中元素的顺序,它会按你依次添加的顺序进行保存。现在字典,里面的元素实际上是有序的。

官方文档已声明:

三 、字典和集合都是无序的,在内存中是怎么存储?

dict 与 set 实现原理是一样的,都是将实际的值放到 list 中。

唯一不同的在于 hash 函数操作的对象,对于 dict,hash 函数操作的是其 key,而对于 set 是直接操作的它的元素。

假设操作内容为 x,其作为因变量,放入 hash 函数,通过运算后取 list 的余数,转化为一个 list 的下标,此下标位置对于 set 而言用来放其本身。

而对于 dict 则是创建了两个 list,一个 list 该下表放此 key,另一个 list 中该下标对应的 value。

其中,我们把实现 set 的方式叫做 Hash Set,实现 dict 的方式叫做 Hash Map/Table(注:map 指的是通过 Key 来寻找 value 的过程)。

1.为什么说字典和集合是无序的?

1.1 字典和集合底层都是存储在列表里面

一个字典,在存储的时候,会拆分成 2 部分,会存在 2 个列表里面,一个列表存键,一个列表存值:

字典存储时的拆分

1.2 怎么通过 Key 找到对应的 Value 值呢?

字典在存储之前,做了个 Hash 操作:

Hash操作如图,图片来自网络

拿到字典的键,进行哈希操作。通过对应的哈希算法,然后得出一串数字。

拿哈希出来的值除以内存分出来的列表的长度,得到余数。这个余数当成对应元素的下标。把键和值通过下标存在列表中对应的位置。

1.3 散列类型的存储过程

散列类型的存储过程,图片来自网络

散列类型的意思就是无序的。 散列就是哈希。散列内部元素是无序的。

刚开始内存分了 12 个格子存数据,哈希后,第一个元素得出的余数是 6,有 2 个列表,会把键存在对应的列表里面,把值存在对应的 6 的位置。

散列表存储数据很松散,不像列表完整得排过来的。散列表里面是分散存储的,会把对应的键存到一个散列表里面。

查找字典中元素的时候,首先它会拿到你这个键,同样进行哈希运算。运算完毕后得出一个值,然后去散列表里面找对应的键。找到对应的键,然后比较下是不是这个键。

字典哈希的是它的键,不是它的值。集合是哈希的它的值,所以集合里面的值是不可变类型的,不能有可变类型的值。

2.字典查找值的过程

字典查找值的过程

散列值就是哈希值。拿到键名,进行哈希,哈希过后得到散列值。

拿到散列值进行相应的运算,然后拿到表元。表元是在散列表中的一个序号。

2.1 第一种情况

比如序号是 6,看 6 里面存的这个键,跟你刚才输进来查找的那个键是不是一样的。

如果是一样的,键相等,会返回表元里面对应的值,会给你找到你所存储的字典的值。

如果它在这里没找到值的话,这个时候会抛出异常。(也就是字典通过键去找值,没找到的时候就会抛出错误。)

2.2 第二种情况
散列冲突:

每个元素哈希出来的结果是不一样的。如图,第一个元素计算出来是 6,会找到散列表中第 6 个格子。第二个值,运算之后,如果得出来的也是个 6,那么这个时候就会起散列冲突。

解决散列冲突有二种方案:

方案一:

有散列冲突的时候,会对散列表进行扩容,扩容后进行重新排序。

方案二:

在后面再加个列表。这样的话,第一个元素计算出来是 6,会找到散列表中第 6 个格子。

第二个值,运算之后,如果得出来的也是个 6,因为加了一个列表(这个列表可存储多个值),就不会起散列冲突了。

以上是字典,散列类型底层存储。

3.Python 里基础数据类型分为三大类

第一类,数值类型: 1 一个数只有单个元素,像这个 1 就是 1。

第二类,序列类型: 字符串、列表、元组。

第三类,散列类型: 字典、集合。特征:内部元素是无序的。

4.为什么会出现散列冲突?

举个栗子:

这两个数据通过哈希,计算散列值,取余后拿到的余数,如果是一样的话,在储存值的时候,就会造成散列冲突。

通过字典的键去哈希,把哈希值存在散列表里面。通过对应的键,然后找到列表中存储的对应元素的值。

集合相对于列表比较简单一些。集合没有键和值,直接拿到集合里面的值进行哈希操作。

四、可变和不可变元素:可哈希和不可哈希

1.可变类型的数据不可进行哈希运算,不可变的数据类型可进行哈希运算。

集合里面只能存储可哈希的对象。意思是集合里面只能存储不可变的数据类型。

例如:set2 = {1,2,3,[1,2]}

这个集合就报错了:

因为列表是可变类型。可变类型是不能进行哈希运算的。

数值类型、字符串、元组可以,列表、字典、集合不能作为元素储存在这个集合里面。

集合里面的元素通过哈希操作算出对应值,放到散列表里面。

2.集合为什么无序?

因为散列表里面存储元素的时候是没有顺序的,散列表也是会不断变化的(会变化长度、调整元素位置的),所以说散列类型是无序的。

3.散列类型为什么是无序的?

通过哈希算法算了之后,然后存到对应的散列表里面,散列表里面数据存储是没有固定顺序的。

五、性能分析

字典最占用内存,其次是集合。然后是列表、元组。元组是占用内存最少的。但是查找元素的时候,集合是速度最快的,然后是字典。

集合用起来不方便,如果知道哪个元素就好查找,但是不知道那个元素在哪里,就不方便从集合里去取那个元素。字典通过键取值,元组、列表通过下标。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-12-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 清菡软件测试 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
机器学习之决策树(Decision Tree)及其Python代码实现
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54927178
大黄大黄大黄
2018/09/14
2.6K0
机器学习之决策树(Decision Tree)及其Python代码实现
机器学习笔记之决策树分类Decision Tree
决策树(decision tree)是一种依托于策略抉择而建立起来的树。机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,从根节点到叶节点所经历的路径对应一个判定测试序列。决策树可以是二叉树或非二叉树,也可以把他看作是 if-else 规则的集合,也可以认为是在特征空间上的条件概率分布。决策树在机器学习模型领域的特殊之处,在于其信息表示的清晰度。决策树通过训练获得的 “知识”,直接形成层次结构。这种结构以这样的方式保存和展示知识,即使是非专家也可以很容易地理解。
Jetpropelledsnake21
2021/03/12
4K0
机器学习笔记之决策树分类Decision Tree
决策树算法:ID3,C4.5,CART
对于基本树我将大致从以下四个方面介绍每一个算法:思想、划分标准、剪枝策略,优缺点。
zhangjiqun
2024/12/14
2680
决策树算法:ID3,C4.5,CART
【白话机器学习】算法理论+实战之决策树
如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的, 常见的机器学习算法:
Datawhale
2020/03/04
7380
【白话机器学习】算法理论+实战之决策树
Machine learning -- C4.5算法详解及Python实现
程序实现部分转自 Wsine的博客小站 地址:http://www.cnblogs.com/wsine/p/5180315.html C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。 C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策
昱良
2018/04/04
2.7K0
Machine learning -- C4.5算法详解及Python实现
决策树之ID3、C4.5、C5.0等五大算法及python实现
版权声明:博主原创文章,微信公众号:素质云笔记,转载请注明来源“素质云博客”,谢谢合作!! https://blog.csdn.net/sinat_26917383/article/details/47617801
悟乙己
2019/05/28
2.7K0
决策树(Decision Tree)C4.5算法
C4.5,是机器学习算法中的另一个分类决策树算法,它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法,也是上节所介绍的ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。
Ai学习的老章
2019/04/08
1.7K0
决策树(Decision Tree)C4.5算法
决策树 C4.5算法
小小程序员
2023/12/06
3260
【机器学习】决策树
本文介绍了 ID3,C4.5,CART三种基本的决策树模型。首先介绍了决策树的特征选择,包括信息增益,信息增益率、基尼指数、最小均方差分别对应分类树ID3、C4.5、CART、回归树CART。然后介绍了决策树建树的一般流程、对比分类树和回归树建树的区别。最后介绍了树模型中避免过拟合问题的剪枝方法,包括前剪枝和后剪枝。
yuquanle
2020/04/01
7050
【机器学习】决策树
决策树算法原理及应用(详细版)
C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。
智能算法
2020/09/24
2.6K0
决策树算法原理及应用(详细版)
决策树算法之----C4.5
1. C4.5算法简介 C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,找到一个从属性值到类别的映射关系,并且这个映射能用于对新的类别未知的实体进行分类。 C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构,其中每个内部节点(非树叶节点)表示在一个属性上的测试,每个分枝代
智能算法
2018/04/03
1.6K0
决策树算法之----C4.5
详解决策树 C4.5 算法
‍‍‍‍ 转自:Treant http://www.cnblogs.com/en-heng/p/5013995.html 决策树模型与学习 决策树(decision tree)算法基于特征属性进行分类,其主要的优点:模型具有可读性,计算量小,分类速度快。 决策树算法包括了由Quinlan提出的ID3与C4.5,Breiman等提出的CART。其中,C4.5是基于ID3的,对分裂属性的目标函数做出了改进。 决策树模型 决策树是一种通过对特征属性的分类对样本进行分类的树形结构,包括有向边与三类节点: 1、根节点
企鹅号小编
2018/02/07
2.3K0
详解决策树 C4.5 算法
机器学习之决策树理论
在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。数据分类是一个两阶段过程,包括模型学习阶段(构建分类模型)和分类预测阶段(使用模型预测给定数据的类标号)。决策树分类算法属于监督学习(Supervised learning),即样本数据中有类别标号。下面是两个阶段的简单描述:
用户1359560
2019/01/03
5450
机器学习 | 决策树模型(一)理论
决策树(Decision tree)是一种基本的分类与回归方法,是一种非参数的有监督学习方法。
数据STUDIO
2021/06/24
1.6K0
Come On!决策树算法!
机器学习在各个领域都有广泛的应用,特别在数据分析领域有着深远的影响。决策树是机器学习中最基础且应用最广泛的算法模型。本文介绍了机器学习的相关概念、常见的算法分类和决策树模型及应用。通过一个决策树案例,着重从特征选择、剪枝等方面描述决策树的构建,讨论并研究决策树模型评估准则。最后基于 R 语言和 SPSS 这两个工具,分别设计与实现了决策树模型的应用实例。 机器学习概念 机器学习 (Machine Learning) 是近 20 多年兴起的一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度
陆勤_数据人网
2018/02/26
9690
Come On!决策树算法!
C4.5决策树及CART决策树
信息增益比本质: 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。惩罚参数:数据集D以特征A作为随机变量的熵的倒数。
用户10950404
2024/07/30
1600
C4.5决策树及CART决策树
Python+sklearn决策树算法使用入门
简单地说,决策树算法相等于一个多级嵌套的选择结构,通过回答一系列问题来不停地选择树上的路径,最终到达一个表示某个结论或类别的叶子节点,例如有无贷款意向、能够承担的理财风险等级、根据高考时各科成绩填报最合适的学校和专业、一个人的诚信度、商场是否应该引进某种商品、预测明天是晴天还是阴天。
Python小屋屋主
2019/05/29
3.2K0
AI - 决策树模型
决策树的思想来源可以追溯到古希腊时期,当时的哲学家们就已经开始使用类似于决策树的图形来表示逻辑推理过程。然而,决策树作为一种科学的决策分析工具,其发展主要发生在20世纪。
@小森
2024/03/24
1920
AI - 决策树模型
分类和回归-决策树算法(ID3、C4.5和CART)
决策树(Decision Tree)是⼀种树形结构,每个节点表示⼀个属性上的判断,每个分⽀代表⼀个判断结果的输出,最后每个叶节点代表⼀种分类结果,本质是⼀颗由多个判断节点组成的树。
唔仄lo咚锵
2022/10/31
1K0
分类和回归-决策树算法(ID3、C4.5和CART)
决策树学习笔记(二):剪枝,ID3,C4.5
推荐导读:本篇为树模型系列第二篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据挖掘竞赛的朋友提供帮助。
1480
2019/07/15
1.5K0
决策树学习笔记(二):剪枝,ID3,C4.5
推荐阅读
相关推荐
机器学习之决策树(Decision Tree)及其Python代码实现
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档