Python 排序的技巧 May 1st, 2009Goto commentsLeave a comment 用 Python 排序時相較於 C、Java 多了效率議題。

Python 排序的技巧
May 1st, 2009Goto commentsLeave a comment
用 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。物換星移，忽然有淡淡的懷舊感傷。

歷史上的今天
初始化 graph 的教訓，不熟的語法別亂用 - 2008