Python Deep Drive III 第 9 節 – Specialized Dictionaries

Python 深入學習 3. Dictionaries
1

▌collections

資料來源：collections — 容器資料型態 — Python 3.11.2 說明文件

原始碼： Lib/collections/__init__.py

這個模組實作了一些特別的容器資料型態，用來替代 Python 一般內建的容器，例如 dict（字典）、list（串列）、set（集合）和 tuple（元組）。

namedtuple() 用來建立具名欄位的 tuple 子類別的工廠函式
deque 一個類似 list 的容器，可以快速的在頭尾加入 (append) 元素與移除 (pop) 元素
ChainMap 一個類似 dict 的類別，用來為多個對映 (mapping) 建立單一的視圖 (view)
Counter dict subclass for counting hashable objects
OrderedDict dict 的子類別，會記錄物件被加入的順序
defaultdict dict 的子類別，當值不存在 dict 中時會呼叫一個提供預設值的工廠函式
UserDict dict 物件的包裝器 (wrapper)，簡化了 dict 的子類別化過程
UserList list 物件的包裝器，簡化了 list 的子類別化過程
UserString 字串物件的包裝器，簡化了字串的子類別化過程

▌OrderedDict vs Python 3.6 Plain Dicts

本節 Fred 老師的 github (Jupyter Notebook)

這節主要在示範，使用 Python 3.6 Plain Dicts，來實作原本只在 OrderedDict 支援的 methods。

  • reverse iteration

  • pop first/last item

  • move key to beginning/end of dictionary

  • equality (==) that takes key order into account

reverse iteration

其實目前 Plain Dicts 就已經支援了。（老師說 3.8 之後，但我沒去確認）

老師的示範程式：

from collections import OrderedDict

d1 = OrderedDict(a=1, b=2, c=3, d=4)
d2 = dict(a=1, b=2, c=3, d=4)

print(d1)
# OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])
print(d2)
# {'a': 1, 'b': 2, 'c': 3, 'd': 4}

for k in reversed(d1): # 目前版本的 Python，這裡放 d2 一樣可以
    print(k)
# d
# c
# b
# a

for k in reversed(list(d2.keys())):
    print(k)
# d
# c
# b
# a

Popping Items

要從 dict 前面或後面移除一個 element，首要之務就是取得他的 key 值。

老師的示範程式：

d2 = dict(a=1, b=2, c=3, d=4)

def popitem(d, last=True):
    if last:
        return d.popitem()
    else:
        first_key = next(iter(d.keys()))
        return first_key, d.pop(first_key)

d2 = dict(a=1, b=2, c=3, d=4)
print(d2)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
print(popitem(d2))  # ('d', 4)
print(d2)  # {'a': 1, 'b': 2, 'c': 3}

d2 = dict(a=1, b=2, c=3, d=4)
print(d2)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
print(popitem(d2, last=False))  # ('a', 1)
print(d2)  # {'b': 2, 'c': 3, 'd': 4}

補充：我請 ChatGPT 寫一個從 dict 移除頭尾的 popitem 示範碼，結果他張冠李戴，把 OrderedDict 的拿來用。

  • dict 的 popitem() 無參數，從尾端移除 element（Python 3.7 以上）
  • OrderedDict 的 popitem(last=True) 可指定 last 是 True or False

Move to End

移到尾端很容易，先 pop 該 element，然後再 insert 即可（預設插入尾端）。

老師的示範程式：

d2 = dict(a=1, b=2, c=3, d=4)
print(d2)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}

key = 'b'
d2[key] = d2.pop(key)
print(d2)  # {'a': 1, 'c': 3, 'd': 4, 'b': 2}

Moving to the beginning

移到前端複雜些。老師的解法是，先將該 element 移到尾端，然後整個 dict 一個一個 element 往前 shift，直到移至最前端。

利百代 彩虹筆

老師的示範程式：

d = dict(a=1, b=2, c=3, d=4, e=5, f=6)
key = 'c'

print(d.keys())  # dict_keys(['a', 'b', 'c', 'd', 'e', 'f'])

