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