list.sort() VS sorted(list) - Чем сортировать список в Python?

Многие разработчики Python задаются вопросом, какой метод сортировки списка более эффективен — использование встроенной функции sorted() или задействование метода list.sort(). В данной статье мы попытаемся дать ответ на этот вопрос. Рабочий репозиторий можете найти на GitHub.

Содержание статьи

Потребление памяти при сортировке в Python
Скорость сортировки в Python
Дополнительные заметки о сортировке в Python

Начальной точкой будет список, содержащий 1 000 000 случайных целых чисел и созданный через модуль random:

import random

arr = [random.randint(0, 50) for r in range(1_000_000)]

import random

arr = [random.randint(0, 50) for r in range(1_000_000)]

Сгенерированные числа находятся в диапазоне от 0 (включительно) до 50 (включительно).

Есть вопросы по Python?

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

Python Форум Помощи

Telegram Чат & Канал

Вступите в наш дружный чат по Python и начните общение с единомышленниками! Станьте частью большого сообщества!

Чат

Канал

Паблик VK

Одно из самых больших сообществ по Python в социальной сети ВК. Видео уроки и книги для вас!

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

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

Рассмотрим подробнее наш Python скрипт:

# 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")

# 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, но нам требуются одинаковые шансы для обеих. По этой причине мы также создадим для нее функцию-обертку. Кроме того, реализован простой синтаксический парсинг аргументов командной строки, позволяющий использовать его как можно проще из командной строки.

Интересно, как все работает? Посмотрим!

$ 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

$ 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() для измерения времени выполнения обеих функций.

# 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()

# 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() больше ничего не нужно сортировать.

Указанный выше код выводит следующий результат:

$ python main.py
"sorted(list)" spend time: 0.1104379
"list.sort()" spend time: 0.0956471

$ python main.py

"sorted(list)" spend time: 0.1104379

"list.sort()" spend time: 0.0956471

Как видите, метод list.sort() немного быстрее, чем функция sorted(). Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:

>>> 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

>>> 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, Ник Коглан, упоминал в Твиттере, что размер списка результата известен. Фактически, происходит следующее:

new_array = arr.copy()
arr.sort()

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

Vasile Buldumac

Являюсь администратором нескольких порталов по обучению языков программирования Python, Golang и Kotlin. В составе небольшой команды единомышленников, мы занимаемся популяризацией языков программирования на русскоязычную аудиторию. Большая часть статей была адаптирована нами на русский язык и распространяется бесплатно.

E-mail: vasile.buldumac@ati.utm.md

Образование
Universitatea Tehnică a Moldovei (utm.md)

2014 — 2018 Технический Университет Молдовы, ИТ-Инженер. Тема дипломной работы «Автоматизация покупки и продажи криптовалюты используя технический анализ»
2018 — 2020 Технический Университет Молдовы, Магистр, Магистерская диссертация «Идентификация человека в киберпространстве по фотографии лица»