Golang 的排序演算法將換成 pdqsort，LLVM libc++ 換成 BlockQuicksort
source link: https://blog.gslin.org/archives/2022/04/22/10673/golang-%e7%9a%84%e6%8e%92%e5%ba%8f%e6%bc%94%e7%ae%97%e6%b3%95%e5%b0%87%e6%8f%9b%e6%88%90-pdqsort%ef%bc%8cllvm-libc-%e6%8f%9b%e6%88%90-blockquicksort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Golang 的排序演算法將換成 pdqsort，LLVM libc++ 換成 BlockQuicksort
在 Hacker News 首頁上看到的消息，Golang 將會把 sort.Sort() 換成 pdqsort (Pattern-defeating Quicksort)：「Go will use pdqsort in next release (github.com/golang)」，對應的 commit 則是在「sort: use pdqsort」這邊可以看到。
然後另外是「Changing std:sort at Google’s scale and beyond (danlark.org)」這邊題到了，LLVM 將 libc++ 的 std::sort 從 Quicksort 換成 BlockQuicksort。另外在文章裡面有提到一段 Knuth 老大在 TAOCP 裡講 sorting algorithm 沒有霸主的情況：
It would be nice if only one or two of the sorting methods would dominate all of the others, regardless of application or the computer being used. But in fact, each method has its own peculiar virtues. […] Thus we find that nearly all of the algorithms deserve to be remembered, since there are some applications in which they turn out to be best.
先回到 pdqsort 的部份，pdqsort 作者的 GitHub 上 (orlp/pdqsort) 可以看到他對 pdqsort 的說明：
Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns.
看名字也可以知道 pdqsort 是從 Quicksort 改良的版本，而依照 Golang 的 commit 上的測試，與 Quicksort 相比，少數情況下會慢一點點，大多數的情況下會快一些，而在特殊情境下會讓 worst case 下降。
Golang 選擇把 unstable 的 Quicksort 換成 pdqsort，LLVM 則是選擇把 Quicksort 換成 BlockQuicksort，這邊看起來有些分歧...
反倒是各個程式語言對於 stable 的 Mergesort 陸陸續續都換成了 Timsort，看起來比較像是有個共識...
Related
MySQL ALTER TABLE
《瑪莉亞的凝望》第三本看到一半，到 Twitter 上看到 Jeremy Zawodny (O'Reilly 出的 High Performance MySQL 第一版與第二版的作者之一) 在喊 MySQL ALTER TABLE 跑了八天了： I have an ALTER TABLE running for nearly 8 days now... yikes. 結果 Aaron Brazell 居然很機車的這樣問他 XDDD @jzawodn Removing South Carolina from all Craigslist tables? 如果不清楚 Craigslist 與南卡的新聞，可以參考紐約時報「Under Pressure, Craigslist to Remove ‘Erotic’ Ads」這篇的說明。…
May 27, 2009In "Computer"
JavaScript 的 sort 變成 stable
看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort... 本來 JavaScript 的規格書裡，各種 sort 都沒有保證 stable，而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化，提案在規格裡加入 stable 的要求，可以減少開發者因為不知道 unstable 而造成的問題... Firefox 則是很久前就決定使用 Merge sort 了 (看了一下，當時還在從 Firebird 轉換名稱到 Firefox 的時期)：「Array.sort isn't a stable sort (switch to MergeSort)」。 另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm，之前就有看到但發現沒在 blog 上提過...…
July 3, 2019In "Browser"
Git 的 Diff 演算法
在 Lobsters Daily 上看到「When to Use Each of the Git Diff Algorithms」這篇 2020 的文章 (Lobsters 這邊常冒出一些舊文章)，講 Git 的 diff 演算法。 文章裡面題到了四個演算法，看了一下 git-diff 的 manpage 也還是這四個： --diff-algorithm={patience|minimal|histogram|myers} 另外看 manpage 時還有看到 --anchored 的用法，看起來是用來提示 Git 產生比較好懂的 diff 結果： --anchored= Generate a diff using the "anchored diff" algorithm. This option may be specified more…
October 28, 2021In "Computer"
Leave a Reply
Your email address will not be published. Required fields are marked *
Comment *
Name *
Email *
Website
Notify me of follow-up comments by email.
Notify me of new posts by email.
To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)
Post navigation
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK