python - 为什么 DSU decorate-sort-undecorate 比提供比较函数更快？

Question

Python 爱好者喜欢谈论一种称为 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 方法，每个项目只发生一次转换。如果键函数开销很大，那么每个项目只调用一次应该更有效。

请注意，您可以使用内置函数执行装饰/排序/取消装饰方法:

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