5、数据结构字典和集合
集合(可变数据结构)
集合初始化
集合常用方法
set和线性结构
可hash类型
字典(可变数据结构)
字典的用途
创建和使用
字典初始化
字典基本操作
字典的特性
字符串格式化
字典方法
缺省字典
缺省字典实际案例
有序字典
应用场景
Counter数据类型
集合初始化
集合常用方法
set和线性结构
可hash类型
字典(可变数据结构)
字典的用途
创建和使用
字典初始化
字典基本操作
字典的特性
字符串格式化
字典方法
缺省字典
缺省字典实际案例
有序字典
应用场景
Counter数据类型
集合(可变数据结构)
集合(set),set为非线性结构,集合是可变的、无序的并且它是不能重复的元素集合,它是无序的,因为集合对象是一个不同hashable对象组成的无序集合,在内存中是随意排放的,也就意味着它是不能使用索引,也无法切片,但是它也是可变的,我们可以任意修改,并且还有一个非常强大的能力,就是去重,元素的内容是不允许重复的;
需要注意的是,集合内部不可以有list、bytearray、set、dict,因为他们都是不可以hash类型,因为他们是可变的,一旦变动hash值也会变;
集合是可迭代对象,可以进行遍历,同时也支持成员运算符in和not in,用来判断元素时候在集合中;
集合初始化
集合的定义和其他数据类型不一样,其他数据类型可以使用括号,大括号等定义,但是集合不行,集合默认使用的是{}大括号,但是已经被字典使用了,所以在定义一个空集合的时候,只能使用set()来初始化一个空集合,同时set也支持传入一个可迭代对象;
# 空集合的定义,只能使用如下方法,因为{}已经被字典使用了
s1=set()
# 集合定义
s2={1,2,3,4}
# 或者
s3={range(1,10)}
集合常用方法
如下,就是集合都全部可使用方法;
add():为集合添加元素;
clear():移除集合中的所有元素;
copy():拷贝一个集合;
difference(): 返回多个集合的差集;
difference_update():移除集合中的元素,该元素在指定的集合也存在;
discard():删除集合中指定的元素;
intersection():返回集合的交集;
intersection_update():返回集合的交集;
isdisjoint(): 判断两个集合是否包含相同的元素,如果没有返回 True,否则返回 False;
issubset(): 判断指定集合是否为该方法参数集合的子集;
issuperset(): 判断该方法的参数集合是否为指定集合的子集;
pop():随机移除元素;
remove(): 移除指定元素;
symmetric_difference(): 返回两个集合中不重复的元素集合;
symmetric_difference_update():移除当前集合中在另外一个指定集合相同的元素,并将另外一个指定集合中不同的元素插入到当前集合中;
union(): 返回两个集合的并集;
update(): 给集合添加元素;
set和线性结构
线性结构的时间复杂度它的查询时间是O(n),即随着数据规模的增大而增加耗时,set、dict等结构,内部使用hash作为key,时间复杂度可以做到O(1),它的查询时间和数据规模无关;
下面就来一个案例,分别对set和list两种不同数据结构的性能进行分析;
可hash类型
在Python中,常见的可hash数据类型有,int、float、complex、bool、string、bytes、tuple、None,他们都是不可变类型,都是可hash类型,hashable;
hash称之为散列值,需要注意的,这个值哪怕有一点微小的变化,hash出来的值就会出现巨大的变化,这个hash值可以理解为一个大整数,这个大整数会转成16进制,这个16进制数实际上就是hash空间的门牌号码,假设这个hash值是3,它将会把这个值放在第三个位置;
字典(可变数据结构)
字典是key/value组成的一对对对数据的集合,它也是可变的、无序的并且key是不重复的,因为对于字典的key都会进行hash存储的,依靠hash值来找到它,所以不可变,一旦变化hash值就会变化;
字典,它就是将一系列值组合成数据结构,并通过编号来访问各值时,列表很有用。那么本章主要是介绍一种可通过名称来访问其各个值的数据结构,这种数据结构称之为映射(mapping),字典是Python中唯一的内置映射数据类型,它的值不按顺序排列,而是存储在键下,键可能是数字、字符或者元组;
字典的用途
字典的名称指出了这种数据结构的用途,普通图书适合从头到尾的顺序阅读,如果你愿意,可以快速翻到任何一页,这有点像Python的列表;
字典,旨在让你能够轻松的找到特定的单词(键),从而获取其定义(值),在很多情况下,使用字典都比使用列表更合适,其主要用途如下;
1、表示棋盘的状态,其中每个键都是由坐标组成的元组;
2、存储文件修改时间,其中的键为文件名;
3、数字电话/地址簿;
假设,我们要使用Python来创建一个通讯录应该怎么做呢,下面分别用列表和字典的方式进行比较;
# 列表
# 创建一个名称列表
people_name = ["cce","cfj"]
# 创建一个号码列表
people_phone = ["189...456","186...313"]
# 拿到cce的电话号码
people_phone[people_name.index("cce")] # 貌似并不实用,给出的结果还错了,因为字典的无序原理,导致获取的结果错误
'186...313'
# 字典
people={"cce":"189...456","cfj":"186...313"}
# 拿到cce的电话
people["cce"]
'189...456'
由此上例子可以看出,在这种特殊的场景下,使用字典或许比使用列表要好得多得多;
创建和使用
字典由键及其相应的值组成,这种键值对称称之为项(item),在前面的示例中,键为名字,而值则为电话号码,每个键与其值之间都用冒号(:)隔开,而项之间则用逗号隔开,而一个项或者多个项都放在花括号内{},这便是字典;
空字典用两个花括号表示,需要注意的是,在字典中,键必须是独一无二的,值却没有什么要求;
字典初始化
使用dict函数可以其他映射(如其他字典),或者键值对序列创建字典;
>>> dict([("cce","189...456"),("cfj","186...313")])
{'cce': '189...456', 'cfj': '186...313'}
# 还可以使用关键字实参,来调用dict函数创建字典
>>> dict(cce="189...456",cfj="186...313") # 注意,键不可带引号
{'cce': '189...456', 'cfj': '186...313'}
字典基本操作
字典的基本操作在很多方面都类似序列;
len(d):返回字典d包含都项(键值对)数量;
d[k]:返回键为k相关的值;
d[k]=v:将v赋值给键为k的项;
del d[k]:删除键为k的项;
k in d:检查字典d是否有包含k的项;
字典的特性
键的类型:字典中的键可以是整数,但并非必须是整数。字典中的键可以是任何不可变 的类型,如浮点数(实数)、字符串或元组;
自动添加:即便是字典中原本没有的键,也可以给它赋值,这将在字典中创建一个新项;
成员资格:表达式k in d(其中d是一个字典)查找的是键而不是值,而表达式v in l(其 中l是一个列表)查找的是值而不是索引;
- 注意:
相比于检查列表是否包含指定的值,检查字典是否包含指定键效率更高,数据结构越大,效率差距就越大
字符串格式化
在前面学过字符串格式化format,在此我们也可以使用字符串格式化设置功能来设置值的格式,这些值作为命令或非命名参数提供给方法format,在有些情况下,通过在字典存储一系列命名的值,可让格式更易读;
例如,可在字典中包含各种信息,这样只需在格式字符串中提取所需的信息即可。为此, 必须使用format_map来指出你将通过一个映射来提供所需的信息;
>>> user={"cce":18}
>>> print("my name is cce , and my age is {cce}".format_map(user))
my name is cce , and my age is 18
字典方法
与其他内置类型一样,字典也有方法。字典的方法很有用,但其使用频率可能没有列表和字符串的方法那样高;
dict.clear()删除字典内所有元素;
dict.copy():返回一个字典的浅拷贝;
dict.fromkeys(seq[, val])创建一个新字典,以序列 seq 中元素做字典的键,val 为字典所有键对应的初始值;
dict.get(key, default=None):返回指定键的值,如果值不在字典中返回default值;
dict.has_key(key):如果键在字典dict里返回true,否则返回false;
dict.items():以列表返回可遍历的(键, 值)元组数组;
dict.keys():以列表返回一个字典所有的键;
dict.setdefault(key, default=None):和get()类似, 但如果键不存在于字典中,将会添加键并将值设为default;
dict.update(dict2):把字典dict2的键/值对更新到dict里;
dict.values():以列表返回字典中的所有值;
pop(key[,default]):删除字典给定键 key 所对应的值,返回值为被删除的值。key值必须给出。 否则,返回default值;
popitem():返回并删除字典中的最后一对键和值;
缺省字典
在collections包下面有一个defaultdict的缺省字典,第一个参数是一个初始化函数,当试图访问这个字典的时候,如果访问的key不存在,那么defaultdict就会调用这个工厂函数,创建一个key为访问的key,值为初始化函数的一个字典元素;
说白了,没有访问的k/v对,defaultdict就使用工程方法,创建一个k/v对,简化了操作;
from collections import defaultdict
d1=defaultdict(tuple)
print(d1["a"])
d2=defaultdict(list)
print(d2["b"])
# ()
# []
缺省字典实际案例
在很多常见下,我们要对一个字典进行赋值,但是又担心对指定key赋值对时候,该key又不存在这个字典中,所以这个时候我们对缺省字典就很有用了,如果访问到该key在这个字典中不存在,那么就自动创建一个名为key的k,该k的值默认为None,可以传入一个可调用对象;
from collections import defaultdict
from random import randint
# 原始方式
d1= {}
for k in 'abcd':
for v in range(randint(1,5)):
if k not in d1:
d1[k]=list()
d1[k].append(v)
print(d1)
# 使用工厂方法
d1=defaultdict(list) # 当访问的key不存在时,则会创建key,这个key的值为defaultdict传入的list,也就是一个[];
for k in 'abcd':
for v in range(randint(1,5)):
d1[k].append(v)
print(d1)
有序字典
在Python3.6中字典有个新特性,字典会将元素插入顺序记录下来,然后按照这个顺序排序,但是Python3.6之下是没有的,所以可能会用到OrderedDict,创建一个有序字典;
# Python3.5默认情况下,无序
d1={}
d1["a"]=1
d1["b"]=2
d1["c"]=3
d1["d"]=4
print(d1) # {'d': 4, 'a': 1, 'c': 3, 'b': 2} # 可以看到,在Python3.5中,默认是无序的
# 使用有序字典
from collections import OrderedDict
d2=OrderedDict()
d2["a"]=1
d2["b"]=2
d2["c"]=3
d2["d"]=4
print(d2) # OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)]) 可以看到,已经根据插入顺序排序了
应用场景
假设,我们使用字典记录了N该产品,产品是有ID的,ID是有规律的,比如由小到大,如果我们正好按照编号的顺序插入这些key/value对,插入到字典当中,那我们在遍历的时候,有的时候,想希望按照ID的顺序取的方式去取这些K/V对,那我们就可以直接拿来使用了,否则,我们还需要重新排序,因为在数据量较大时,排序是非常浪费时间的;
Counter数据类型
在collections包下面还有一个Counter的数据类型,它继承自dict,也就是我们常用于统计的一种数据类型,用于追踪值的出现次数,可以帮助我们针对某项数据进行计数,比如它可以来计算每个人使用多少颜色;
elements() : 返回一个迭代器,其中元素的重复次数和它的count一样多,返回的次序是无序的,如果count值小于1,将忽略;
most_common(n) : 返回结果中的count次数最大的前几名,如果省略n,则返回所有的统计结果;
subtract([iterable-or-mapping]) : 用于两个Counter数据类型做映射,从一个可迭代对象或从另一个映射(或计数器)中减去元素。类似dict.update(),但减去计数,而不是替换它们。输入和输出都可以为零或负;
update([iterable-or-mapping]) : 元素从一个可迭代对象计数或从另一个映射(或计数器)增加。类似dict.update(),但增加计数,而不是替换它们。此外,可迭代对象应为一系列元素,而不是(key, value)对;
from collections import Counter
count = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
print(count) # Counter({'blue': 3, 'red': 2, 'green': 1})
print(count.get("blue")) # 3 它继承自dict,所以,我们可以直接使用dict的所有方法