# first move desired key to end
d[key] = d.pop(key)  
print(d.keys())  # dict_keys(['a', 'b', 'd', 'e', 'f', 'c'])

keys = list(d.keys())[:-1]
for key in keys:
    d[key] = d.pop(key)
    print(d.keys())  # 所有 element 逐項自尾端往前 shift
    
print(d)  # {'c': 3, 'a': 1, 'b': 2, 'd': 4, 'e': 5, 'f': 6}

當然，我們可以把 Move to end 和 Move to the beginning 放在一個函式中：

def move_to_end(d, key, *, last=True):
    d[key] = d.pop(key)
    
    if not last:
        for key in list(d.keys())[:-1]:
            d[key] = d.pop(key)  

d = dict(a=1, b=2, c=3, d=4, e=5, f=6)

move_to_end(d, 'c')
print(d)  # {'a': 1, 'b': 2, 'd': 4, 'e': 5, 'f': 6, 'c': 3}

move_to_end(d, 'c', last=False)
print(d)  # {'c': 2, 'a': 1, 'b': 2, 'd': 3, 'e': 4, 'f': 5}

Equality Comparison

Python 3.6 之後的 dict 即支援順序，所以這個相等有兩個特性：

  1. 鍵／值相等。
  2. 順序相同。

首先老師先示範基本概念：

d1 = {'a': 10, 'b': 20, 'c': 30}
d2 = {'b': 20, 'c': 30, 'a': 10}

d1 == d2  # True

d1.keys() == d2.keys()  # True。因為 key 的行為模式是 set，所以沒有順序之分。

list(d1.keys()) == list(d2.keys())  # False。先轉成有順序的 list 就可以比較了。

d1 == d2 and list(d1.keys()) == list(d2.keys())  # False

但轉成 list 會占用較多的記憶體，所以我們使用 iteration 來逐一比較各個 key。這裡老師使用 zip 來示範：

def dict_equal_sensitive(d1, d2):
    if d1 == d2:
        for k1, k2 in zip(d1.keys(), d2.keys()):
            if k1 != k2:
                return False
        return True
    else:
        return False

dict_equal_sensitive(d1, d2)  # False

dict_equal_sensitive(d1, d1)  # True

如果不想用 loop，也可以用 all 和 map 來實作。

def dict_equal_sensitive(d1, d2):
    if d1 == d2:
        return all(map(lambda el: el[0] == el[1], 
                       zip(d1.keys(), d2.keys())
                      )
                  )
    else:
        return False

dict_equal_sensitive(d1, d2)  # False

dict_equal_sensitive(d1, d1)  # True

如果你只需要保證 dict 的順序，那麼標準的 dict 就可以了。

如果會用到上述這些特殊的 method，直接用 OrderedDict 提供的會方便快速許多。

Timings

照慣例，來看看 dicts 和 OrderedDicts 的效能差異。

老師的示範程式，請自行參考 github。這裡列出效能比較表（單位：秒）：

dict OrderedDict
creating 0.4636 0.7186
get key value 0.0056 0.0058
pop last 0.0650 0.2618
pop first 2.9098 0.0380
move_to_end ? ?
equality ? ?

▌OrderedDict

這裡是請 ChatGPT 產生的 collections.OrderedDict class methods 表格：
Here is a table explaining the methods available in the collections.OrderedDict class in Python:

Method Description
OrderedDict() Constructor for creating an ordered dictionary object. Can be called with no arguments or with a mapping object, an iterable of (key, value) pairs, or keyword arguments.
clear() Removes all elements from the ordered dictionary.
copy() Returns a shallow copy of the ordered dictionary.
fromkeys(seq[, value]) Returns a new ordered dictionary with keys from seq and values set to value.
get(key[, default]) Returns the value of the specified key. If the key is not found, it returns default or None if default is not provided.
items() Returns a view of the ordered dictionary’s items as a list of (key, value) pairs.
keys() Returns a view of the ordered dictionary’s keys as a list.
pop(key[, default]) Removes the specified key and returns its value. If the key is not found, it returns default or raises a KeyError if default is not provided.
popitem() Removes and returns the (key, value) pair that was last inserted.
setdefault(key[, default]) Returns the value of the specified key. If the key is not found, it inserts default as the key’s value and returns default. If default is not provided, it inserts None as the key’s value.
update([other]) Merges the elements of other into the ordered dictionary. other can be a mapping object, an iterable of (key, value) pairs, or keyword arguments.
values() Returns a view of the ordered dictionary’s values as a list.

