Python中多键排序的效率

Question

我有一个字符串列表，我想按 Python 3.6 中的两个自定义键函数对其进行排序。将多排序方法（按较小键排序，然后按主键排序）与多键方法（将键作为元组(major_key, lesser_key)）进行比较，我可以看到后者比前者慢 2 倍以上，这是惊讶，因为我认为它们是等价的。我想了解为什么会这样。

import random
from time import time

largest = 1000000
length = 10000000
start = time()
lst = [str(x) for x in random.choices(range(largest), k=length)]
t0 = time() - start

start = time()
tmp = sorted(lst, key=lambda x: x[::2])
l1 = sorted(tmp, key=lambda x: ''.join(sorted(x)))
t1 = time() - start

start = time()
l2 = sorted(lst, key=lambda x: (''.join(sorted(x)), x[::2]))
t2 = time() - start

print(f'prepare={t0} multisort={t1} multikey={t2} slowdown={t2/t1}')

assert l1 == l2

Answer 1

这是第三种计时方法：

start = time()
l3 = sorted(lst, key=lambda x: (''.join(sorted(x)) + "/" + x[::2]))
t3 = time() - start

并将最后一行扩展为

assert l1 == l2 == l3

这使用单个字符串作为键，但将您视为“主”和“辅助”键的两个字符串键组合起来。注意：

>>> chr(ord("0") - 1)
'/'

这就是为什么这两个键可以组合起来 - 它们由一个 ASCII 字符分隔，该字符比较“小于”任何 ASCII 数字（当然，这完全特定于您所使用的精确类型的键）。

使用您发布的精确程序，这通常比我快一点。multisort()

准备=3.628943920135498 multisort=15.646344423294067 multikey=34.255955934524536 减速=2.1893903782103075 onekey=15.11461067199707

我相信现代 CPython 发行版的末尾简要解释了“为什么”的主要原因Objects/listsort.txt：

如上所述，即使是最简单的 Python 比较也会触发大量 C 级指针取消引用、条件和函数调用。通过预扫描数据以确定数据在类型方面是否同质，可以部分缓解这种情况。如果是这样，有时可以用较快的特定类型比较来代替较慢的通用 PyObject_RichCompareBool。

当使用单个字符串作为键时，此预排序扫描会推断列表中的所有键实际上都是字符串，因此可以跳过确定要调用哪个比较函数的所有运行时费用：排序始终可以调用特定于字符串的比较函数而不是通用的（而且成本要高得多）PyObject_RichCompareBool。

multisort()也受益于这种优化。

但multikey()并不多。预排序扫描发现所有键都是元组，但元组比较函数本身无法假设有关元组元素类型的任何信息：它必须在PyObject_RichCompareBool每次调用时都进行假设。（注意：正如评论中提到的，它并不是那么简单：仍然利用键都是元组来进行一些优化，但它并不总是有效，而且充其量也不太有效 - 请参阅下一节以获得更清晰的证据。）

重点

测试用例中发生了很多事情，这导致需要付出更大的努力来解释越来越小的区别。

因此，为了查看类型同质性优化的效果，让我们将事情简化很多：key根本没有任何功能。就像这样：

from random import random, seed
from time import time

length = 10000000
seed(1234567891)
xs = [random() for _ in range(length)]

ys = xs[:]
start = time()
ys.sort()
e1 = time() - start

ys = [(x,) for x in xs]
start = time()
ys.sort()
e2 = time() - start

ys = [[x] for x in xs]
start = time()
ys.sort()
e3 = time() - start
print(e1, e2, e3)

这是我的盒子上的典型输出：

3.1991195678710938 12.756590843200684 26.31903386116028

所以直接对浮点数进行排序是迄今为止最快的。将浮点数粘贴在 1 元组中已经非常具有破坏性，但优化仍然带来了非常显着的好处：将浮点数粘贴在单例列表中再次需要两倍多的时间。在最后一种情况下（并且仅在最后一种情况下），PyObject_RichCompareBool总是被调用。