python - 如何排序(key=lambda x :) implemented behind the scene?

Question

一个例子:

names = ["George Washington", "John Adams", "Thomas Jefferson", "James Madison"]
sorted(names, key=lambda name: name.split()[-1].lower())

我知道key是用来比较不同名字的，但是它可以有两种不同的实现方式:

1. 首先计算每个名称的所有键，并以某种方式将键和名称绑定(bind)在一起，并对它们进行排序。
2. 每次比较时计算 key

第一种方法的问题是它必须定义另一个数据结构来绑定(bind)键和数据。第二种方式的问题是key可能会计算多次，即name.split()[-1].lower()会执行多次，非常耗时-消费。

我只是想知道 Python 以何种方式实现 sorted()。

Answer 1

key 函数只为每个值执行一次一次，以生成一个(keyvalue, value) 对；然后将其用于排序，稍后仅按排序顺序返回值。这有时称为 Schwartzian transform .

你可以自己测试一下；您可以计算该函数被调用的频率，例如:

>>> def keyfunc(value):
...     keyfunc.count += 1
...     return value
...
>>> keyfunc.count = 0
>>> sorted([0, 8, 1, 6, 4, 5, 3, 7, 9, 2], key=keyfunc)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> keyfunc.count
10

或者您可以收集所有传入的值；您会看到它们遵循原始输入顺序:

>>> def keyfunc(value):
...     keyfunc.arguments.append(value)
...     return value
...
>>> keyfunc.arguments = []
>>> sorted([0, 8, 1, 6, 4, 5, 3, 7, 9, 2], key=keyfunc)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> keyfunc.arguments
[0, 8, 1, 6, 4, 5, 3, 7, 9, 2]

如果想看CPython源码，相关函数调用listsort() ，并且 keyfunc 用于以下循环(saved_ob_item 是输入数组)，它在 排序发生之前执行:

for (i = 0; i < saved_ob_size ; i++) {
    keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],
                                           NULL);
    if (keys[i] == NULL) {
        for (i=i-1 ; i>=0 ; i--)
            Py_DECREF(keys[i]);
        if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
            PyMem_FREE(keys);
        goto keyfunc_fail;
    }
}

lo.keys = keys;
lo.values = saved_ob_item;

所以最后，您有两个数组，一个带有键，另一个带有原始值。所有排序操作并行作用于两个数组，对 lo.keys 中的值进行排序，同时移动 lo.values 中的元素。