sorted(key=lambda x:) 是如何在后台实现的？

Question

一个例子：

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

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

首先计算每个名称的所有键，并以某种方式将键和名称绑定在一起，并对它们进行排序。 p
每次比较发生时计算密钥

第一种方法的问题是它必须定义另一个数据结构来绑定键和数据。第二种方式的问题是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;

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

sorted(key=lambda x:) 是如何在后台实现的？

How is sorted(key=lambda x:) implemented behind the scene?

python

sorting

lambda

python-internals