collections：一款強(qiáng)大的內(nèi)置容器

01 初識(shí)collections

Collections模塊是python的內(nèi)置模塊之一，提供了很多容器類型。按照官方文檔介紹，它被用作是對(duì)python通用內(nèi)置類型（list、dict、set、tuple）的一個(gè)替代。

最初collections模塊的類型眾多，在python3.3版本中將一部分抽象數(shù)據(jù)類型寫進(jìn)了collections.abc（abc，abstract base classes）中，后續(xù)將在python3.9版本全部整合至collections.abc模塊。

collections模塊提供了9種容器類型

（適用于python3.8及更早版本）

collections模塊當(dāng)前包括9類容器接口，本文主要介紹其中比較常用的3種數(shù)據(jù)類型：deque，defaultdict，Counter。

02 雙端隊(duì)列：deque

deque（double-ended queue）是一個(gè)與列表類似的容器類型，其最大的優(yōu)勢(shì)在于支持高效的雙端添加(append)和彈出(pop)操作，兩個(gè)方向的開(kāi)銷都是 O(1) 復(fù)雜度。

其常用函數(shù)包括：

append(x)#添加 x 到右端。
appendleft(x)#添加 x 到左端。
extend(iterable)#擴(kuò)展deque的右側(cè)，通過(guò)添加iterable參數(shù)中的元素。
extendleft(iterable)#擴(kuò)展deque的左側(cè)，通過(guò)添加iterable參數(shù)中的元素。注意，iterable參數(shù)中的順序?qū)⒈环催^(guò)來(lái)添加。
insert(i, x)#在位置 i 插入 x 。如果插入會(huì)導(dǎo)致一個(gè)限長(zhǎng) deque 超出長(zhǎng)度 maxlen 的話，就引發(fā)一個(gè)IndexError
pop()#移去并且返回一個(gè)元素，deque 最右側(cè)的那一個(gè)。 如果沒(méi)有元素的話，就引發(fā)一個(gè) IndexError。
popleft()#移去并且返回一個(gè)元素，deque 最左側(cè)的那一個(gè)。 如果沒(méi)有元素的話，就引發(fā) IndexError。
remove(value)#移除找到的第一個(gè) value。 如果沒(méi)有的話就引發(fā) ValueError。
index(x[, start[, stop]])#返回 x 在 deque 中的位置（在索引 start 之后，索引 stop 之前）。 返回第一個(gè)匹配項(xiàng)，如果未找到則引發(fā) ValueError。
count(x)#計(jì)算 deque 中元素等于 x 的個(gè)數(shù)。
reverse()#將deque逆序排列。返回 None 。
rotate(n=1)#向右循環(huán)移動(dòng) n 步。 如果 n 是負(fù)數(shù)，就向左循環(huán)。
#如果deque不是空的，向右循環(huán)移動(dòng)一步就等價(jià)于 d.appendleft(d.pop()) ， 向左循環(huán)一步就等價(jià)于 d.append(d.popleft()) 。
clear()#移除所有元素，使其長(zhǎng)度為0.
copy()#創(chuàng)建一份淺拷貝。

需注意的幾個(gè)要點(diǎn)：

1. deque在初始化時(shí)，可以接受一個(gè)任意可迭代類型或者為空，同時(shí)可接受一個(gè)缺省參數(shù)maxlen，如果不提供maxlen值，則默認(rèn)不限長(zhǎng)度。
2. 初始化如果提供maxlen參數(shù)，在append、appendleft、extend和extendleft 4類操作中，若增加元素后超過(guò)最大長(zhǎng)度，操作不會(huì)報(bào)錯(cuò)，而是在操作的另一端自動(dòng)丟棄多余元素（模擬處理"過(guò)期"元素）；但在insert操作中，由于目標(biāo)是在deque之間插入，deque無(wú)法"決策"該丟棄哪一端的多余元素，從而引發(fā)IndexError

