Сортировка данных — важная составляющая разработки приложения. Поэтому рано или поздно каждому разработчику приходится задумываться о том, как это реализовать наиболее эффективным способом. Python имеет несколько функций, позволяющих реализовать этот функционал. В частности, это функции sorted и list.sort(). Сегодня необходимо более подробно разобраться в особенностях применения каждой из этих функций, а также в том, какая из них действительно лучше.
У многих создателей приложений на Python появляется вопрос, какой метод сортировки списка дает лучше результат— применение функции sorted(), которая является встроенной в этом языке программирования либо использование метода list.sort(). Сегодня мы попробуем ответить на такой популярный вопрос.
Давайте сперва будем использовать список, в который включен 1 миллион случайных целых чисел, для создания которого мы используем модуль random. И на этом примере попробуем продемонстрировать работу каждой из этих функций.
import random arr = [random.randint(0, 50) for r in range(1_000_000)]
Как следствие, те числа, которые нами генерируются, находятся в пределах от 0 (включительно) до 50 (также включительно). Наше приложение сделано именно таким образом.
Потребление памяти при сортировке
Сперва давайте попробуем сравнить, сколько именно памяти отводится для под нужды каждой функции по отдельности. Для понимания того, какое максимальное использование памяти, нужен модуль 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")
Он выглядит сложно лишь на первый взгляд. Но при более детальном рассмотрении все оказывается значительно проще.
Для встроенных функций нами создается две функции-обертки для обеспечения возможности осуществлять их передачу в роли аргументов в 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
Как можно понять, с помощью функции sorted(), используется почти на треть больше памяти, чем для list.sort(). В этом нет ничего удивительного , учитывая то, что последний вариант изменяет список на месте, в то время как первый создает отдельный список.
О скорости сортировки в Python
Чтобы разобраться в количестве времени, которое необходимо для выполнения каждой из этих функций-оберток, используется модуль boxx, который не включен в стандартную комплектацию языка Python ни одной из версий. Тем не менее, это не проблема, поскольку все можно найти в интернете. Скачайте его, а далее смотрите на пример кода. Данный фрагмент демонстрирует, как правильно используется функцию 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()
Учтите, что сперва рекомендуется запустить функцию sorted_builtin(), поскольку метод list.sort() осуществляет сортировку списка сразу. Следовательно, функции sorted() и не надо уже ничего сортировать.
После того, как мы запустим код выше, результат получим следующий. В вашем конкретном случае цифры могут быть другими, поскольку время выполнения отличается в зависимости от мощности аппаратного обеспечения, а также ряда других характеристик (например, загруженности ОЗУ другими приложениями или модулями системы).
$ 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
Эти функции имеют почти одинаковый байтовый код. Единственное отличие: 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 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(). Тем не менее, если вы не нуждаетесь в наличии оригинального списка, это гораздо эффективнее.
Как вы можете прочитать из фрагмента выше, в официальной документации Python говорится, что и так становится понятно: list.sort() эффективнее. Помимо этого, в документации идет речь о том, что очень часто sorted() значительно удобнее. Простыми словами, все зависит от целей, для которых используется та и другая функция.
Может появиться вопрос по поводу стабильности каждой из этих техник. К счастью, в документации имеется ответ и на это. Результаты сортировки стабильны. Это означает, что если у записей ключ такой же самый, то и их изначальный порядок будет сохранен.
Это же верно при использовании реверсивного параметра либо двойном использовании реверсивной функции.
Заключение
После осуществления мини-анализа мы доказали, что list.sort() немного быстрее sorted() и использует на 24% меньше памяти. Тем не менее, стоит учитывать, что list.sort() используется исключительно для списков, а sorted() принимает какие-угодно итерации. Также во время применения list.sort() вы потеряете оригинальный список.
В любом случае, сделав эти выводы, можно существенно улучшить свою работу.
