一个例子:
names = ["George Washington", "John Adams", "Thomas Jefferson", "James Madison"]
sorted(names, key=lambda name: name.split()[-1].lower())
我知道key
用于比较不同的名称,但它可以有两种不同的实现:
- 首先计算每个名称的所有键,然后以某种方式将键和名称绑定(bind)在一起,然后对它们进行排序。
- 每次比较时计算 key
第一种方法的问题在于它必须定义另一个数据结构来绑定(bind)键和数据。第二种方式的问题是key可能会被计算多次,即name.split()[-1].lower()
会被执行多次,非常耗时-消耗。
我只是想知道Python以什么方式实现sorted()
。
最佳答案
每个值只执行一次 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
中的元素。
关于python - 如何排序(key=lambda x :) implemented behind the scene?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41078689/