如何在场景后面实现排序(key = lambda x :)？

Question

一个例子:

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

我知道key用于比较不同的名称,但它可以有两种不同的实现:

1. 首先计算每个名称的所有键,然后以某种方式将键和名称绑定在一起,然后对它们进行排序.p
2. 每次进行比较时计算密钥

第一种方法的问题是它必须定义另一个数据结构来绑定密钥和数据.第二种方法的问题是密钥可能被多次计算,也就是说,name.split()[-1].lower()将被执行多次,这非常耗时.

我只是想知道Python实现的方式sorted().

Answer 1

关键功能每个值只执行一次,以产生一(keyvalue, value)对; 然后将其用于排序,稍后将按排序顺序返回值.这有时被称为Schwartzian变换.

你可以自己测试一下; 你可以计算调用函数的频率,例如:

>>> 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.