28.08.2024 в 00:51

Как оптимизация сравнения ускоряет сортировку в Python

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

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

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

Функции sorted() и list.sort() были оптимизированы для часто встречающихся сценариев, что привело к приросту скорости от 40 до 75%. (Эти изменения были реализованы Эллиотом Гороховским в рамках bpo-28685)

Введение в сортировку в Python

Отсортировать список в Python можно двумя вариантами:

Метод списка: list.sort(*, key=None, reverse=False), который сортирует заданный список на месте
Встроенная функция: sorted(iterable , / , * , key=None , reverse=False), которая возвращает отсортированный список без изменения своего аргумента.

Если вам нужно отсортировать любой другой встроенный итерируемый объект, вы можете использовать только sorted независимо от типа итерируемого объекта или генератора, переданного в качестве параметра.

sorted всегда возвращает список, поскольку он используется внутри list.sort.

Вот примерный эквивалент sorted реализации CPython на языке C, переписанный на чистом Python:

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

Как Python ускоряет сортировку

Как сказано во внутренней документации Python по сортировке: иногда можно заменить более быстрые сравнения, специфичные для определенного типа, на более медленные, общие PyObject_RichCompareBool.

И вкратце эту оптимизацию можно описать следующим образом: когда список однороден, Python использует функцию сравнения, специфичную для типа

Что такое однородный список?

Однородный список — это список, содержащий элементы только одного типа.

Например:

homogeneous = [1, 2, 3, 4]

Пример неоднородного списка:

heterogeneous = [1, "2", (3, ), {'4': 4}]

В официальной документации по Python говорится: cписки изменяемы, а их элементы обычно однородны и доступны путем итерации по списку.

Замечание о кортежах

В том же руководстве говорится: кортежи неизменяемы и обычно содержат неоднородную последовательность элементов.

Так что если вы когда-нибудь задумывались, когда использовать кортеж, а когда список, вот практическое правило: если элементы одного типа, используйте список, в противном случае используйте кортеж.

Подождите, а что насчет массивов?

Python реализует объект-контейнер однородного массива для числовых значений.

Однако, начиная с версии Python 3.12, массивы не реализуют собственный sort метод.

Единственный способ отсортировать их — использовать sorted, который внутренне создает список из массива, стирая в процессе любую информацию, связанную с типом.

Причины использования функции сравнения, специфичной для типа?

Сравнения в Python требуют больших затрат, поскольку Python выполняет различные проверки перед выполнением любого фактического сравнения.

Вот упрощенное объяснение того, что происходит под капотом при сравнении двух значений в Python:

Python проверяет, что значения, переданные в функцию сравнения, не являются NULL
Если значения имеют разные типы, но правый операнд является подтипом левого, Python использует функцию сравнения правого операнда, но в обратном порядке (например, он будет использовать < for >).
Если значения относятся к одному и тому же типу или к разным типам, но ни один из них не является подтипом другого:Python сначала попробует функцию сравнения левого операндаЕсли это не удается, то попробуется функция сравнения правого операнда, но в обратном порядке.Если и это не удается, а сравнение выполняется на равенство или неравенство, будет возвращено сравнение идентичности (True для значений, которые ссылаются на один и тот же объект в памяти)В противном случае он повышает TypeError

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

Например, при сравнении строк Python проверит, занимают ли символы строки более одного байта памяти, а сравнение чисел с плавающей точкой будет сравнивать пару float и float и int по-разному.

Более подробное объяснение и схему можно найти здесь: Добавление оптимизации сортировки с учетом данных в CPython.

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

Предварительная проверка типов элементов списка

Не существует волшебного способа узнать, все ли элементы списка имеют один и тот же тип, кроме как перебрать список и проверить каждый элемент.

Python делает почти то же самое — проверяет типы ключей сортировки, сгенерированных функцией key, переданной list.sort в sorted качестве параметра

Составление списка ключей

Если указана функция key, Python использует ее для построения списка ключей, в противном случае list в качестве ключей сортировки используются собственные значения.

В упрощенном виде построение ключей можно выразить следующим кодом Python.

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

Обратите внимание, что keys внутри CPython используется массив C ссылок на объекты CPython, а не список Python.

После создания ключей Python проверяет их типы.

Проверка типа ключа

При проверке типов ключей алгоритм сортировки Python пытается определить, являются ли все элементы в массиве ключей либо str, int, float либо tuple, либо просто одного типа, с некоторыми ограничениями для базовых типов.

Стоит отметить, что проверка типов ключей добавляет некоторую дополнительную работу заранее. Python делает это, потому что это обычно окупается, делая фактическую сортировку быстрее, особенно для длинных списков.

int ограничения

int не должно быть большим числом

На практике это означает, что для работы этой оптимизации целое число должно быть меньше 2^30 - 1 (это может варьироваться в зависимости от платформы).

В качестве примечания вот замечательная статья, в которой объясняется, как Python обрабатывает большие целые числа: # Как Python реализует сверхдлинные целые числа?

str ограничения

Все символы строки должны занимать менее 1 байта памяти, то есть они должны быть представлены целыми значениями в диапазоне 0-255.

На практике это означает, что строки должны состоять только из латинских символов, пробелов и некоторых специальных символов, встречающихся в таблице ASCII.

float ограничения

Для работы этой оптимизации нет никаких ограничений на плавающие числа.

tuple ограничения

Проверяется только тип первого элемента.
Этот элемент сам по себе не должен быть кортежем.
Если все кортежи имеют один и тот же тип первого элемента, к ним применяется оптимизация сравнения.
Все остальные элементы сравниваются как обычно.

Применение

Упоминание этих знаний может стать приятным штрихом на собеседовании на должность разработчика Python.

Что касается фактической разработки кода, понимание этой оптимизации может помочь вам улучшить производительность сортировки.

Оптимизируйте, выбирая тип значений с умом

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

Поэтому, когда придет время оптимизировать, преобразуйте список таким образом

floats_and_int = [1.0, -1.0, -0.5, 3]

В список, который выглядит так

just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now

Это сможет улучшить производительность.

Оптимизация с использованием ключей для списков объектов

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

При сортировке объектов пользовательских классов Python использует определенные вами методы сравнения, такие как __lt__ (меньше чем) или __gt__ (больше чем).

Однако оптимизация, специфичная для типа, не применяется к пользовательским классам.
Python всегда будет использовать общий метод сравнения для этих объектов.

Вот пример:

class MyClass:
    def __init__(self, value): 
        self.value = value 

    def __lt__(self, other): 
        return self.value < other.value 

my_list = [MyClass(3), MyClass(1), MyClass(2)] 
sorted_list = sorted(my_list)

В этом случае Python будет использовать __lt__ метод для сравнений, но не получит выгоды от оптимизации, специфичной для типа. Сортировка по-прежнему будет работать правильно, но она может быть не такой быстрой, как сортировка встроенных типов.

Если при сортировке пользовательских объектов производительность имеет решающее значение, рассмотрите возможность использования ключевой функции, которая возвращает встроенный тип:

sorted_list = sorted(my_list, key=lambda x: x.value)

Послесловие

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

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

Рассмотрим сценарий, в котором сортировка основана на временных метках: использование однородного списка целых чисел (временных меток Unix) вместо объектов datetime может эффективно использовать эту оптимизацию.

Однако важно помнить, что читаемость и удобство поддержки кода должны иметь приоритет над подобными оптимизациями.

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

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

Источник:

#Python

Войти на сайт