from collections import deque
dq = deque('abcde', 6)
dq.extend('fg')
print(dq)#deque(['b', 'c', 'd', 'e', 'f', 'g'], maxlen=6)
dq.appendleft('h')
print(dq)#deque(['h', 'b', 'c', 'd', 'e', 'f'], maxlen=6)
dq.insert(3,'i')
print(dq)#IndexError: deque already at its maximum size

1. extendleft()是在左端擴(kuò)展，而且是將可迭代元素以相反的順序擴(kuò)展到左端。
2. extendleft()和popleft()是O(1)復(fù)雜度，但remove()和insert()仍然是O(n)復(fù)雜度。
3. pop()和popleft()不支持任意索引的彈出，即僅能彈出左端或右端的元素，兩個(gè)函數(shù)不允許接受任意參數(shù)。
4. rotate()操作可以很容易的實(shí)現(xiàn)經(jīng)典的旋轉(zhuǎn)字符串問(wèn)題

from collections import deque
dq = deque('abcdefg')
dq.rotate(3)#右旋3位
print(dq)#deque(['e', 'f', 'g', 'a', 'b', 'c', 'd'])

deque支持迭代、len()、in等基本操作，但不支持切片操作，這也是deque相比列表的一個(gè)缺點(diǎn)。

from collections import deque
dq = deque([1, 2, 3, 4])
dq[0:2]#TypeError: sequence index must be integer, not 'slice'

03 默認(rèn)字典：defaultdict

defaultdict是python內(nèi)置類型dict的子類，支持dict的所有操作，重點(diǎn)是在初始化時(shí)可以接收一個(gè)default_factory作為字典默認(rèn)生成類型。

def __init__(self, default_factory=None, **kwargs): # known case of _collections.defaultdict.__init__
    """
    defaultdict(default_factory[, ...]) -- > dict with default factory

    The default factory is called without arguments to produce
    a new value when a key is not present, in __getitem__ only.
    A defaultdict compares equal to a dict with the same items.
    All remaining arguments are treated the same as if they were
    passed to the dict constructor, including keyword arguments.

    # (copied from class doc)
    """

使用defaultdict的最大便利是指定默認(rèn)類型后，后續(xù)操作元素時(shí)可以直接操作，無(wú)需判斷是否存在及初始化。例如，想用字典統(tǒng)計(jì)一個(gè)列表中各元素的個(gè)數(shù)，可以這樣操作：

from collections import defaultdict
colors = ['yellow', 'blue', 'yellow', 'blue', 'red']
colorDict = defaultdict(int)
for color in colors:
    colorDict[color] += 1
print(colorDict)#defaultdict(< class 'int' >, {'yellow': 2, 'blue': 2, 'red': 1})

或者列表中元素是一個(gè)元組類型，我們需要記錄所有相同key的對(duì)應(yīng)value值：

from collections import defaultdict
persons = [('name', 'A'), ('name', 'B'), ('age', 18), ('age', 20), ('name', 'C')]
perDict = defaultdict(list)
for k, v in persons:
    perDict[k].append(v)
print(perDict)#defaultdict(< class 'list' >, {'name': ['A', 'B', 'C'], 'age': [18, 20]})

除了int和list外，還支持set類型默認(rèn)字典。注意：defaultdict只是在操作某一個(gè)此前不存在的key時(shí)自動(dòng)用default_factory初始化一個(gè)value，但在in操作時(shí)，若此前不存在則仍然判斷為False。

from collections import defaultdict
persons = [('name', 'A'), ('name', 'B'), ('age', 18), ('age', 20), ('name', 'C')]
perDict = defaultdict(list)
for k, v in persons:
    perDict[k].append(v)
'height' in perDict #False

04 計(jì)數(shù)器：Counter

在上個(gè)例子中，我們利用defaultdict簡(jiǎn)化了統(tǒng)計(jì)列表中元素個(gè)數(shù)的操作，但實(shí)際上collections中針對(duì)計(jì)數(shù)操作還有一個(gè)更加專業(yè)的容器類型：Counter。

