Как отсортировано (key = lambda x :) реализовано за сценой?

Question

Пример:

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

Я знаю key используется для сравнения различных имен, но он может иметь две разные реализации:

1. Сначала вычислим все ключи для каждого имени, и привязать ключ и имя вместе в некотором роде и сортировать их. Р
2. Compute ключ каждый раз, когда происходит сравнение

проблема с первым подходом является то, что он должен определить другую структуру данных для привязки ключа и данных. Проблема со вторым подходом заключается в том, что ключ может быть рассчитан несколько раз, то есть name.split()[-1].lower() будет выполняться много раз, что очень трудоемко.

Мне просто интересно, каким образом реализован Python sorted().

Answer 1

Ключевая функция выполняется только один раз за значение, для производства пары (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 в тандеме.