Многие разработчики Python задаются вопросом, какой метод сортировки списка более эффективен — использование встроенной функции sorted() или задействование метода list.sort(). В данной статье мы попытаемся дать ответ на этот вопрос. Рабочий репозиторий можете найти на GitHub.
Содержание статьи
Потребление памяти при сортировке в Python
Скорость сортировки в Python
Дополнительные заметки о сортировке в Python
Начальной точкой будет список, содержащий 1 000 000 случайных целых чисел и созданный через модуль random:
Python
1
2
3
importrandom
arr=[random.randint(0,50)forrinrange(1_000_000)]
Сгенерированные числа находятся в диапазоне от 0 (включительно) до 50 (включительно).
> Есть вопросы по Python?
На нашем форуме вы можете задать любой вопрос и получить ответ от всего нашего сообщества!
Сначала сравним, сколько памяти потребляет каждая из функций. Для отслеживания максимального использования памяти, используем встроенный модуль resource. Так как данный модуль позволяет отслеживать использование памяти для одного потока, мы запускаем сортировку списка в отдельном потоке. Также можно использовать FunctionSniffingClass, включенный в репозитории.
# Уберите знак комментария, если вы хотите увидеть результат
# print(mythread.results)
break;
print(" MAX Memory Usage:",round(max_memory/(2**20),3),"MB")
Для встроенных функций мы создаем две функции-обертки, чтобы была возможность передавать их в качестве аргументов в FunctionSniffingClass. Мы могли бы передать встроенную отсортированную функцию непосредственно в FunctionSniffingClass, но нам требуются одинаковые шансы для обеих. По этой причине мы также создадим для нее функцию-обертку. Кроме того, реализован простой синтаксический парсинг аргументов командной строки, позволяющий использовать его как можно проще из командной строки.
Интересно, как все работает? Посмотрим!
Shell
1
2
3
4
5
6
7
8
9
10
11
$python memory_measurement/main.pysort
Calling the Target Function...
FunctionCall Complete
MAX Memory Usage:23.371MB
$python memory_measurement/main.pysorted
Calling the Target Function...
FunctionCall Complete
MAX Memory Usage:30.879MB
Как видите, функция sorted() потребляет примерно на 32% больше памяти, чем метод list.sort(). Этого следовало ожидать, так как последний вариант изменяет список на месте, тогда как первый всегда создают отдельный список.
Скорость сортировки в Python
Для измерения времени выполнения обеих функций-оберток используем сторонний модуль boxx. Следующий код показывает, как можно использовать функцию timeit() для измерения времени выполнения обеих функций.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# speed/main.py
importrandom
fromboxx importtimeit
deflist_sort(arr):
returnarr.sort()
defsorted_builtin(arr):
returnsorted(arr)
defmain():
arr=[random.randint(0,50)forrinrange(1_000_000)]
withtimeit(name="sorted(list)"):
sorted_builtin(arr)
withtimeit(name="list.sort()"):
list_sort(arr)
if__name__=="__main__":
main()
На заметку: Обратите внимание, что сначала лучше запустить функцию sorted_builtin(), так как метод list.sort() сразу сортирует список, поэтому функции sorted() больше ничего не нужно сортировать.
Указанный выше код выводит следующий результат:
Shell
1
2
3
$python main.py
"sorted(list)"spend time:0.1104379
"list.sort()"spend time:0.0956471
Как видите, метод list.sort() немного быстрее, чем функция sorted(). Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:
Python
1
2
3
4
5
6
7
8
9
10
11
>>>importdis
>>>dis.dis(list_sort)
120LOAD_FAST0(arr)
2LOAD_METHOD0(sort)
4CALL_METHOD0
6RETURN_VALUE
>>>dis.dis(sorted_builtin)
160LOAD_GLOBAL0(sorted)
2LOAD_FAST0(arr)
4CALL_FUNCTION1
6RETURN_VALUE
Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция list_sort() сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция sorted_builtin() сначала загружает встроенную функцию sorted(), а за ней следует список и вызов загруженной функции со списком в качестве аргумента.
Кроме того, оба варианта используют одинаковый алгоритм сортировки Timesort. В обоих используется одинаковый алгоритм сортировки, байтовый код обоих также практически идентичен.
Почему же временные результаты отличаются?
Можно предположить, что в то время как list.sort() может работать с известным размером и менять элементы внутри данного размера, sorted() должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через sorted(). На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:
Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему list.sort() на 13% быстрее, чем sorted().
Однако, в действительности все не совсем так. Один из разработчиков CPython, Ник Коглан, упоминал в Твиттере, что размер списка результата известен. Фактически, происходит следующее:
Данная теория не верна — sorted знает, насколько в этом случае велики входные данные, поэтому он может предварительно распределить вывод. Чего нельзя избежать, так это дополнительного копирования данных, необходимого для создания нового списка. Если вы измерите "arr2 = arr.copy(); arr2.sort()", результат должен быть сопоставим с sorted(arr).
Он также утверждает, что это может быть не вполне очевидным. Особенно, если вы не акцентируете на этом внимание и не замечаете этого в имплементации.
«Идея изменения размера была достойным предположением — даже при чтении исходного кода трюк с предварительным распределением скрыт в реализации list.extend, и поэтому его легко пропустить, если вы еще не знаете, что он там есть :)»
Имплементация приводит к разнице во времени выполнения, поскольку создание копии списка занимает некоторое время.
Дополнительные заметки о сортировке в Python
Перед завершением статьи давайте рассмотрим, что говорит документация Python о сортировке:
Вы также можете использовать метод list.sort(). Он сразу изменяет список (и возвращает None во избежание неразберихи). Обычно это не так удобно, как sorted() — однако, если вам не нужен оригинальный список, это более эффективно.
Как видите, в официальной документации утверждается, что уже и так было доказано: list.sort() немного эффективнее. Кроме того, в документации говорится о том, что зачастую sorted() намного удобнее.
Может возникнуть вопрос касательно того, являются ли обе техники стабильные. К счастью, в документации есть ответ и на это:
Результаты сортировки остаются стабильными. Это значит, что если у нескольких записей одинаковый ключ, будет сохранен их оригинальный порядок.
Также верно при использовании реверсивного параметра или применении реверсивной функции дважды.
Заключение
После проведения небольшого анализа мы доказали, что list.sort() немного быстрее sorted() и потребляет на 24% меньше памяти. Однако, стоит иметь в виду, что list.sort() имплементируется только для списков, в то время как sorted() принимает любые итерации. Кроме того, при использовании list.sort() вы потеряете оригинальный список.