Чем отличается sort от sorted в питоне
Перейти к содержимому

Чем отличается sort от sorted в питоне

  • автор:

Особенности сортировки через sort() и sorted()

Здесь мы с вами затронем вопрос сортировки итерируемых объектов с помощью метода sort() и функции sorted(). Давайте вначале посмотрим на отличие в их вызовах. Если у нас имеется какой-либо список:

a=[1,-45,3,2,100,-4]

то этот объект имеет встроенный метод sort, который меняет его состояние и расставляет элементы по возрастанию:

a.sort()

Получим измененный список:

[-45, -4, 1, 2, 3, 100]

А вот коллекции кортежи или строки:

b=("ab", "bc", "wd", "gf") c = "hello world"

не имеют такого встроенного метода и попытка их отсортировать, записав:

b.sort() c.sort()

приведет к ошибке. Для их сортировки как раз и можно воспользоваться второй функцией sorted:

sorted(b)

на выходе получим упорядоченный список

Обратите внимание, чтобы мы не передавали в качестве аргумента функции sorted, на выходе будем получать именно список отсортированных данных. В данном случае передаем кортеж, а получаем – список.

Или же, со строкой:

sorted(c)

результатом будет упорядоченная коллекция из символов:

Причем, эта функция не меняет исходные коллекции b и c, она возвращает новый список с отсортированными данными. В то время как метод sort для списка меняет этот список. Вот на это следует также обращать внимание. То есть, если нам нужно сохранить результат сортировки в переменной, это делается так:

res = sorted(b)

и res будет ссылаться на список:

Также следует иметь в виду, что сортировка данных возможна для однотипных элементов: или чисел, или строк, или кортежей, но не их комбинаций. Например, вот такой список:

a=[1,-45,3,2,100,-4, "b"]

отсортировать не получится:

a.sort()

возникнет ошибка, что строку нельзя сравнивать с числом. И то же самое с функцией sorted:

sorted(a)

Если уберем последний элемент:

a=[1,-45,3,2,100,-4]

то все будет работать:

sorted(a)

И этот пример также показывает, что список можно сортировать и с помощью метода sort и с помощью функции sorted. Разница только в том, что метод sort не создает новой коллекции, а меняет уже существующую. Функция же sorted не меняет исходную коллекцию, а создает новую с отсортированными элементами. Поэтому, для изменения коллекции a здесь следует записывать такую конструкцию:

a = sorted(a)

Оба этих подхода к сортировке поддерживают необязательный параметр

который определяет порядок сортировки: по возрастанию (False) или по убыванию (True). По умолчанию стоит значение reverse=False. Если мы запишем его вот так:

a = sorted(a, reverse=True)

то получим сортировку по убыванию:

[100, 3, 2, 1, -4, -45]

И то же самое с методом sort:

a.sort(reverse=True)

Давайте еще посмотрим, как будет работать сортировка для словаря:

d = {'river': "река", 'house': "дом", 'tree': "дерево", 'road': "дорога"}

Очевидно, для него мы можем использовать только функцию sorted():

sorted(d)

которая на выходе даст список с ключами, отсортированными по возрастанию. И это логично, так как словарь по умолчанию возвращает именно ключи при его итерировании.

Также можно использовать конструкции вида:

sorted(d.values())
sorted(d.items())

Работают они очевидным образом.

Надеюсь, из этого занятия вы лучше стали понимать, как можно выполнять сортировку различных коллекций в языке Python. Для закрепления этого материала вас ждут практические задания, а я буду всех ждать на следующем уроке, где мы продолжим эту тему и поговорим о тонкой настройке алгоритма сортировки данных.

Видео по теме

#1. Первое знакомство с Python Установка на компьютер

#2. Варианты исполнения команд. Переходим в PyCharm

#3. Переменные, оператор присваивания, функции type и id

#4. Числовые типы, арифметические операции

#5. Математические функции и работа с модулем math

