为什么DSU decorate-sort-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第三项的.

使用比较方法,每个项目转换多次.使用decorate/sort/undecorate方法,每个项目只进行一次转换.如果关键功能很昂贵,那么每个项目只调用一次应该更有效.

请注意,您可以使用内置函数执行decorate/sort/undecorate方法:

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

Answer 2

在排序过程中必须重复调用该cmp函数，每次排序器需要比较两个对象时调用一次。由于在排序过程中同一对象可能必须与多个其他对象进行比较，因此cmp每个对象可能会被多次调用。另一方面，使用 DSU 只需要为列表中的每个项目执行一次装饰代码，无论进行多少次比较。

在最新版本的 Python 中，您可以使用key参数来sort代替：items.sort(key=lambda item: item[2])。这可以有效地为您完成 DSU。