Python中多键排序的效率

我有一个字符串列表，我想按 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

这是第三种计时方法：

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 数字（当然，这完全特定于您所使用的精确类型的键）。

这通常是一点faster than multisort()对我来说，使用您发布的精确程序。

准备=3.628943920135498 多重排序=15.646344423294067 多键=34.255955934524536 减速=2.1893903782103075 一键=15.11461067199707

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

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

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

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

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

Focus

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

因此，为了看看类型同质性优化的效果，让我们把事情简化很多：不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总是被调用。