Python: 愛他沒有如果 (Part 2)

前情提要: Part 1

最近比較有心情寫東西了，來把這個主題終結一下 XD

在上一篇提到將 legacy code 裡常看到的長長 if-else 改成 register pattern 的樣子，或許會覺得這樣寫很好，因此想將程式改成這個樣子。今天這篇就是接續上一篇，來根據 register pattern 使用到的資料結構 (hash table)，分析使用這樣的 pattern 之後可能造成的 performance impact。

畢竟，軟體工程的世界常常就是有一好就沒兩好。

Big-O 迷思

首先，我們知道 Python 的 dict 是以 hash table 的方式實作的，不像其他語言有區分不同的實作方式。譬如在 C++，如果想用 hash table 的話需要使用 <unordered_map> 這個 standard template library，而 <map> 裡面有的，通常會是一個以 binary search tree 來實作。

這邊不會特別細說 hash table，但簡單的來說 hash table 是透過一個雜湊函數 (hash function) 把一個 key 映射至一個 integer，然後在一段記憶體找到該 integer 對應的位置存放雜湊值、key 與 value，進而完成 key 與 value 對照的功能 (也就是可以透過 key 快速找到對應的 value)。以下圖為例來說，假設 key 算出來的 hash value 是 5，我們就把 (hash, key, value) 存到第 5 個 slot 裡：

簡單說明到此為止(免得被抓包我是資料結構白痴 😛)。

那根據 CPython 的 hash function 的實作，可以看到一個 hash function 的優勢在於它的時間複雜度是 O(1) 。稍微有經驗的工程師看到 O(1) 大概都會很高興，這好像是在說我們在 Part 1 說的改寫方式算是非常有效率的一種實作方式，但真的是這樣嗎？

我們常常聽見一些討論在說某某演算法是 O(N) 所以比另一個 O(N^2) 的演算法更快更好什麼的。這邊我們不細究 Big-O Notation O(.) 的定義，但簡單的來說就是在描述當數據量提升之後所需要的時間會趨近於什麼樣的估計值 (也就是跟 O 裡面那個函數只差了常數倍)。所以說 O(1) 的意思就是說執行某個函數會只需要固定的時間，與 input 大小無關。

所以說當我們在 Part 1 裡說的一樣，把一個長長的 if...elif...else 改成 hash table 之後，除了可以透過 register pattern 的方式動態加入新的 case 外，對每個 case 來說取得對應 handler 的時間也是一樣的，所以我們就可以得到一個有彈性…又快(?)的實作。

Slow Hash Function

到底替換成 O(1) 的 hash table 之後會不會變快，當然就取決於到底你用的 hash function 是執行起來是有多快囉，哪怕是固定的時間，如果執行起來太久，當然就可能比一個 if ... == ooo 來得更慢。

這邊我們就用一個簡單的例子來實驗一下：

這邊我故意在 __hash__ 裡 sleep(0.1) 也就是一個 100ms 的延遲，去模擬一個 hashable 物件的 hash function 很慢這件事。

然後大概簡單寫兩個 function：

測試一下速度:

就可以看到速度上其實就有一定的差異。

所以在進行這樣的改寫的時候，或許你要考慮一下你的 __hash__ 的 O(1) 到底是多快的 O(1)。

但通常我的經驗是都蠻快的啦，所以別太早擔心這個問題 XD

(題外話) Data Model: __eq__ 與 __hash__

眼尖的人或許會注意到，我在 SlowHashObject 裡同時實作了 __hash__ 與 __eq__ 兩個 method，甚至如果你把 __eq__ 拿掉了，上面的 code 還會產生 KeyError:

其實這跟前面提到的 CPython 的 dict 是以 hash table 的方式實作的，這代表 dict 其實會需要處理 collision 的問題。那是因為雖然 hash function 必須要有：

1. 能把任何 input 轉換成固定大小的值 (CPython 裡會是 Py_ssize_t)
2. 不同的 hash value 必定代表 input 不同
3. input 的微小差異會早成 hash value 顯著的不同
4. 同樣的 input 會有同樣的 hash value

但仔細想想就可以知道，它沒有保證兩個非常不一樣的 input 要有不一樣的 hash value。因此，是很有可能兩個不一樣的 key 算出來的 hash value 是一樣的，那在上面的示意圖可以知道，這兩個 key 會被分配到同樣位置的 slot ，那這個時候到底該把哪個 key 放在那個 slot 就成了問題，也就是發生了 collision，而一個完整個 hash table 的實作是必須能夠處理 collision 的。

那這邊稍微解釋一下，給定我們要插入一組 key 跟 value，首先如果一個 slot 已經被佔用了，hash table 會先把佔用的 slot 裡儲存的 key 去跟現在要插入的 key 做比較。如果相等，代表我們是要用新的 value 去替換掉舊的 value；反之，如果我們發現 key 是不相等的，我們就要透過 probing 去找到下一個空著的 slot (CPython 用的是 random probing)。

所以順著這個思路，我們可以知道，如果在 CPython 裡，一個物件要能被當作 key 來使用的話，它除了要提供 __hash__ method 去產生 hash value 之外，為了支援 collision 的處理，它還必須能支援比較相不相同的功能，也因此這也是會建議如果你實作了 __hash__ 的話，最好也一起實作 __eq__。

這不僅僅是說開發 CPython 要注意而已，在使用很多封裝 data 物件的套件裡，譬如 attrs 跟 dataclass，都會有相關的文件內容在討論這個議題：

• https://www.attrs.org/en/stable/hashing.html#hash-method-generation
• https://docs.python.org/3/library/dataclasses.html#dataclasses.dataclass

可以看一下上面文件有關 unsafe_hash 的敘述。

Python Language Reference 裡對於 __hash__ 也有相關的說明說一個 object 如果要用在 hash collection (諸如 dict, set, frozenset) 就應該要正確實作 __hash__ 與 __eq__ 。

好啦，那這次就先說這些，Happy Python Programming!

References

• https://stackoverflow.com/questions/21595048/how-python-dict-stores-key-value-when-collision-occurs
• https://docs.python.org/3/reference/datamodel.html#object.__hash__
• https://www.attrs.org/en/stable/hashing.html#hash-method-generation
• https://cplusplus.com/reference/map/map/
• https://en.cppreference.com/w/cpp/container/unordered_map