Counter類型也是一個(gè)繼承自dict類型的容器，同時(shí)也是一個(gè)集合，元素及其計(jì)數(shù)值存儲(chǔ)為key：value值。這里，計(jì)數(shù)可以是任何整數(shù)值，包括0和負(fù)數(shù)。

初始化一個(gè)Counter類型主要有2種方式：

1. 用一個(gè)可迭代對(duì)象或者一個(gè)字典：
2. 在用可迭代對(duì)象初始化時(shí)，counter會(huì)自動(dòng)統(tǒng)計(jì)所有元素及其出現(xiàn)的次數(shù)，且統(tǒng)計(jì)元素保留迭代對(duì)象中元素出現(xiàn)的先后順序（這點(diǎn)比較關(guān)鍵，后面有例為證）；

而在用一個(gè)字典初始化時(shí)，value值可以不是整數(shù)，甚至可以不是數(shù)值（不過(guò)個(gè)人認(rèn)為這已經(jīng)違背了計(jì)數(shù)器的初衷）

from collections import Counter
colors = ['blue', 'red', 'green', 'blue', 'red', 'yellow']
colorC = Counter(colors)
print(colorC)#Counter({'blue': 2, 'red': 2, 'green': 1, 'yellow': 1})
persons = {'name':'AA', 'age':20}
personC = Counter(persons)
print(personC)#Counter({'name': 'AA', 'age': 20})

Counter作為一個(gè)計(jì)數(shù)器容器類型，有幾個(gè)常用的統(tǒng)計(jì)類接口：

elements()#返回一個(gè)迭代器，其中每個(gè)元素重復(fù)其計(jì)數(shù)值次。 元素會(huì)按首次出現(xiàn)的順序返回。 如果一個(gè)元素的計(jì)數(shù)值小于一，elements() 將會(huì)忽略它。
most_common([n])#返回一個(gè)列表，其中包含 n 個(gè)最常見(jiàn)的元素及出現(xiàn)次數(shù)，按常見(jiàn)程度由高到低排序。 如果 n 被省略或?yàn)?None，most_common() 將返回計(jì)數(shù)器中的 所有 元素。 計(jì)數(shù)值相等的元素按首次出現(xiàn)的順序排序：
subtract([iterable-or-mapping])#從 迭代對(duì)象 或 映射對(duì)象 減去元素。像 dict.update() 但是是減去，而不是替換。輸入和輸出都可以是0或者負(fù)數(shù)。
A+B #計(jì)數(shù)器相加
A-B #計(jì)數(shù)器相減
A&B #計(jì)數(shù)器交集
A|B #計(jì)數(shù)器并集

利用這些接口，可以方便的實(shí)現(xiàn)特定的一些計(jì)數(shù)統(tǒng)計(jì)，包括出現(xiàn)最多的元素及其個(gè)數(shù)、加減法等。重點(diǎn)說(shuō)明下Counter中的兩個(gè)"減法"操作，一個(gè)是subtract，另一個(gè)是“-”，即重載的__sub__操作，二者主要區(qū)別如下：

1. subtract是實(shí)例方法，__sub__是重寫的類方法。
2. subtract對(duì)實(shí)例進(jìn)行inplace操作，無(wú)返回值，而__sub__返回相減后的結(jié)果。
3. subtract是簡(jiǎn)單的完成元素及其計(jì)數(shù)的減法，即：A、B都有的元素，結(jié)果是基數(shù)之差，0個(gè)也會(huì)包含在結(jié)果中；A有B無(wú)的，則直接返回A的計(jì)數(shù)值；A無(wú)B有的，則會(huì)按A中相應(yīng)元素計(jì)數(shù)為0去操作減法，返回的是B中元素計(jì)數(shù)值的負(fù)數(shù)。
4. __sub__中以"-"操作符前面的對(duì)象為主（姑且叫做前向保留），即忽略前面沒(méi)有而后面對(duì)象特有的元素，當(dāng)共有元素計(jì)數(shù)相減為0時(shí)，結(jié)果不保留（類似SQL語(yǔ)言中的left join）。