#6. Функции print() и input(). Преобразование строк в числа int() и float()

#7. Логический тип bool. Операторы сравнения и операторы and, or, not

#8. Введение в строки. Базовые операции над строками

#9. Знакомство с индексами и срезами строк

#10. Основные методы строк

#11. Спецсимволы, экранирование символов, row-строки

#12. Форматирование строк: метод format и F-строки

#13. Списки — операторы и функции работы с ними

#14. Срезы списков и сравнение списков

#15. Основные методы списков

#16. Вложенные списки, многомерные списки

#17. Условный оператор if. Конструкция if-else

#18. Вложенные условия и множественный выбор. Конструкция if-elif-else

#19. Тернарный условный оператор. Вложенное тернарное условие

#20. Оператор цикла while

#21. Операторы циклов break, continue и else

#22. Оператор цикла for. Функция range()

#23. Примеры работы оператора цикла for. Функция enumerate()

#24. Итератор и итерируемые объекты. Функции iter() и next()

#25. Вложенные циклы. Примеры задач с вложенными циклами

#26. Треугольник Паскаля как пример работы вложенных циклов

#27. Генераторы списков (List comprehensions)

#28. Вложенные генераторы списков

#29. Введение в словари (dict). Базовые операции над словарями

#30. Методы словаря, перебор элементов словаря в цикле

#31. Кортежи (tuple) и их методы

#32. Множества (set) и их методы

#33. Операции над множествами, сравнение множеств

#34. Генераторы множеств и генераторы словарей

#35. Функции: первое знакомство, определение def и их вызов

#36. Оператор return в функциях. Функциональное программирование

#37. Алгоритм Евклида для нахождения НОД

#38. Именованные аргументы. Фактические и формальные параметры

#39. Функции с произвольным числом параметров *args и **kwargs

#40. Операторы * и ** для упаковки и распаковки коллекций

#41. Рекурсивные функции

#42. Анонимные (lambda) функции

#43. Области видимости переменных. Ключевые слова global и nonlocal

#44. Замыкания в Python

#45. Введение в декораторы функций

#46. Декораторы с параметрами. Сохранение свойств декорируемых функций

#47. Импорт стандартных модулей. Команды import и from

#48. Импорт собственных модулей

#49. Установка сторонних модулей (pip install). Пакетная установка

#50. Пакеты (package) в Python. Вложенные пакеты

#51. Функция open. Чтение данных из файла

#52. Исключение FileNotFoundError и менеджер контекста (with) для файлов

#53. Запись данных в файл в текстовом и бинарном режимах

#54. Выражения генераторы

#55. Функция-генератор. Оператор yield

#56. Функция map. Примеры ее использования

#57. Функция filter для отбора значений итерируемых объектов

#58. Функция zip. Примеры использования

#59. Сортировка с помощью метода sort и функции sorted

#60. Аргумент key для сортировки коллекций по ключу

#61. Функции isinstance и type для проверки типов данных

#62. Функции all и any. Примеры их использования

#63. Расширенное представление чисел. Системы счисления

#64. Битовые операции И, ИЛИ, НЕ, XOR. Сдвиговые операторы

#65. Модуль random стандартной библиотеки

#66. Аннотация базовыми типами

#67. Аннотации типов коллекций

#68. Аннотации типов на уровне классов

#69. Конструкция match/case. Первое знакомство

#70. Конструкция match/case с кортежами и списками

#71. Конструкция match/case со словарями и множествами

#72. Конструкция match/case. Примеры и особенности использования

© 2024 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта

Как работает метод sort в python?

В python, метод sort применяется к спискам(в отличие от функции sorted() , которая применяется к любым итерируемым объектам). Важно, что все элементы списка должны быть одинакового типа(строки, числа, кортежи). Метод list.sort() изменяет список по месту, и возвращает None . Если вызвать метод без параметров, то элементы списка отсортируются в порядке возрастания.

