Ученые улучшили функцию сортировки в Python

Главная » Маркетинг, Статьи » Ученые улучшили функцию сортировки в Python

Ученые-компьютерщики Ливерпульского университета решили давнюю алгоритмическую головоломку для ускорения работы одного из основных строительных блоков Python, самого популярного языка программирования и основы современных систем искусственного интеллекта.

В результате открытия было найдено лучшее решение для сортировки списков в Python, названное Powersort, которое было реализовано в Python 3.11, последней версии, выпущенной в октябре.

Powersort упорядочивает списки объектов по возрастанию с помощью функций «list.sort» и «sorted», и за его изобретение отвечает доктор Себастьян Уайлд, преподаватель факультета компьютерных наук Ливерпульского университета.

Доктор Уайлд изучал TimSort, пользовательский алгоритм сортировки, придуманный Тимом Питерсом, влиятельным разработчиком Python, и, в частности, его политику слияния, которая определяет порядок, в котором обнаруженные прогоны последовательно «сливаются», образуя более длинные прогоны, пока в конечном итоге список не будет полностью отсортирован.

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

В ходе дискуссии между доктором Уайлдом и его тогдашним научным руководителем, профессором Яном Манро из Университета Ватерлоо, Канада, выяснилось, что теоретический алгоритм 1970-х годов дает оптимальное решение проблемы поиска хороших порядков слияния.

Улучшенная функция сортировки в python

Это открытие привело к рождению алгоритма «Powersort», который был первоначально опубликован на Европейском симпозиуме по алгоритмам 2018 года и в дальнейшем тщательно изучался сообществом Python, прежде чем попал в эталонную реализацию Python.

Доктор Уайлд сказал: «Я рад, что мои исследования нашли практическое применение и были реализованы в Python 3.11. Я наткнулся на решение по поиску хороших порядков слияния во время своей работы по исследованию Timsort. Через неделю после того, как я нашел алгоритм 50-летней давности, родился «Powersort»».

«Я очень рад, что сам Тим Питерс взял нашу идею в эталонную реализацию CPython. Его реализация Timsort — это шедевр алгоритмической инженерии, и никто не знает этот код так, как он.»

Карл Фридрих Больц-Терейк, член Python Software Foundation и основной разработчик PyPy, альтернативной реализации Python, добавил: «Powersort — отличный пример того, как природа Python с открытым исходным кодом позволяет нам очень быстро внедрять передовые научные разработки в производство для всех. Когда я узнал о Powersort, я смог включить его в PyPy за считанные дни».

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

Timsort также используется в других важных программных платформах, включая библиотеки Java и Android, используемые в большинстве смартфонов, и движок V8 JavaScript, используемый в Google Chrome и node.js, на котором основана большая часть современных веб-приложений, которые потенциально могут извлечь выгоду из Powersort.

Доктор Уайлд продолжает исследования в области сортировки и только что закончил работу над усовершенствованием Powersort, теперь объединяющего четыре прогона одновременно на каждом шаге.