from collections import Counter
A = Counter([1, 3, 4, 2, 2, 3, 4])
B = Counter([1, 2, 4, 5, 6, 6, 7])
print(A, B)  #Counter({3: 2, 4: 2, 2: 2, 1: 1}) Counter({6: 2, 1: 1, 2: 1, 4: 1, 5: 1, 7: 1})
print(A.most_common(3))  #[(3, 2), (4, 2), (2, 2)]
print(A-B) ##Counter({3: 2, 4: 1, 2: 1})
A.subtract(B) ## 對(duì)A進(jìn)行inplace操作，操作后A：Counter({1: 0, 3: 2, 4: 1, 2: 1, 5: -1, 6: -2, 7: -1})

運(yùn)用Counter類的操作，有時(shí)可以得到很好的效果。例如：

• 利用減法“-”操作的前向保留特點(diǎn)：

給你兩個(gè)長(zhǎng)度相等的字符串 s 和 t。每一個(gè)步驟中，你可以選擇將 t 中的 任一字符 替換為 另一個(gè)字符。返回使 t 成為 s 的字母異位詞的最小步驟數(shù)。字母異位詞 指字母相同，但排列不同的字符串。

示例 ：

輸出：s = "leetcode", t = "practice"

輸出：5

提示：用合適的字符替換 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 變成 s 的字母異位詞。

來(lái)源：力扣（LeetCode）1347# 制造字母異位詞的最小步驟數(shù)

class Solution:
    def minSteps(self, s: str, t: str) - > int:
        return sum((collections.Counter(s) - collections.Counter(t)).values())

利用Counter初始化時(shí)保留迭代元素出場(chǎng)順序的特點(diǎn)：

字符串S和 T 只包含小寫字符。在S中，所有字符只會(huì)出現(xiàn)一次。S 已經(jīng)根據(jù)某種規(guī)則進(jìn)行了排序。我們要根據(jù)S中的字符順序?qū)進(jìn)行排序。更具體地說(shuō)，如果S中x在y之前出現(xiàn)，那么返回的字符串中x也應(yīng)出現(xiàn)在y之前。返回任意一種符合條件的字符串T。

示例:

輸入:

S = "cba"

T = "abcd"

輸出: "cbad"

解釋:

S中出現(xiàn)了字符 "a", "b", "c", 所以 "a", "b", "c" 的順序應(yīng)該是 "c", "b", "a".

由于 "d" 沒(méi)有在S中出現(xiàn), 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的輸出。

來(lái)源：力扣（LeetCode）791#自定義字符串排序

class Solution:
    def customSortString(self, S: str, T: str) - > str:
        cs = collections.Counter(S)
        ct = collections.Counter(T)
        return ''.join(list(((cs+ct)-cs).elements()))

05 總結(jié)

1. collections模塊提供了很好的容器型數(shù)據(jù)結(jié)構(gòu)，對(duì)于python通用內(nèi)置類型list、dict等是一個(gè)很好的擴(kuò)展和補(bǔ)充
2. deque實(shí)現(xiàn)了一個(gè)雙端隊(duì)列，可以實(shí)現(xiàn)O(1)復(fù)雜度的雙向添加和彈出元素以及擴(kuò)展，但remove()和insert()仍然是O(n)操作。pop()和popleft()不接受任何參數(shù)，僅能彈出端頭元素
3. defaultdict可以通過(guò)設(shè)置默認(rèn)值實(shí)現(xiàn)直訪問(wèn)字典的key值，而無(wú)需判斷是否存在
4. Counter繼承字典，可以很好的實(shí)現(xiàn)計(jì)數(shù)器功能，并支持常用的+、-、交、并操作。

還有其他一些實(shí)用的功能，如namedtuple、ordereddict等讀者可以自行查詢使用。