爲什麼DSU裝飾排序undecorate比提供比較功能更快？

Question

Pythonistas喜歡談論一個叫DSU技術：

假設我要排序的第三個字段的int值的列表：

# Decorate 
decorated = [(int(item[2]), item) for item in items] 
# Sort 
decorated.sort() 
# Undecorate 
items = [item[1] for item in decorated] 

據說，這種方法比更有效：

def compare(item1, item2): 
    return cmp(int(item1[2]), int(item2[2])) 
items.sort(compare) 

爲什麼DSU更快？是什麼讓sort（）沒有比較特殊？

Answer 1

這取決於如何昂貴的排序從價值的項目轉換的是。在這種情況下，轉換採用第三項的int。

隨着比較方法中，轉換髮生每個項目多次。使用裝飾/排序/未整理方法，轉換隻會發生一次每個項目。如果關鍵功能很貴，那麼每個項目只調用一次應該更有效率。

請注意，你可以做裝飾/排序/去除裝飾方法內置插件：分揀機需要比較每次

items.sort(key=lambda item: int(item[2])) 

Answer 2

的cmp函數必須在排序過程中反覆調用，一旦兩個對象。由於在排序過程中可能必須將相同的對象與其他對象進行比較，因此可能會爲每個對象多次調用cmp。另一方面，使用DSU只需要爲列表中的每個項目執行一次裝飾代碼，而不管進行了多少次比較。

在Python的最新版本中，您可以使用key參數sort來代替：items.sort(key=lambda item: item[2])。這有效地爲您做DSU。