Сортировка списков в Python: list.sort() против sorted(list)

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Многие разработчики 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?

На нашем форуме вы можете задать любой вопрос и получить ответ от всего нашего сообщества!

Открыть форум

> Чат и Паблик Программистов

Присоединяйтесь к нашему чату в Телеграм и подпишитесь на наш паблик в ВК.

Потребление памяти при сортировке в Python

Сначала сравним, сколько памяти потребляет каждая из функций. Для отслеживания максимального использования памяти, используем встроенный модуль resource. Так как данный модуль позволяет отслеживать использование памяти для одного потока, мы запускаем сортировку списка в отдельном потоке. Также можно использовать FunctionSniffingClass, включенный в репозитории.

Рассмотрим подробнее наш 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

importrandom

importresource

importsys

importtime

fromsniffing importFunctionSniffingClass

deflist_sort(arr):

returnarr.sort()

defsorted_builtin(arr):

returnsorted(arr)

if__name__=="__main__":

iflen(sys.argv)!=2:

sys.exit("Please run: python (sort|sorted)")

elifsys.argv[1]=="sorted":

func=sorted_builtin

elifsys.argv[1]=="sort":

func=list_sort

else:

sys.exit("Please run: python (sort|sorted)")

# код теста Lib

arr=[random.randint(0,50)forrinrange(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)

ifused_mem>max_memory:

max_memory=used_mem

# Проверяет, завершен ли вызов функции

ifmythread.isShutdown():

# Уберите знак комментария, если вы хотите увидеть результат

# 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, можно найти следующий комментарий об изменении размера списка объектов:

Паттерн роста: 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() вы потеряете оригинальный список.


Источник: python-scripts.com

Комментарии: