Самый популярный язык программирования - Python для AI. Ученые-компьютерщики улучшают возможности сортировки в Python

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

Это открытие привело к созданию превосходного решения для сортировки списков в Python под названием Powersort, которое было реализовано в последней версии Python 3.11, выпущенной в октябре.

Powersort сортирует списки в порядке возрастания с помощью функций "list.sort" и "sorted", а его изобретателем является доктор Себастьян Вилд, преподаватель информатики в Ливерпульском университете.

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

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

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

Это открытие привело к созданию 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, которая объединяет четыре одновременных выполнения на каждом шаге.

Данное исследование доступно на сервере препринтов arXiv.

/по материалам