Python 排序的技巧

用 Python 排序時相較於 C、Java 多了效率議題。由於 Python 內建函數 (built-in function) 是用 C 實作的，排序時盡可能用內建函數效率會快上不少，詳細的數據比較可以參見 Python Cookbook，這篇做個簡單的整理。

背景知識

本篇需要 list comprehension 和 map 的基本觀念，若不清楚的話可以先了解它們再往下看。

排序 list 和 dict

先來看程式碼：

1 2 3 4 5 6 7 8 9 10 11 12 13

d = { 'a': 2, 'b': 1 } # return keys ordered by key print sorted(d) # ['a', 'b'] # return values ordered by key print map(d.get, sorted(d)) # [2, 1] # return keys ordered by value print sorted(d, key=d.get) # ['b', 'a'] # return values ordered by value print sorted(d.values()) # [1, 2] # return (key, value) pairs order by key print sorted(d.items()) # [('a', 2), ('b', 1)] # return (key, value) pairs order by value print sorted(d.items(), key=operator.itemgetter(1)) # [('b', 1), ('a', 2)]

上面的程式列出所有排序 dict ( 在一些語言裡稱為 hash table) 的方法，這裡用到幾個技巧，分別說明一下。

return values ordered by key：Python 的 method call 其實和 function call 差不多，obj.func(x) 相當於傳回 func(obj, x)，所以 d.get 一樣可以傳進 map 裡，結果是會取回 d 的 value。關於 function 和 method 的說明，可以參考《理解 python 的 method 和 function 兼谈 descriptor 》

return keys ordered by value：同上的技巧，注意參數 key 有做最佳化處理，使得 d 的每個元素只會呼叫一次 d.get ( 而不是比較次數 O(N*logN) 次 )，不用擔心取 key 的函式會被重覆執行。

return (key, value) pairs order by value：這部份的 code 和排序 list 一樣，關鍵在於用了 operator.itemgetter，它的文件說明摘錄如下：

Return a callable object that fetches the given item(s) from its operand.
After, f=itemgetter(2), the call f(r) returns r[2].

以程式碼來表示的話，類似於這麼寫：

1 2	def itemgetter(n): return lambda r: r[n]

只要資料轉成 list of lists 的形式，就可以用 operator.itemgetter 處理。轉成 list of lists 的時間和資料數量成正比，相對於套入用 python 寫的 comparator 來說，快上不少。module operator 裡有許多好用的函式，在套用 map、max、sort 等內建函式時，可以配合使用，一來不用自己重寫小函式，二來內建函式用 C 實作，速度快上許多。

Decorate-Sort-Undecorate (DSU)

若要比較的方式比較複雜，像是希望有 stable sort，或是比較的 key 不只一個，可以套用 DSU 的解法。這裡以 stable sort 為例 (程式引用自 Python Cookbook)：

1 2 3 4

def stable_sorted_copy(alist, _indices=xrange(sys.maxint)): decorated = zip(alist, _indices) decorated.sort() return [ item for item, index in decorated ]

DSU 的關鍵在於先把每筆資料轉成 [key1, key2, ..., original item] 的形式，如此一來內建的 sort 就會依 key1, key2, … 的順序排序，排好後再取回 original item。同樣的，排序 object 依欄位值或 method 傳回值，都可以套用 DSU。而 stable sort 的情況比較不同，是將資料轉成 [original item, original position ]，排序後再取回 original item。

附帶一提，xrange 是 generator，使用 generator 好處可以參見 PEP 289: Generator Expressions。

參考資料

• Python Cookbook 第二章 Searching and Sorting：有詳細的例子一步步解釋各種寫法，並分析優劣。
• Sorting Mini-HOW TO - Sorting by keys：這篇比 Cookbook 的介紹精簡許多。
• Functional Programming HOWTO：這篇清楚地說明許多重要的基本觀念。

備註

發表這篇後，才發現去年的今天我在寫 Ruby。物換星移，忽然有淡淡的懷舊感傷。