Сортировка Python с ключевой реализацией

Question

Я экспериментировал с сортировкой Python по ключу. Я заинтересован во внутренней работе алгоритма. Это примерно эквивалентно преобразованию Шварца (Decorate-Sort-Undecorate) ?

В частности:

• Ключи спецификации извлекаются только один раз. Можно ли предположить, что это происходит до того, как произойдет какое-либо сравнение?
• Как извлеченные ключи хранятся в памяти? Как кортежи (key, orginal_value) или использует какой-то другой метод.

Я использовал следующую тестовую программу

class Isbn:
    def __init__(self, isbn_num):
        self.isbn_num = isbn_num

    def __lt__(self, other):
        print(f"__lt__ {self.isbn_num} {other.isbn_num}")
        return self.isbn_num < other.isbn_num

    def __repr__(self) -> str:
        return f'Isbn({self.isbn_num})'


class Book:
    def __init__(self, isbn):
        self.isbn = Isbn(isbn)

    def __repr__(self) -> str:
        return f'Book({self.isbn})'

    @property
    def key(self):
        print(f"key {self.isbn}")
        return self.isbn


books = [Book(5), Book(10), Book(6), Book(2)]
books.sort(key=lambda b: b.key)
print(books)

Что дает следующий вывод:

key Isbn(5)
key Isbn(10)
key Isbn(6)
key Isbn(2)
__lt__ 10 5
__lt__ 6 10
__lt__ 6 10
__lt__ 6 5
__lt__ 2 6
__lt__ 2 5
[Book(Isbn(2)), Book(Isbn(5)), Book(Isbn(6)), Book(Isbn(10))]

Answer 1

Говоря конкретно о CPython (доступны другие реализации Python):

Это делает преобразование. В настоящее время он создает C-массив ключей перед тем, как начать сортировку. Это сделано полностью в C - так что это не список Python. Кортежи Python не задействованы.

Это отрывок из (текущего) соответствующего кода C (хотя, конечно, он будет меняться по мере развития CPython), взятый из listobject.c.

key_func является ключевой функцией. saved_ob_size - длина списка. saved_ob_item - массив из исходного списка.

2239 if (keyfunc == NULL) { 
         ...
2243     } 
2244     else { 
         ...    
2256         for (i = 0; i < saved_ob_size ; i++) { 
2257             keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i], 
2258                                                    NULL); 
                 ...
2265             } 
2266         } 

Answer 2

Да. В некоторых случаях Python использует Schwartzian transform. С этой документации .

Программисты Python используют преобразование в тех случаях, когда операция сравнения может быть дорогой.