my_list = [7, 5, 8, 2, 11, 1, 14] my_list.sort() print(my_list) # [1, 2, 5, 7, 8, 11, 14] 

Сортировка в порядке убывания:

my_list = [7, 5, 8, 2, 11, 1, 14] my_list.sort(reverse=True) print(my_list) # [14, 11, 8, 7, 5, 2, 1] 

Также, метод sort может принимать параметр key (функция), по которому будет произведена сортировка:

my_list = [7, 5, 8, 2, 11, 1, 14] my_list.sort(key=lambda x: x%2) 

в данном случае, сначала в отсортированном списке буду четные, а потом нечетные элементы.

Всё о сортировке в Python: исчерпывающий гайд

Сортировка в Python выполняется с помощью sorted() и list.sort(). Разбираем на примерах, как это работает.

Сортировка в Python выполняется функцией sorted() , если это итерируемые объекты, и методом list.sort() , если это список. Рассмотрим подробнее, как это работало в старых версиях и как работает сейчас.

Примечание Вы читаете улучшенную версию некогда выпущенной нами статьи.

Разработка на Python с нуля: роадмап программиста

Основы сортировки

Так как отсортировать список Python? Для сортировки по возрастанию достаточно вызвать функцию сортировки Python sorted() , которая вернёт новый отсортированный список:

>>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 

Для сортировки списка Python также можно использовать метод списков list.sort() , который изменяет исходный список (и возвращает None во избежание путаницы). Обычно Python sort list не так удобен, как использование sorted() , но если вам не нужен исходный список, то так будет немного эффективнее:

>>> a = [5, 2, 3, 1, 4] >>> a.sort() >>> a [1, 2, 3, 4, 5] 

Прим.перев. В Python вернуть None и не вернуть ничего — одно и то же.

Ещё одно отличие заключается в том, что метод list.sort() определён только для списков, в то время как функция sorted Python работает со всеми итерируемыми объектами. Грубо говоря, функция sort Python сортирует список и сохраняет его в отсортированном виде, в то время как функция sorted Питон создаёт новый отсортированный список без изменения исходного.

>>> sorted() [1, 2, 3, 4, 5] 

Прим.перев. При итерировании по словарю Python возвращает его ключи. Если вам нужны их значения или пары «ключ-значение», используйте методы dict.values() и dict.items() соответственно.

Рассмотрим основные функции сортировки Python.

Функции-ключи

С версии Python 2.4 у list.sort() и sorted() появился параметр key для указания функции, которая будет вызываться на каждом элементе до сравнения. Вот регистронезависимое сравнение строк:

>>> sorted("This is a test string from Andrew".split(), key=str.lower) ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This'] 

Значение key должно быть функцией, принимающей один аргумент и возвращающей ключ для сортировки. Работает быстро, потому что функция-ключ вызывается один раз для каждого элемента.

Всё о сортировке в Python: исчерпывающий гайд 1

Часто можно встретить код, где сложный объект сортируется по одному из его индексов. Например:

>>> student_tuples = [ ('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10), ] >>> sorted(student_tuples, key=lambda student: student[2]) # сортируем по возрасту [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] 

Тот же метод работает для объектов с именованными атрибутами:

>>> class Student: def __init__(self, name, grade, age): self.name = name self.grade = grade self.age = age def __repr__(self): return repr((self.name, self.grade, self.age)) def weighted_grade(self): return 'CBA'.index(self.grade) / self.age >>> student_objects = [ Student('john', 'A', 15), Student('jane', 'B', 12), Student('dave', 'B', 10), ] >>> sorted(student_objects, key=lambda student: student.age) # сортируем по возрасту [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]​ 
Функции модуля operator

Показанные выше примеры функций-ключей встречаются настолько часто, что Python предлагает удобные функции, чтобы сделать всё проще и быстрее. Модуль operator содержит функции itemgetter() , attrgetter() и, начиная с Python 2.6, methodcaller() . С ними всё ещё проще:

>>> from operator import itemgetter, attrgetter, methodcaller >>> sorted(student_tuples, key=itemgetter(2)) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] >>> sorted(student_objects, key=attrgetter('age')) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] 

