导读
python之禅中有这样一句:simple is better than complex。翻译成中文我想就是“大道至简、大巧不工”。
具体到python中数据结构的选择运用,虽然有很多类型可供选择:除了基本的列表、字典、集合和元组4个基本类型外,collections模块中提供了很多定制化的数据结构,还有专用的堆heapq和枚举enum等。诚然,特定数据结构在某些应用场景下可能有神奇的效果,但把基础数据类型用到极致也可堪称是绝招。
本篇文章主要面向python初学者,介绍列表、字典、集合和元组4个基本数据结构的常用接口和用法,最后通过一道LeetCode原题讲解了数据结构的综合运用。
01 列表
列表可能是在使用python中最为常用的数据结构了,它类似于其他语言中的数组,但又可以存储多种数据类型,同时还可以自适应更改列表长度。可以说,在python中几乎没有一个列表解决不了的数据结构,如果有,那就……
列表简单易用且不失功能强大,除了丰富的魔法方法外,列表支持直接调用的接口并不多(通过dir(list)命令可以查看列表的所有接口),主要包括11个接口方法:
列表类型内置11个方法接口
列表的这些方法中,除了clear用的较少外,其他都是常用接口,需要注意的是虽然pop、remove、index和insert操作语法比较类似,但存在一个最大的不同是:insert接受的索引参数可以是任意索引,无论是否超出列表合法索引;而pop接受的索引必须是合法索引、index和remove接受的元素必须是存在的元素,否则会报错。例如:
1lyst = [1, 2, 3, 5]
2#索引9超出合法范围,自动在尾端插入
3lyst.insert(9, 10) #[1, 2, 3, 5, 10]
4#索引9超出合法范围,pop操作报错
5lyst.pop(9) #IndexError: pop index out of range
6#元素100不在列表中,index报错
7lyst.index(100) #ValueError: 100 is not in list
8#元素100不在列表中,remove报错
9lyst.remove(100) #ValueError: list.remove(x): x not in list
当然,列表的强大之处不仅在于这11个接口,更加pythonic的操作是列表切片和列表推导式,这两者用得好,基本可以替代很多接口方法,更能免去很多for循环操作,性能也更加高效。
02 字典
列表之外,字典可能是python中用的也比较多的数据结构了,由于字典的底层应用哈希映射,所以要求字典的所有key必须是不可变元素(可哈希对象),增删改查操作一般都能实现O(1)复杂度,是低复杂度的必备数据结构。
字典类型内置11个方法接口
这里对pop和popitem、setdefault和get以及update操作进行举例:
1# popitem删除最后一个元素
2dic = {'a':1, 'b':2, 'c':3}
3dic.popitem()
4dic #{'a': 1, 'b': 2}
5# pop删除指定元素
6dic = {'a':1, 'b':2, 'c':3}
7dic.pop('a')
8dic #{'b': 2, 'c': 3}
9# setdefault操作
10dic = {'a':1, 'b':2, 'c':3}
11val = dic.setdefault('e', 100)
12dic #{'a': 1, 'b': 2, 'c': 3, 'e': 100}
13val #100
14# get操作
15dic = {'a':1, 'b':2, 'c':3}
16val = dic.get('e', 100)
17dic #{'a': 1, 'b': 2, 'c': 3}
18val #100
19# update操作
20dic = {'a':1, 'b':2, 'c':3}
21dic2 = {'a':4, 'd':10}
22dic.update(dic2)
23dic #{'a': 4, 'b': 2, 'c': 3, 'd': 10}
03 集合
集合操作可能最常见于用于对列表去重,它的最大特性是各元素仅保留1次,底层也是应用了哈希函数,所以在集合中查找元素一般也可实现O(1)复杂度,同时集合的嵌套元素也要求是不可变类型(可哈希对象)。
集合类型内置17个方法接口
举个例子:
1# pop删除最早的元素
2s = {1, 2, 3}
3# s.pop() #删除1,删除后s = {2, 3}
4# 在原集合中将1改为4,即此时s = {4, 2, 3)
5s = {4, 2, 3}
6s.pop() #删除2,删除后s = {4, 3}
7# remove与discard操作
8s = {1, 2, 3}
9s.remove(4) #KeyError: 4
10s.discard(4) #无操作
除了与列表和字典中类似的增删改操作外,集合还支持数学概念下的集合操作,如交集、并集、差集等。
1#inplace求交集
2s1 = {1, 2, 3}
3s2 = {2, 4, 5}
4s1.intersection_update(s2)
5s1 #{2}
6#返回交集结果
7s1 = {1, 2, 3}
8s2 = {2, 4, 5}
9s3 = set.intersection(s1, s2)
10s3 #{2}
11# 判断是否存在交集,若存在则返回False,否则返回True
12s1 = {1, 2, 3}
13s2 = {2, 3}
14set.isdisjoint(s1, s2) #True
15# 判断子集和超集
16s1 = {1, 2, 3}
17s2 = {2, 3}
18s1.issubset(s2) #False
19s1.issuperset(s2) #True
另外,集合的底层哈希实现决定了它有一个神奇特性,即可实现序列的排序:
1import random
2s = list(range(10))
3random.shuffle(s)
4print(s) #[3, 4, 9, 5, 8, 6, 7, 2, 0, 1]
5print(list(set(s))) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
当然,要求排序的元素不存在重复元素,否则……
04 元组
如果说列表、字典和集合都有其各自擅长应用场景的话,那么元组可能是最没有存在感的数据结构:它接口有限、功能单一,而且是不可变类型。一般而言,用元组解决的问题都可以用列表实现。但使用用元组时,更多在于暗示该序列为不可变类型。当然,当元组内嵌套子列表时实际上是可以对嵌套的子列表进行更改操作的。
正因为元组的不可变特性,其操作接口十分有限,仅包括查找和计数两个接口:
元组类型内置2个方法接口
举个例子:
1t = (1, 2)
2t.index(3) #ValueError: tuple.index(x): x not in tuple
3t.count(3) # 0
需要注意元组初始化时的一个常见错误:当元组元素个数为1个时,要在元素后面加一个",",否则会被转为相应的元素;而当元组元素个数为多个时,小括号可以省略:
1# 单元素元组的初始化要加","
2t = ('s')
3type(t) # str
4t = ('s',)
5type(t) #tuple
6# 多元素元组初始化时可省略小括号
7t = '2', 1, True
8type(t) #tuple
另外,考虑元组的不可变特性,所以元组也常用于以多个元素作为key的字典存储,而这是列表和集合等可变类型所不具备的:
1dic = dict()
2dic[[1, 2]] = 1 #TypeError: unhashable type: 'list'
3dic[{1, 2}] = 1 #TypeError: unhashable type: 'set'
4dic[(1, 2)] = 1 #可正常存储为字典
05 综合案例
这里列举一个LeetCode每日一题的例子:
LeetCode 355. 设计推特 设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近十条推文。 你的设计需要支持以下的几个功能: postTweet(userId, tweetId): 创建一条新的推文 getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。 follow(followerId, followeeId): 关注一个用户 unfollow(followerId, followeeId): 取消关注一个用户
题目要求实现推特的几个常用功能,包括创建(增)、检索(查)、关注(改或增)、取消关注(删),可以说综合运用了数据结构的各种常用操作。为了实现较好的时间复杂度,结合python中4个常用数据结构的各自特性:
1class Twitter:
2 def __init__(self):
3 """
4 Initialize your data structure here.
5 """
6 self.user = {}#当前系统用户列表,每个用户对应2个子字典,F和T
7 self.Tid = 0 #记录推文绝对id
8
9 def _new_user(self, userId):
10 """
11 create a new user, follow self
12 """
13 F = {userId}#关注者集合,并初始时关注自己
14 T = []#推文列表
15 self.user[userId] = {'F':F, 'T':T}
16
17 def postTweet(self, userId: int, tweetId: int) -> None:
18 """
19 Compose a new tweet.
20 """
21 if userId not in self.user:
22 self._new_user(userId)
23 self.user[userId]['T'].append((self.Tid, tweetId))#更新推文列表,记录为元组:(推文绝对id, 推文id)
24 self.Tid += 1
25
26 def getNewsFeed(self, userId: int) -> List[int]:
27 """
28 Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
29 """
30 if userId not in self.user:#用户不存在
31 return []
32 Tlist = []
33 for uid in self.user[userId]['F']:
34 Tlist.extend(self.user[uid]['T'])#关注的推文
35 Tlist.sort(reverse=True)
36 T10 = Tlist[:10]#列表逆序排序后取前10
37 return [T[1] for T in T10]
38
39 def follow(self, followerId: int, followeeId: int) -> None:
40 """
41 Follower follows a followee. If the operation is invalid, it should be a no-op.
42 """
43 if followerId not in self.user:
44 self._new_user(followerId)
45 if followeeId not in self.user:
46 self._new_user(followeeId)
47 self.user[followerId]['F'].add(followeeId)#利用集合的自动去重特性,省去重复关注的判断
48
49 def unfollow(self, followerId: int, followeeId: int) -> None:
50 """
51 Follower unfollows a followee. If the operation is invalid, it should be a no-op.
52 """
53 if followerId in self.user and followeeId in self.user and followeeId != followerId:
54 self.user[followerId]['F'].discard(followeeId)#集合的删除,省去判断元素是否存在
以上,就是综合运用了python中4个基本数据结构各自特性的一个案例,基本上是考虑了各数据类型的优点。