Вчені поліпшили функцію сортування в 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, який тепер об’єднує чотири прогони одночасно на кожному кроці.

Коллектив сайта

(Пока оценок нет)

Loading...