Всем привет! Продолжаем тему внутреннего устройства Питона :)
Когда приступаешь к изучению программирования, равно или поздно сталкиваешься с алгоритмами сортировки – изучаешь сортировку пузырьком, вставками, выбором, быстрая сортировка – да этих алгоритмов много.
И тут возникает вопрос – есть ли смысл применять все эти сортировки на практике, когда в Python уже и так есть методы sorted() и sort() ?
Давайте окунемся в эти методы поглубже и подумаем, какой алгоритм там используется. Чтобы не ходить вокруг да около – в Python штатным алгоритмом является Timsort – так называемый “гибридный” алгоритм, разработанный программистом Тимом Петерсом. “Гибридный” означает, что внутри алгоритма используется сразу несколько известных алгоритмом. Эдакий алгоритм над алгоритмами.
Выглядит timsort изнутри вот так:
- Коллекция разбивается на подколлекции (либо массив на подмассивы, говоря терминами алгоритмов, а не Python)
- Каждая подколлекция сортируется известным нам алгоритмом сортировки вставками
- При помощи сортировки слиянием, подколлекции сливаются в единую коллекцию.
Если вам хочется залезть еще глубже, то более подробно об устройстве алгоритма рекомендую почитать на Википедии – там довольно интересная статья.
Итак, что же нам это дает? А дает timsort довольно хорошую скорость работы. Максимальная сложность алгоритма составляет O(n log n), так же, как и Merge Sort, например. Не переживайте, если вы не понимаете, что это значит. Чуть ниже расскажу более простыми словами.
Но вопрос, если максимальная скорость работы Timsort сопоставима с сортировкой слиянием, в чем её преимущество? А преимущество в том, что timsort в некоторых случаях может давать аж линейную скорость, что недостижимо ни в быстрой сортировке, ни в сортировке слиянием. То есть, сортировка слиянием гарантирует скорость O(n log n), в то время, как для timsort она является всего лишь максимальной, и во многих случаях она может отработать еще быстрее. Грубо говоря, на некоторых данных timsort сработает настолько быстро, что ни одному другому алгоритму не по силам, а в худшем случае – скорость будет не ниже, чем у аналогичных алгоритмов.
Тогда в итоге – может ли случится такая ситуация, когда вместо стандартного sorted() лучше написать свою сортировку? Да, такое вполне может быть. Но это будет актуально только в том случае, если вы точно знаете, что timsort на коллекцию выдаст результат не лучше, чем O(n log n) либо, если вам нужно написать сортировку с какой-нибудь хитростью. Пример из банальных – после каждого шага сортировки нужно вызывать какую-нибудь функцию или изменять переменную. Такое тоже может быть, хотя и случай редкий.
Кстати, не забывайте, что встроенные структуры данных и методы написаны на языке C, что уж точно не убавит скорости по сравнению с кодом сортировки, написанным на Python.
В предыдущей статье я писал про то, как работает функция len() и почему она работает так быстро. Почитайте, это тоже интересно :)
Если вы хотите изучать Python, и не знаете, как заглянуть в него глубже, чем в решение простых задач – приглашаю вас на мой курс по Python разработке с нуля. Даже если у вас есть небольшой опыт, будет только плюсом. Подробнее можете почитать на сайте моего курса https://myfriendcourse.ru