Функции operator дают возможность использовать множественные уровни сортировки массива Python. Отсортируем учеников сначала по оценке, а затем по возрасту:

>>> sorted(student_tuples, key=itemgetter(1, 2)) [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] >>> sorted(student_objects, key=attrgetter('grade', 'age')) [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)] 

Используем функцию methodcaller() для сортировки учеников по взвешенной оценке:

>>> [(student.name, student.weighted_grade()) for student in student_objects] [('john', 0.13333333333333333), ('jane', 0.08333333333333333), ('dave', 0.1)] >>> sorted(student_objects, key=methodcaller('weighted_grade')) [('jane', 'B', 12), ('dave', 'B', 10), ('john', 'A', 15)] 
Сортировка по возрастанию и сортировка по убыванию в Python

list.sort() и sorted() есть параметр reverse , принимающий boolean-значение. Он нужен для обозначения сортировки по убыванию. Отсортируем учеников по убыванию возраста:

>>> sorted(student_tuples, key=itemgetter(2), reverse=True) [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] >>> sorted(student_objects, key=attrgetter('age'), reverse=True) [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] 
Стабильность сортировки и сложные сортировки в Python

Начиная с версии Python 2.2, сортировки гарантированно стабильны: если у нескольких записей есть одинаковые ключи, их порядок останется прежним. Пример:

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> sorted(data, key=itemgetter(0)) [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)] 

Обратите внимание, что две записи с ‘blue’ сохранили начальный порядок. Это свойство позволяет составлять сложные сортировки путём постепенных сортировок. Далее мы сортируем данные учеников сначала по возрасту в порядке возрастания, а затем по оценкам в убывающем порядке, чтобы получить данные, отсортированные в первую очередь по оценке и во вторую — по возрасту:

>>> s = sorted(student_objects, key=attrgetter('age')) # сортируем по вторичному ключу >>> sorted(s, key=attrgetter('grade'), reverse=True) # по первичному [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] 

Алгоритмы сортировки Python вроде Timsort проводят множественные сортировки так эффективно, потому что может извлечь пользу из любого порядка, уже присутствующего в наборе данных.

Декорируем-сортируем-раздекорируем
  1. Сначала исходный список пополняется новыми значениями, контролирующими порядок сортировки.
  2. Затем новый список сортируется.
  3. После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.

Вот так можно отсортировать данные учеников по оценке:

>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)] >>> decorated.sort() >>> [student for grade, i, student in decorated] # раздекорируем [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)] 

Это работает из-за того, что кортежи сравниваются лексикографически, сравниваются первые элементы, а если они совпадают, то сравниваются вторые и так далее.

Не всегда обязательно включать индекс в декорируемый список, но у него есть преимущества:

  1. Сортировка стабильна — если у двух элементов одинаковый ключ, то их порядок не изменится.
  2. У исходных элементов не обязательно должна быть возможность сравнения, так как порядок декорированных кортежей будет определяться максимум по первым двум элементам. Например, исходный список может содержать комплексные числа, которые нельзя сравнивать напрямую.

Ещё эта идиома называется преобразованием Шварца в честь Рэндела Шварца, который популяризировал её среди Perl-программистов.

Для больших списков и версий Python ниже 2.4, «декорируем-сортируем-раздекорируем» будет оптимальным способом сортировки. Для версий 2.4+ ту же функциональность предоставляют функции-ключи.

Использование параметра cmp

Все версии Python 2.x поддерживали параметр cmp для обработки пользовательских функций сравнения. В Python 3.0 от этого параметра полностью избавились. В Python 2.x в sort() можно было передать функцию, которая использовалась бы для сравнения элементов. Она должна принимать два аргумента и возвращать отрицательное значение для случая «меньше чем», положительное — для «больше чем» и ноль, если они равны:

