計算機科學家改進 Python 排序功能

利物浦大學計算機科學家解決了一個長期存在的演算法難題，以加速 Python 的核心構建塊，Python 是最流行的程式語言之一，也是現代人工智慧系統的基礎之一。

這是一種更好的 Python 列表排序解決方案，稱為 Powersort，已在 Python 3。11（10 月釋出的最新版本）中實現。

Powersort 透過“list。sort”和“sorted”函式按升序排列物件列表，利物浦大學計算機科學系講師 Sebastian Wild 博士負責其發明。

Wild 博士一直在研究 TimSort，這是一種由一位非常厲害的Python 開發人員 Tim Peters 發明的自定義排序演算法，特別是它的合併策略，它確定檢測到的執行被連續“合併”以形成更長執行的順序，直到最終列表已完全排序。

Wild 博士對其合併策略知之甚少感到驚訝，因為它甚至潛伏著一個演算法錯誤和潛在的安全問題。事實證明，這個關鍵部件後來被發現存在缺陷。

Wild 博士和他當時的博士後導師，加拿大滑鐵盧大學的 Ian Munro 教授的一次討論發現，一個來自 70 年代的理論演算法為尋找好的合併順序的問題提供了最優解。

這一發現導致了“Powersort”的誕生，它最初發表於 2018 年歐洲演算法研討會，並在到達 Python 參考實現之前受到 Python 社群的進一步審查。

Wild 博士說，“我很高興我的研究已經投入實際使用，並已在 Python 3。11 中實現。我透過調查 Timsort 的工作偶然發現了找到好的合併順序的解決方案。‘Powersort’ 誕生了。”

“我很高興 Tim Peters 親自將我們的想法帶入了 CPython 參考實現。他的 Timsort 實現是演算法工程的傑作，沒有人像他一樣瞭解這段程式碼。”

Carl Friedrich Bolz-Tereick 是 Python 軟體基金會的成員，也是 Python 的另一種實現 PyPy 的核心開發人員，他補充說：“Powersort 是一個很好的例子，說明 Python 的開源特性如何使我們能夠非常快速地，帶來前沿研究，將發現用於每個人的生產使用。當我瞭解 Powersort 時，我可以在幾天內將其包含到 PyPy 中。”

“隨著今年 10 月 Python 3。11 的正式釋出，數以億計的使用者現在將享受到排序速度變得越來越快。儘管許多輸入的改進很小，但 Python 安裝的絕對數量，可以在全球範圍內節省能源。”

Timsort 還用於其他重要的軟體平臺，包括用於大多數智慧手機的 Java 和 Android 執行時庫，以及用於 Google Chrome 和 node。js 的 V8 JavaScript 引擎，驅動許多現代 Web 應用程式，這些應用程式都可以從 Powersort 中獲益。

Wild 博士繼續對排序進行研究，他剛剛完成了 Powersort 的改進工作，現在在每個步驟中同時合併四個執行。

該研究發表在

arXiv

預印本伺服器上。