01 初識collections

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

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

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

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

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

02 雙端隊列：deque

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

其常用函數包括：

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

需注意的幾個要點：

1. deque在初始化時，可以接受一個任意可迭代類型或者為空，同時可接受一個缺省參數maxlen，如果不提供maxlen值，則默認不限長度。
2. 初始化如果提供maxlen參數，在append、appendleft、extend和extendleft 4類操作中，若增加元素后超過最大長度，操作不會報錯，而是在操作的另一端自動丟棄多余元素（模擬處理"過期"元素）；但在insert操作中，由于目標是在deque之間插入，deque無法"決策"該丟棄哪一端的多余元素，從而引發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()是在左端擴展，而且是將可迭代元素以相反的順序擴展到左端。
2. extendleft()和popleft()是O(1)復雜度，但remove()和insert()仍然是O(n)復雜度。
3. pop()和popleft()不支持任意索引的彈出，即僅能彈出左端或右端的元素，兩個函數不允許接受任意參數。
4. rotate()操作可以很容易的實現經典的旋轉字符串問題

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 默認字典：defaultdict

defaultdict是python內置類型dict的子類，支持dict的所有操作，重點是在初始化時可以接收一個default_factory作為字典默認生成類型。

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的最大便利是指定默認類型后，后續操作元素時可以直接操作，無需判斷是否存在及初始化。例如，想用字典統計一個列表中各元素的個數，可以這樣操作：

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的對應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類型默認字典。注意：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 計數器：Counter

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

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

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

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

而在用一個字典初始化時，value值可以不是整數，甚至可以不是數值（不過個人認為這已經違背了計數器的初衷）

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作為一個計數器容器類型，有幾個常用的統計類接口：

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

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

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

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

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

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

示例 ：

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

輸出：5

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

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

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

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

字符串S和 T 只包含小寫字符。在S中，所有字符只會出現一次。S 已經根據某種規則進行了排序。我們要根據S中的字符順序對T進行排序。更具體地說，如果S中x在y之前出現，那么返回的字符串中x也應出現在y之前。返回任意一種符合條件的字符串T。

示例:

輸入:

S = "cba"

T = "abcd"

輸出: "cbad"

解釋:

S中出現了字符 "a", "b", "c", 所以 "a", "b", "c" 的順序應該是 "c", "b", "a".

由于 "d" 沒有在S中出現, 它可以放在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 總結

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

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