>>> def numeric_compare(x, y): return x - y >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) [1, 2, 3, 4, 5] 

Можно сравнивать в обратном порядке:

>>> def reverse_numeric(x, y): return y - x >>> sorted([5, 2, 4, 1, 3], cmp=reverse_numeric) [5, 4, 3, 2, 1] 

При портировании кода с версии 2.x на 3.x может возникнуть ситуация, когда нужно преобразовать пользовательскую функцию для сравнения в функцию-ключ. Следующая обёртка упрощает эту задачу по Python:

def cmp_to_key(mycmp): 'Перевести cmp=функция в key=функция' class K(object): def __init__(self, obj, *args): self.obj = obj def __lt__(self, other): return mycmp(self.obj, other.obj) < 0 def __gt__(self, other): return mycmp(self.obj, other.obj) >0 def __eq__(self, other): return mycmp(self.obj, other.obj) == 0 def __le__(self, other): return mycmp(self.obj, other.obj) = 0 def __ne__(self, other): return mycmp(self.obj, other.obj) != 0 return K 

Чтобы произвести преобразование, оберните старую функцию:

>>> sorted([5, 2, 4, 1, 3], key=cmp_to_key(reverse_numeric)) [5, 4, 3, 2, 1] 

В Python 2.7 функция cmp_to_key() была добавлена в модуль functools.

Поддержание порядка сортировки

В стандартной библиотеке Python нет модулей, аналогичных типам данных C++ вроде set и map . Python делегирует эти задачи сторонним библиотекам, доступным в Python Package Index: они используют различные методы для сохранения типов list , dict и set в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:

  • SortedContainers — реализация сортированных типов list , dict и set на чистом Python, по скорости не уступает реализациям на C. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада.
  • rbtree — быстрая реализация на C для типов dict и set . Реализация использует структуру данных, известную как красно-чёрное дерево.
  • treap — сортированный dict . В реализации используется Декартово дерево, а производительность улучшена с помощью Cython.
  • bintrees — несколько реализаций типов dict и set на основе деревьев на C. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей.
  • banyan — быстрая реализация dict и set на C.
  • skiplistcollections — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов dict и set .
  • blist — предоставляет сортированные типы list , dict и set , основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и C.
Прочее

Для сортировки с учётом языка используйте locale.strxfrm() в качестве ключевой функции или locale.strcoll() в качестве функции сравнения. Параметр reverse всё ещё сохраняет стабильность сортировки. Этот эффект можно сымитировать без параметра, использовав встроенную функцию reversed() дважды:

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data)))) 

Чтобы создать стандартный порядок сортировки для класса, просто добавьте реализацию соответствующих методов сравнения:

>>> Student.__eq__ = lambda self, other: self.age == other.age >>> Student.__ne__ = lambda self, other: self.age != other.age >>> Student.__lt__ = lambda self, other: self.age < other.age >>> Student.__le__ = lambda self, other: self.age >> Student.__gt__ = lambda self, other: self.age > other.age >>> Student.__ge__ = lambda self, other: self.age >= other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)] 

Для типов, сравнение которых работает обычным образом, рекомендуется определять все 6 операторов. Декоратор классов functools.total_ordering упрощает их реализацию. Функциям-ключам не нужен доступ к внутренним данным сортируемых объектов. Они также могут осуществлять доступ к внешним ресурсам. Например, если оценки ученика хранятся в словаре, их можно использовать для сортировки отдельного списка с именами учеников:

>>> students = ['dave', 'john', 'jane'] >>> newgrades = >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john'] 

Надеемся, теория по Python list sort и соответствующие задачи по Питону с разбором были для вас полезны. Вас также может заинтересовать статьи:

  • Хочу научиться программировать на Python. С чего начать?
  • Хочу научиться программировать на Python: инструкция для продолжающих

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

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

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

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

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

Есть вопросы по 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
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 # Секунды
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)
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() потребляет примерно на 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 )
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__» :

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *