Сортировка списков в Python: list.sort() против sorted(list)
Сортировка списков в Python: list.sort() против sorted(list)
Содержание статьи
- Потребление памяти при сортировке в Python
- Скорость сортировки в Python
- Дополнительные заметки о сортировке в Python
Python
1
2
3
import random
arr = [random.randint(0, 50) for r in range(1_000_000)]
Сгенерированные числа находятся в диапазоне от 0 (включительно) до 50 (включительно).
Есть вопросы по Python?
На нашем форуме вы можете задать любой вопрос и получить ответ от всего нашего сообщества!
Telegram Чат & Канал
Вступите в наш дружный чат по Python и начните общение с единомышленниками! Станьте частью большого сообщества!
Паблик VK
Одно из самых больших сообществ по Python в социальной сети ВК. Видео уроки и книги для вас!
Потребление памяти при сортировке в Python
Рассмотрим подробнее наш Python скрипт:
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# memory_measurement/main.py
import random
import resource
import sys
import time
from sniffing import FunctionSniffingClass
def list_sort(arr):
return arr.sort()
def sorted_builtin(arr):
return sorted(arr)
if __name__ == "__main__":
if len(sys.argv) != 2:
sys.exit("Please run: python (sort|sorted)")
elif sys.argv[1] == "sorted":
func = sorted_builtin
elif sys.argv[1] == "sort":
func = list_sort
else:
sys.exit("Please run: python (sort|sorted)")
# код теста Lib
arr = [random.randint(0, 50) for r in range(1_000_000)]
mythread = FunctionSniffingClass(func, arr)
mythread.start()
used_mem = 0
max_memory = 0
memory_usage_refresh = .005 # Секунды
while(1):
time.sleep(memory_usage_refresh)
used_mem = (resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)
if used_mem > max_memory:
max_memory = used_mem
# Проверяет, завершен ли вызов функции
if mythread.isShutdown():
# Уберите знак комментария, если вы хотите увидеть результат
# print(mythread.results)
break;
print("\nMAX 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.py sort
Calling the Target Function...
Function Call Complete
MAX Memory Usage: 23.371 MB
$ python memory_measurement/main.py sorted
Calling the Target Function...
Function Call Complete
MAX Memory Usage: 30.879 MB
Как видите, функция 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
import random
from boxx import timeit
def list_sort(arr):
return arr.sort()
def sorted_builtin(arr):
return sorted(arr)
def main():
arr = [random.randint(0, 50) for r in range(1_000_000)]
with timeit(name="sorted(list)"):
sorted_builtin(arr)
with timeit(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
>>> import dis
>>> dis.dis(list_sort)
12 0 LOAD_FAST 0 (arr)
2 LOAD_METHOD 0 (sort)
4 CALL_METHOD 0
6 RETURN_VALUE
>>> dis.dis(sorted_builtin)
16 0 LOAD_GLOBAL 0 (sorted)
2 LOAD_FAST 0 (arr)
4 CALL_FUNCTION 1
6 RETURN_VALUE
Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция list_sort() сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция sorted_builtin() сначала загружает встроенную функцию sorted(), а за ней следует список и вызов загруженной функции со списком в качестве аргумента.
Кроме того, оба варианта используют одинаковый алгоритм сортировки Timesort. В обоих используется одинаковый алгоритм сортировки, байтовый код обоих также практически идентичен.
Почему же временные результаты отличаются?
Можно предположить, что в то время как list.sort() может работать с известным размером и менять элементы внутри данного размера, sorted() должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через sorted(). На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:
Паттерн роста: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
— CPython: Objects/listobject.c
Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему list.sort() на 13% быстрее, чем sorted().
Однако, в действительности все не совсем так. Один из разработчиков CPython, Ник Коглан, упоминал в Твиттере, что размер списка результата известен. Фактически, происходит следующее:
Python
1
2
new_array = arr.copy()
arr.sort()
Из Твиттера Ника Коглана:
Данная теория не верна — 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() вы потеряете оригинальный список.