01 初識collections

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

最初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 雙端隊列：deque

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

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

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

需注意的幾個要點：

1. deque在初始化時，可以接受一個任意可迭代類型或者為空，同時可接受一個缺省參數(shù)maxlen，如果不提供maxlen值，則默認(rèn)不限長度。
2. 初始化如果提供maxlen參數(shù)，在append、appendleft、extend和extendleft 4類操作中，若增加元素后超過最大長度，操作不會報錯，而是在操作的另一端自動丟棄多余元素（模擬處理"過期"元素）；但在insert操作中，由于目標(biāo)是在deque之間插入，deque無法"決策"該丟棄哪一端的多余元素，從而引發(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()不支持任意索引的彈出，即僅能彈出左端或右端的元素，兩個函數(shù)不允許接受任意參數(shù)。
4. rotate()操作可以很容易的實現(xiàn)經(jīng)典的旋轉(zhuǎ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相比列表的一個缺點。

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的所有操作，重點是在初始化時可以接收一個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ù)操作元素時可以直接操作，無需判斷是否存在及初始化。例如，想用字典統(tǒng)計一個列表中各元素的個數(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})

或者列表中元素是一個元組類型，我們需要記錄所有相同key的對應(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只是在操作某一個此前不存在的key時自動用default_factory初始化一個value，但在in操作時，若此前不存在則仍然判斷為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 計數(shù)器：Counter

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

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

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

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

而在用一個字典初始化時，value值可以不是整數(shù)，甚至可以不是數(shù)值（不過個人認(rèn)為這已經(jīng)違背了計數(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作為一個計數(shù)器容器類型，有幾個常用的統(tǒng)計類接口：

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

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

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

運用Counter類的操作，有時可以得到很好的效果。例如：

• 利用減法“-”操作的前向保留特點：

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

示例 ：

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

輸出：5

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

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

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

利用Counter初始化時保留迭代元素出場順序的特點：

字符串S和 T 只包含小寫字符。在S中，所有字符只會出現(xiàn)一次。S 已經(jīng)根據(jù)某種規(guī)則進(jìn)行了排序。我們要根據(jù)S中的字符順序?qū)進(jìn)行排序。更具體地說，如果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" 沒有在S中出現(xiàn), 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的輸出。

來源：力扣（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)，對于python通用內(nèi)置類型list、dict等是一個很好的擴(kuò)展和補(bǔ)充
2. deque實現(xiàn)了一個雙端隊列，可以實現(xiàn)O(1)復(fù)雜度的雙向添加和彈出元素以及擴(kuò)展，但remove()和insert()仍然是O(n)操作。pop()和popleft()不接受任何參數(shù)，僅能彈出端頭元素
3. defaultdict可以通過設(shè)置默認(rèn)值實現(xiàn)直訪問字典的key值，而無需判斷是否存在
4. Counter繼承字典，可以很好的實現(xiàn)計數(shù)器功能，并支持常用的+、-、交、并操作。

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