|
python之禪中有這樣一句：simple is better than complex。翻譯成中文我想就是“大道至簡(jiǎn)、大巧不工”。 具體到python中數(shù)據(jù)結(jié)構(gòu)的選擇運(yùn)用，雖然有很多類型可供選擇：除了基本的列表、字典、集合和元組4個(gè)基本類型外，collections模塊中提供了很多定制化的數(shù)據(jù)結(jié)構(gòu)，還有專用的堆heapq和枚舉enum等。誠(chéng)然，特定數(shù)據(jù)結(jié)構(gòu)在某些應(yīng)用場(chǎng)景下可能有神奇的效果，但把基礎(chǔ)數(shù)據(jù)類型用到極致也可堪稱是絕招。 
文章來(lái)源：小數(shù)志
作者：luanhz 本篇文章主要面向python初學(xué)者，介紹列表、字典、集合和元組4個(gè)基本數(shù)據(jù)結(jié)構(gòu)的常用接口和用法，最后通過(guò)一道LeetCode原題講解了數(shù)據(jù)結(jié)構(gòu)的綜合運(yùn)用。 列表可能是在使用python中最為常用的數(shù)據(jù)結(jié)構(gòu)了，它類似于其他語(yǔ)言中的數(shù)組，但又可以存儲(chǔ)多種數(shù)據(jù)類型，同時(shí)還可以自適應(yīng)更改列表長(zhǎng)度。可以說(shuō)，在python中幾乎沒(méi)有一個(gè)列表解決不了的數(shù)據(jù)結(jié)構(gòu)，如果有，那就…… 列表簡(jiǎn)單易用且不失功能強(qiáng)大，除了豐富的魔法方法外，列表支持直接調(diào)用的接口并不多（通過(guò)dir(list)命令可以查看列表的所有接口），主要包括11個(gè)接口方法： 
列表類型內(nèi)置11個(gè)方法接口 append：在列表尾端增加一個(gè)元素 insert：在列表指定位置插入一個(gè)元素，值得說(shuō)明的是insert的目標(biāo)索引位置可以為任意參數(shù)，當(dāng)超過(guò)列表長(zhǎng)度時(shí)會(huì)自動(dòng)截?cái)嗖迦?/p> extend：與另一個(gè)列表進(jìn)行拼接擴(kuò)展 pop：刪除一個(gè)元素，接受一個(gè)索引參數(shù)，且要求索引為有效索引，不允許超出列表索引范圍；缺省為-1，此時(shí)刪除尾端元素 remove：刪除一個(gè)元素，接受一個(gè)列表元素參數(shù)，要求該元素在列表中存在，不可缺省 clear：清空整個(gè)列表，相當(dāng)于為列表賦值為空列表 index：查找目標(biāo)元素在列表中的索引，要求該元素在列表中存在，否則報(bào)錯(cuò) count：計(jì)算目標(biāo)元素在給定列表中的個(gè)數(shù)，當(dāng)目標(biāo)元素不存在時(shí)返回0 sort：對(duì)列表進(jìn)行inplace排序，可接受一個(gè)key參數(shù)指定排序規(guī)則，接受reverse參數(shù)明確是正序還是逆序 reverse：對(duì)列表進(jìn)行inplace翻轉(zhuǎn) copy：對(duì)列表進(jìn)行淺拷貝
列表的這些方法中，除了clear用的較少外，其他都是常用接口，需要注意的是雖然pop、remove、index和insert操作語(yǔ)法比較類似，但存在一個(gè)最大的不同是：insert接受的索引參數(shù)可以是任意索引，無(wú)論是否超出列表合法索引；而pop接受的索引必須是合法索引、index和remove接受的元素必須是存在的元素，否則會(huì)報(bào)錯(cuò)。例如：1lyst = [1, 2, 3, 5]
2#索引9超出合法范圍，自動(dòng)在尾端插入
3lyst.insert(9, 10) #[1, 2, 3, 5, 10]
4#索引9超出合法范圍，pop操作報(bào)錯(cuò)
5lyst.pop(9) #IndexError: pop index out of range
6#元素100不在列表中，index報(bào)錯(cuò)
7lyst.index(100) #ValueError: 100 is not in list
8#元素100不在列表中，remove報(bào)錯(cuò)
9lyst.remove(100) #ValueError: list.remove(x): x not in list
當(dāng)然，列表的強(qiáng)大之處不僅在于這11個(gè)接口，更加pythonic的操作是列表切片和列表推導(dǎo)式，這兩者用得好，基本可以替代很多接口方法，更能免去很多for循環(huán)操作，性能也更加高效。
列表之外，字典可能是python中用的也比較多的數(shù)據(jù)結(jié)構(gòu)了，由于字典的底層應(yīng)用哈希映射，所以要求字典的所有key必須是不可變?cè)兀晒?duì)象），增刪改查操作一般都能實(shí)現(xiàn)O(1)復(fù)雜度，是低復(fù)雜度的必備數(shù)據(jù)結(jié)構(gòu)。 
字典類型內(nèi)置11個(gè)方法接口 fromkeys：從一個(gè)序列化對(duì)象（如列表等）創(chuàng)建一個(gè)字典，同時(shí)可接受一個(gè)缺省參數(shù)作為value，缺省時(shí)value為None setdefault：與查找的get方法類似，當(dāng)查找的key存在時(shí)返回其value值；否則在字典中增加該鍵值對(duì)，若value缺省，則value為None pop：接受一個(gè)key，刪除該元素并返回其value值，實(shí)際上相當(dāng)于列表的remove popitem：不接受任何參數(shù)，刪除字典最后一個(gè)元素并返回其value值（python3.6以后，字典元素按照插入先后默認(rèn)有序），當(dāng)字典為空時(shí)引發(fā)錯(cuò)誤，實(shí)際上相當(dāng)于列表的pop()缺省參數(shù)操作 clear：與列表clear類似，清空字典 update：相當(dāng)于列表的extend操作，但遇到相同的key時(shí)會(huì)保留后面字典中相應(yīng)的value值 keys：返回字典的所有鍵 values：返回字典的所有值 items：返回字典的所有鍵值對(duì)，每個(gè)鍵值對(duì)為元組形式 get：接受一個(gè)key和一個(gè)默認(rèn)value，當(dāng)字典中存在該元素時(shí)返回其value，否則返回默認(rèn)值 copy：字典的淺拷貝
這里對(duì)pop和popitem、setdefault和get以及update操作進(jìn)行舉例：
1# popitem刪除最后一個(gè)元素
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}
集合操作可能最常見(jiàn)于用于對(duì)列表去重，它的最大特性是各元素僅保留1次，底層也是應(yīng)用了哈希函數(shù)，所以在集合中查找元素一般也可實(shí)現(xiàn)O(1)復(fù)雜度，同時(shí)集合的嵌套元素也要求是不可變類型（可哈希對(duì)象）。 
集合類型內(nèi)置17個(gè)方法接口 add：在集合中增加一個(gè)元素，如果元素已存在，則無(wú)實(shí)際操作 pop：不接受任何參數(shù)，堪稱是最神秘的操作，不同于列表的從尾端刪除、字典的指定鍵刪除，集合的pop操作看似是'隨機(jī)'刪除。但實(shí)際上是按照加入集合的先后順序，刪除'最早'加入的元素 remove：類似于列表的remove操作，移除指定元素，當(dāng)元素不存在時(shí)引發(fā)錯(cuò)誤 discard：remove的替代版，當(dāng)元素存在時(shí)移除，元素不存在時(shí)誤操作且不報(bào)錯(cuò) clear：清空集合 update：接受一個(gè)可迭代對(duì)象（可以不是集合類型），類似字典的update操作，逐一插入 copy：集合的淺拷貝
1# pop刪除最早的元素
2s = {1, 2, 3}
3# s.pop() #刪除1，刪除后s = {2, 3}
4# 在原集合中將1改為4，即此時(shí)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) #無(wú)操作
除了與列表和字典中類似的增刪改操作外，集合還支持?jǐn)?shù)學(xué)概念下的集合操作，如交集、并集、差集等。 intersection：接受兩個(gè)集合作為參數(shù)，求兩個(gè)集合的交集，生成新集合作為返回結(jié)果 intersection_update：對(duì)intersection的變形，在調(diào)用方法的集合上進(jìn)行inplace操作，無(wú)返回值 isdisjoint：判斷兩個(gè)集合中是否存在公共元素，不存在公共元素時(shí)結(jié)果為True，否則為False
union：接受兩個(gè)集合作為參數(shù)，返回并集的新集合作為返回值。ps：并集操作的inplace操作接口即為update difference：接受兩個(gè)集合作為參數(shù)，求前者與后者的差集，生成新集合作為返回結(jié)果 difference_update：與交集類似，對(duì)調(diào)用方法的集合進(jìn)行inplace操作 symmetric_difference：對(duì)稱差集，類似于補(bǔ)集，返回兩個(gè)集合除公共元素意外的并集，即A有B無(wú)或A無(wú)B有的元素 symmetric_difference_update：對(duì)調(diào)用方法的集合進(jìn)行inplace操作
issubset：判斷是否是子集，返回bool結(jié)果 - issuperset：判斷是否是超集，返回bool結(jié)果
1#inplace求交集
2s1 = {1, 2, 3}
3s2 = {2, 4, 5}
4s1.intersection_update(s2)
5s1 #{2}
6#返回交集結(jié)果
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
另外，集合的底層哈希實(shí)現(xiàn)決定了它有一個(gè)神奇特性，即可實(shí)現(xiàn)序列的排序：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]
當(dāng)然，要求排序的元素不存在重復(fù)元素，否則…… 如果說(shuō)列表、字典和集合都有其各自擅長(zhǎng)應(yīng)用場(chǎng)景的話，那么元組可能是最沒(méi)有存在感的數(shù)據(jù)結(jié)構(gòu)：它接口有限、功能單一，而且是不可變類型。一般而言，用元組解決的問(wèn)題都可以用列表實(shí)現(xiàn)。但使用用元組時(shí)，更多在于暗示該序列為不可變類型。當(dāng)然，當(dāng)元組內(nèi)嵌套子列表時(shí)實(shí)際上是可以對(duì)嵌套的子列表進(jìn)行更改操作的。 正因?yàn)樵M的不可變特性，其操作接口十分有限，僅包括查找和計(jì)數(shù)兩個(gè)接口：
元組類型內(nèi)置2個(gè)方法接口
1t = (1, 2)
2t.index(3) #ValueError: tuple.index(x): x not in tuple
3t.count(3) # 0
需要注意元組初始化時(shí)的一個(gè)常見(jiàn)錯(cuò)誤：當(dāng)元組元素個(gè)數(shù)為1個(gè)時(shí)，要在元素后面加一個(gè)','，否則會(huì)被轉(zhuǎn)為相應(yīng)的元素；而當(dāng)元組元素個(gè)數(shù)為多個(gè)時(shí)，小括號(hào)可以省略：
1# 單元素元組的初始化要加','
2t = ('s')
3type(t) # str
4t = ('s',)
5type(t) #tuple
6# 多元素元組初始化時(shí)可省略小括號(hào)
7t = '2', 1, True
8type(t) #tuple
另外，考慮元組的不可變特性，所以元組也常用于以多個(gè)元素作為key的字典存儲(chǔ)，而這是列表和集合等可變類型所不具備的：1dic = dict()
2dic[[1, 2]] = 1 #TypeError: unhashable type: 'list'
3dic[{1, 2}] = 1 #TypeError: unhashable type: 'set'
4dic[(1, 2)] = 1 #可正常存儲(chǔ)為字典
這里列舉一個(gè)LeetCode每日一題的例子： LeetCode 355. 設(shè)計(jì)推特 設(shè)計(jì)一個(gè)簡(jiǎn)化版的推特(Twitter)，可以讓用戶實(shí)現(xiàn)發(fā)送推文，關(guān)注/取消關(guān)注其他用戶，能夠看見(jiàn)關(guān)注人（包括自己）的最近十條推文。 你的設(shè)計(jì)需要支持以下的幾個(gè)功能： postTweet(userId, tweetId): 創(chuàng)建一條新的推文 getNewsFeed(userId): 檢索最近的十條推文。每個(gè)推文都必須是由此用戶關(guān)注的人或者是用戶自己發(fā)出的。推文必須按照時(shí)間順序由最近的開(kāi)始排序。 follow(followerId, followeeId): 關(guān)注一個(gè)用戶 unfollow(followerId, followeeId): 取消關(guān)注一個(gè)用戶
題目要求實(shí)現(xiàn)推特的幾個(gè)常用功能，包括創(chuàng)建（增）、檢索（查）、關(guān)注（改或增）、取消關(guān)注（刪），可以說(shuō)綜合運(yùn)用了數(shù)據(jù)結(jié)構(gòu)的各種常用操作。為了實(shí)現(xiàn)較好的時(shí)間復(fù)雜度，結(jié)合python中4個(gè)常用數(shù)據(jù)結(jié)構(gòu)的各自特性： 保存用戶列表：這是一個(gè)隱藏的功能，創(chuàng)建推文或者關(guān)注操作的用戶不存在時(shí)，首先要進(jìn)行用戶創(chuàng)建。為實(shí)現(xiàn)O(1)復(fù)雜度，當(dāng)然是選用字典保存所有用戶id 創(chuàng)建推文：為了存儲(chǔ)推文，列表、字典、集合都可以，因?yàn)椴淮嬖谔厥庖?，所以選用列表即可 檢索最近10條推文：這是本題的難點(diǎn)，因?yàn)槭且獧z索自己已關(guān)注用戶的所有推文中的最近10條，所以存在合并后的TOP10問(wèn)題。當(dāng)然，實(shí)現(xiàn)的方式有很多，堆heapq可能是比較理想的，但實(shí)際上一個(gè)列表也足以滿足需要 關(guān)注和取消關(guān)注：實(shí)際上就是維護(hù)每個(gè)用戶的關(guān)注序列，考慮到后續(xù)還有取關(guān)的操作，加之題目設(shè)定了一些無(wú)效操作（例如重復(fù)關(guān)注和自己關(guān)注自己），所以列表的復(fù)雜度難以滿足要求，字典和集合都可以，這里選用集合，因?yàn)榧系膁iscard接口可很好的處理元素不存在時(shí)的刪除操作。 另外：由于題目中要求查找最新的推文時(shí)，無(wú)法僅按照推文id大小查找先后順序，所以在創(chuàng)建新的推文時(shí)不僅保存期推文id，還保留了一個(gè)推文絕對(duì)id字段來(lái)保留全局先后順序，當(dāng)然是運(yùn)用元組最為合適了
1class Twitter:
2 def __init__(self):
3 '''
4 Initialize your data structure here.
5 '''
6 self.user = {}#當(dāng)前系統(tǒng)用戶列表，每個(gè)用戶對(duì)應(yīng)2個(gè)子字典，F(xiàn)和T
7 self.Tid = 0 #記錄推文絕對(duì)id
8
9 def _new_user(self, userId):
10 '''
11 create a new user, follow self
12 '''
13 F = {userId}#關(guān)注者集合，并初始時(shí)關(guān)注自己
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))#更新推文列表，記錄為元組：(推文絕對(duì)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'])#關(guān)注的推文
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)#利用集合的自動(dòng)去重特性，省去重復(fù)關(guān)注的判斷
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)#集合的刪除，省去判斷元素是否存在
以上，就是綜合運(yùn)用了python中4個(gè)基本數(shù)據(jù)結(jié)構(gòu)各自特性的一個(gè)案例，基本上是考慮了各數(shù)據(jù)類型的優(yōu)點(diǎn)。
|