In conclusion, the collections.OrderedDict class provides all the functionality of a regular dictionary, with the added benefit of preserving the order of items.

▌Counter

本章 Fred 老師的 github (Jupyter Notebook)

請 ChatGPT 產生 collections.Counter class methods 表格，我把老師在課程中說明到的 method，用顏色標出：

By ChatGPT：以下是按照使用頻率排序後的 Python Counter 類別中的方法，以表格的形式呈現，並且附上中文說明：

Method - 方法名稱 Description - 說明
most_common([n]) 回傳一個包含 n 個最常出現元素及其計數次數的列表，若未指定 n 則回傳所有元素。
這是最常用的方法之一，可以用來查找 Counter 中出現次數最多的元素。
update([iterable-or-mapping]) 使用給定的可迭代對象或映射更新 Counter 中元素的計數。
這個方法可以用來將多個 Counter 合併起來，或者將 Counter 更新為另一個可迭代對象中元素的計數。
elements() 回傳一個迭代器，重複每個元素其計數次數所示的次數。
這個方法可以用來取得 Counter 中所有元素，包括重複的元素，並且可以用來進行迭代。
copy() 回傳 Counter 的一個淺層複本。
這個方法可以用來複製一個 Counter，以便進行修改或比較。
items() 回傳 Counter 中所有元素及其計數的列表。
這個方法可以用來取得 Counter 中所有元素及其計數，並且可以用來進行迭代。
subtract([iterable-or-mapping]) 從 Counter 中減去給定的可迭代對象或映射的計數。
這個方法可以用來減少 Counter 中元素的計數，或者從 Counter 中刪除一些元素。
keys() 回傳 Counter 中所有唯一元素的列表。
這個方法可以用來取得 Counter 中所有唯一元素，並且可以用來進行迭代。
values() 回傳 Counter 中所有元素的計數的列表。
這個方法可以用來取得 Counter 中所有元素的計數，並且可以用來進行迭代。
clear() 從 Counter 中刪除所有元素及其計數。
這個方法可以用來清空一個 Counter，以便重新使用。
fromkeys([iterable], [value]) 回傳一個新的 Counter，其鍵由可迭代對象指定，值設為指定的值（預設為 0）。
這個方法可以用來創建一個新的 Counter

ChatGPT 好心提醒：這裡只列出部分比較常用的。

以下是程式範例（一樣請 ChatGPT 產生）。

defaultdict

老師並沒有特別解釋，只在講解 Counter 時順便舉例。

我請 ChatGPT 比較 defaultdict 和 Counter，可能他這部分的資料庫比較少（或者我問的方式太接近），中文的回答基本上只是英文翻譯（以下內容我稍微改過）：

defaultdict 是一種特殊的字典，當訪問一個不存在的鍵（key）時，defaultdict 會自動創建一個對應的值，這個值是由使用者指定的 factory 函數生成的。當傳入的 key 是 int 時，預設值為 0。例如：

from collections import defaultdict

my_dict = defaultdict(int)
my_dict['a'] += 1
print(my_dict)  # defaultdict(<class 'int'>, {'a': 1})
print(my_dict['b'])  # 0
print(my_dict)  # defaultdict(<class 'int'>, {'a': 1, 'b': 0})

Counter 是計數工具，用於統計序列中每個元素出現的次數。我們可以將任何可迭代對象傳入 Counter 的建構函數，它會返回一個字典，其中每個元素都是鍵（key），其出現次數是對應的值（value）。例如：

from collections import Counter

