【CSDN 編者按】說到演算法和資料結構每個程式設計師應該都很瞭解。近日，從事 AI+ 開發工具工作的 Austin Z。 Henley釋出了他的第三篇熱門帖子，總結道每個程式設計師都應該嘗試具有挑戰性的演算法和資料結構。

原文連結：https：//austinhenley。com/blog/challengingalgorithms。html

作者 | Austin Z。 Henley 譯者 | 禾木木

出品 | CSDN（ID：CSDNnews）

此前，Austin Z。 Henley 釋出了兩篇“每個程式設計師都應該嘗試具有挑戰性的專案”。文中列出了每個程式設計師都應該去嘗試的專案，包括文字編輯器、太空入侵者遊戲、 BASIC 編譯器、一個小型的作業系統、一個電子表格、一個影片遊戲控制檯模擬器、光線追蹤器、鍵值儲存 Web API 、Web 瀏覽器和股票交易機器人。這兩篇文章在網路上爆紅，一個月內瀏覽量超過 10 萬次。

繼這兩篇後，Austin Z。 Henley 又釋出了他的第三篇內容，在文章中列出了程式設計師應該嘗試的有趣的演算法和資料結構：

拓撲序列

遞迴下降解析

Myers 差分演算法

Bloom filter

Piece table

伸展樹

拓撲序列

拓撲排序簡單講就是在可求拓撲序列的有向無迴路圖（有向無環圖）中求取拓撲序列的排序演算法。常見的場景包括確定構建系統的任務順序、電子表格中單元格的評估順序、學生每學期畢業應上哪些課，以及各種排程問題。

Austin Z。 Henley 曾在 Tennessee 大學任教時使用它來重新排列圖表，使其更易於閱讀。

拓撲排序：https：//en。wikipedia。org/wiki/Topological_sorting

拓撲排序互動式視覺化：https：//www。cs。usfca。edu/~galles/visualization/TopoSortDFS。html

遞迴下降解析

這一次，就像打開了一種超能力！

如果你需要攝取遞迴資料格式或編寫程式語言，這是最適合的工具。輕鬆地編出語法，並將每個語法規則對映到程式碼函式中。

感覺就像它自己在編碼一樣。

你可以在幾個小時內用它製作一個簡單的編譯器。

Teeny Tiny 編譯器：https：//austinhenley。com/blog/teenytinycompiler2。html

製作翻譯：https：//amzn。to/3HT015y

遞迴下降解析器：https：//en。wikipedia。org/wiki/Recursive_descent_parser

Myers 差分演算法

處理字串通常是一項非常常見的程式設計任務，但作者通常是透過暴力強制來解決需要計算的任何問題。程式設計師們都學過 Levenshtein 距離，但是如果需要以一種合理的方式顯示兩個字串之間的差異呢？

其中，Git 用於顯示差分的預設演算法是 Myers 差分演算法。

Myers 差分演算法：https：//blog。jcoglan。com/2017/02/12/the-myers-diff-algorithm-part-1/

程式碼和互動式視覺化：https：//blog。robertelder。org/diff-algorithm/

Bloom filter

布隆過濾器（ Bloom filter）可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。

它實際上只對大規模的問題有幫助，例如當你需要一個非常大的雜湊表時，它則是對機率資料結構的一個很好的介紹。在記憶體很小的情況下，它可以告訴你表中是否存在某個專案，否則它只能告訴該項是否存在。

Bloom filter：https：//en。wikipedia。org/wiki/Bloom_filter

操作 Bloom filter：https：//onatm。dev/2020/08/10/let-s-implement-a-bloom-filter/

示例：https：//llimllib。github。io/bloomfilter-tutorial/

Piece table

當 Austin Z。 Henley 第一次嘗試製作文字編輯器時，便將所有文字儲存在一個數組中。但這會導致效能問題（例如，當用戶在任何地方插入文字而不是結尾時）。幾年後，在一次實習面試中被問到如何實現一個高效能文字緩衝區。

他也會考慮該使用什麼。有一些不同的方案需要權衡：rope， gap buffer， 或是 piece table。使用 piece table，可以跟蹤對文字執行的編輯，而僅僅不是隻保留生成的文字。它使許多其他功能變得很簡單（例如，撤銷支援和增量儲存）。

不過，piece table 只對文字編輯器有用。只要有可以任意修改的大資料緩衝區時，就可以使用它。

Piece table：https：//en。wikipedia。org/wiki/Piece_table

VS Code 的文字緩衝區：https：//code。visualstudio。com/blogs/2018/03/23/text-buffer-reimplementation

Piece table：https：//darrenburns。net/posts/piece-table/

伸展樹

那麼自我最佳化的資料結構怎麼樣呢？

伸展樹是一種二叉樹，它傾向於將最近訪問的元素靠近根，並且這樣做不需要維護任何額外的元資料。每次訪問一個元素時，它都會被移動到根目錄。

這是一個帶有內建快取的樹，實現起來非常簡單！

伸展樹互動視覺化：https：//www。cs。usfca。edu/~galles/visualization/SplayTree。html

伸展樹：https：//en。wikipedia。org/wiki/Splay_tree

TypeScript 中的實現：https：//github。com/w8r/splay-tree

如果你還知道哪些更有趣的演算法或是資料結構，可以在評論區留言呦。

參考連結：

https：//austinhenley。com/blog/challengingalgorithms。html

https：//austinhenley。com/blog/challengingprojects。html

https：//austinhenley。com/blog/morechallengingprojects。html

《2022-2023 中國開發者大調查》重磅啟動，歡迎掃描下方二維碼，參與問卷調研，更有 iPad 等精美大禮等你拿！