my_list = [1, 2, 3, 1, 2, 1, 1, 4, 4, 4]
my_counter = Counter(my_list)
print(my_counter)  # Counter({1: 4, 4: 3, 2: 2, 3: 1})

對 defaultdict 感興趣的朋友，可以參考這一篇文章。他簡單說明了 defaultdict 的一些擴充特性：__missing__(key) 以及 default_factory。

以下為 Fred 講師的補充說明

好吧，如果這就是全部，Counter 那麼擁有一個不同於OrderedDict .

但是Counter 有許多在計數器上下文中有意義的附加方法：

  1. 遍歷計數器的所有元素，但重複元素的次數與其頻率相同
  2. 找到n 最常見的（按頻率）元素
  3. 根據另一個Counter （或可迭代的）遞減計數器
  4. 根據另一個Counter （或可迭代的）增加計數器
  5. 專門的構造函數提供額外的靈活性

如果你熟悉多重集，那麼這本質上是一個可以用於多重集的數據結構。

OK, so if that’s all there was to Counter it would be pretty odd to have a data structure different than OrderedDict.

But Counter has a slew of additional methods which make sense in the context of counters:

  1. Iterate through all the elements of counters, but repeat the elements as many times as their frequency
  2. Find the n most common (by frequency) elements
  3. Decrement the counters based on another Counter (or iterable)
  4. Increment the counters based on another Counter (or iterable)
  5. Specialized constructor for additional flexibility

If you are familiar with multisets, then this is essentially a data structure that can be used for multisets.

Constructor

在 iterable 中，會自動支援 element 的出現次數計算。包含 string, list…etc.

範例：

from collections import Counter

# strings
c1 = Counter('able was I ere I saw elba')

# list
import random
random.seed(0)
my_list = [random.randint(0, 10) for _ in range(1_000)]
c2 = Counter(my_list)

# keyword arguments
c3 = Counter(a=1, b=10)

# dictionary
c4 = Counter({'a': 1, 'b': 10})

我們可以在初始化 Counter 物件時，傳入 keyword arguments，甚至 dictionary。

範例：

from collections import Counter

c2 = Counter(a=1, b=10)
c2
# Counter({'a': 1, 'b': 10})

c3 = Counter({'a': 1, 'b': 10})
c3
# Counter({'a': 1, 'b': 10})

我們可以在 Counter object 中，儲存整數以外的值。但用途有限，因為預設值仍然是 0，與 object 中包含的其他值無關。

老師上面的 5 有提到 Specialized constructor for additional flexibility，那麼有哪些常見的 constructor？

以下為 ChatGPT 產生，待整理確認。

方法 1

Creating a Counter from an iterable: You can create a Counter by passing an iterable (e.g., list, tuple, string) to the Counter() constructor.

from collections import Counter

my_list = [1, 2, 3, 1, 2, 1, 1, 4, 4, 4]
my_counter = Counter(my_list)
print(my_counter)

The resulting Counter object will count the occurrences of each element in the iterable.

Output:

Counter({1: 4, 4: 3, 2: 2, 3: 1})

方法 2

Creating a Counter from a dictionary: You can also create a Counter by passing a dictionary to the Counter() constructor. The resulting Counter object will count the occurrences of each key in the dictionary.

from collections import Counter

my_dict = {'apple': 3, 'banana': 2, 'orange': 1}
my_counter = Counter(my_dict)
print(my_counter)

Output:

Counter({'apple': 3, 'banana': 2, 'orange': 1})

方法 3

Creating an empty Counter and updating it: You can create an empty Counter object and update it with elements one at a time using the update() method.

from collections import Counter

my_counter = Counter()
my_counter.update([1, 2, 3, 1, 2, 1, 1, 4, 4, 4])
print(my_counter)

Output:

Counter({1: 4, 4: 3, 2: 2, 3: 1})

方法 4

Creating a Counter with keyword arguments: You can also create a Counter object by passing key-value pairs as keyword arguments to the Counter() constructor.

from collections import Counter

my_counter = Counter(apples=3, bananas=2, oranges=1)
print(my_counter)

Output:

Counter({'apples': 3, 'bananas': 2, 'oranges': 1})

most_common

ChatGPT most_common method 的說明及範例：

回傳一個包含 n 個最常出現元素及其計數次數的列表，若未指定 n 則回傳所有元素。

這是最常用的方法之一，可以用來查找 Counter 中出現次數最多的元素。

from collections import Counter

article = "省略"

word_counts = Counter(article.split())
top_5_words = word_counts.most_common(5)

print("Top 5 most common words:")
for word, count in top_5_words:
    print(f"{word}: {count}")

elements

Repeated Iteration

回傳一個迭代器，重複每個元素其計數次數所示的次數。

這個方法可以用來取得 Counter 中所有元素，包括重複的元素，並且可以用來進行迭代。

c1 = Counter('abba')
c1 # Counter({'a': 2, 'b': 2})

for c in c1:
    print(c)
# a
# b

for c in c1.elements():
    print(c)
# a
# a
# b
# b

我們可以利用它來建立一個含重覆元素的 iterable。

假設我們要建立一個從數字 1 往上數，重覆次數就是該數字的 list。

傳統的做法可能是這樣：

l = []
for i in range(1, 11):
    for _ in range(i):
        l.append(i)
print(l)

使用 elements 也可以達成。而且 elements 會傳回 chain object，它是一個 lazy iterable，不需要產生 list（吃記憶體）就可以達成上述目的。

c1 = Counter()
for i in range(1, 11):
    c1[i] = i

c1 # Counter({1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10})

print(c1.elements())
# <itertools.chain object at 0x1047aa518>

for i in c1.elements():
    print(i, end=', ')
#  1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5...

那麼，我們是否可以用 plain dict 來自己寫一個呢？

請參考老師的原始碼。

update / subtract

使用給定的可迭代對象或映射更新 Counter 中元素的計數。

這個方法可以用來將多個 Counter 合併起來，或者將 Counter 更新為另一個可迭代對象中元素的計數。

c1 = Counter(a=1, b=2, c=3)
c2 = Counter(b=1, c=2, d=3)

c1.update(c2)
print(c1)  # Counter({'c': 5, 'b': 3, 'd': 3, 'a': 1})

Counter 可以是負數。

c1 = Counter(a=1, b=2, c=3)
c2 = Counter(b=1, c=2, d=3)

c1.subtract(c2)
print(c1)  # Counter({'a': 1, 'b': 1, 'c': 1, 'd': -3})

c1 = Counter('aabbccddee')
print(c1)  # Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2})

c1.update('abcdef')
print(c1)  # Counter({'a': 3, 'b': 3, 'c': 3, 'd': 3, 'e': 3, 'f': 1})

Mathematical Operations: + - & |

  • +: same as update, but returns a new Counter object instead of an in-place update.

  • -: subtracts one counter from another, but discards zero and negative values

  • &: keeps the minimum of the key values

  • |: keeps the maximum of the key values

c1 = Counter('aabbcc')
c2 = Counter('abc')

c1 + c2
# Counter({'a': 3, 'b': 3, 'c': 3})

c1 - c2
# Counter({'a': 1, 'b': 1, 'c': 1})

c1 = Counter(a=5, b=1)
c2 = Counter(a=1, b=10)

c1 & c2
# Counter({'a': 1, 'b': 1})

c1 | c2
# Counter({'a': 5, 'b': 10})

+ - 也可以做一元運算

  • + : remove any non-positive count from the Counter

  • - : changes the sign of each counter, and removes any non-positive result:

c1 = Counter(a=10, b=-10)
+c1
# Counter({'a': 10})

-c1
# Counter({'b': 10})

應用範例：計算銷售最好的前三項電腦週邊。

你有兩個資料源：銷售列表、退貨列表。從前者減去後者，就是你要的答案。

不過可以思考一下，為什麼這個範例要用 Counter 做？有沒有更好的 use case？

結果老師也是這麼想，也示範了給我們看。

範例請參考老師的 github。