作者：Gergely Orosz
機器之心編譯
參與：小舟、杜偉
數據結構和基礎算法作為計算機科學的必學課程，近幾年卻關注度越來越少。但程式設計師真的不再需要這兩門基礎知識了嗎？一位在 Uber 等科技公司工作過的開發者分享了他的一手經驗，告訴你實際工作中會用到哪些數據結構和算法。
日常工作中，你經常使用算法和數據結構嗎？曾就職於 Uber 等科技公司的工程師 Gergely Orosz 提出了這樣一個問題。此外，他也注意到，越來越多的人覺得算法是無用的，並認為它們只是科技公司提出的一種強制性措施罷了。
本文作者 Gergely Orosz。
不僅如此，也有更多的人抱怨稱算法只是純粹的學術練習。在 Homebrew 作者 Max Howell 發表他的谷歌面試經歷之後，這樣的想法被進一步普及。
雖然 Gergely Orosz 自己也從來不需要使用二叉樹翻轉（binary tree inversion），但是他在 Skype、Microsoft、Skyscanner 以及 Uber 工作時，每天都會遇到使用數據結構和算法的情況。
此外，他有時也需要基於這些概念編寫代碼和做出決策。最後，Gergely Orosz 藉助這些知識來理解有些事物如何和為何構建，以及如何使用或修改它們。
由此可見，數據結構和算法並不是如人們所言用處不大。在本文中，Gergely Orosz 列舉了一系列現實世界的實例，包含生產中會用到的樹、圖等數據結構和各種算法。
值得肯定的，所有這些都出自他的第一手經驗，藉此希望表達他的觀點，即通用數據結構和算法知識並不只是「為了面試」，而是你在快速成長的創新型科技公司工作時，可能會經常遇到的東西。
Gergely Orosz 表示自己曾經用過非常小的算法子集，但幾乎包含了所有的數據結構。毫不奇怪，他不喜歡繁瑣的算法以及包含紅黑樹或 AVL 樹等不常見數據類型的不切實際的面試問題。
接下來具體來看作者列舉出來的實例，以第一人稱的口吻進行講述。
樹和樹遍歷：Skype、Uber 和 UI 框架
在微軟時，當我們構建 Xbox One 遊戲機（由微軟發布）的 Skype 軟體時，我們使用的是內置作業系統 Xbox OS，但缺少關鍵庫。我們當時正在該平臺上構建首個成熟的應用程式之一，所以需要一個能夠結合觸摸手勢和語音命令的導航解決方案。
我們在微軟 WinJS 庫上構建了一個通用的導航框架。為了做到這一點，我們需要維護一個類似於 DOM（文檔對象模型）的圖來跟蹤可操作的元素。為了找出這些元素，我們執行了 DOM 遍歷，基本上是現有 DOM 上的 B - 樹遍歷（B-tree traversal）。這便是 BFS（廣度優先搜索）或者 DFS（深度優先搜索）的經典示例。
在 Uber 時，團隊構建了很多實現節點、依賴關係以及它們之間連接可視化的工具。有一個例子就是 RIB 節點的可視化工具。該可視化工具需要維護一棵樹，將它可視化為可縮放矢量圖形（SVG），然後更新這棵樹，同時行動裝置上的 RIB 樹也發生變化。RIB 自己也會為狀態管理維護一個邏輯樹結構（logical tree structure），但這個樹結構與呈現對象不同，這就是他們設計背後的關鍵所在。
RIB 樹可視化：一個使用樹來表示數據並將其可視化的經典示例。
權重圖和最短路徑：Skyscanner
Skyscanner 會找到最佳機票。為此，它掃描了全球所有的航線，並將它們匯聚在一起。由於航空公司需要考慮中轉站的選擇，所以問題的本質更多地體現在爬蟲，而不是緩存。多城市規劃選項（multi-city planning option）成為了最短路徑問題。
多城市是 Skyscanner 花費大量時間來構建的功能之一。公平地說，產品方面的困難是最多的。最佳的多城市航線選擇就是使用 Dijkstra 或者 A * 這樣的最短路徑算法計算的。
航線用一張有向圖來表示，每條邊都有一個表示票價的權重，算出兩個城市之間票價最便宜的航線就是通過每條航線的改進版的 A * 搜索算法實現的。
但是使用 Skyscanner，實際算法就不那麼重要了。緩存、爬蟲和處理各種網站負載比解決問題本身要難得多。即便如此，最短路徑問題的變體還是在許多基於組合優化價格的旅行公司中使用。
排序：Skype
對於排序這種算法，我很少需要自己實現或深入使用。理解不同類型的排序方法是件很有趣的事，包括冒泡排序、插入排序、歸併排序、選擇排序以及最複雜的快速排序。但是，我還是很少需要自己手動實現這些算法，甚至從來沒有把排序函數作為庫的一部分來編寫。
在微軟 Skype 時，我練習了這方面的知識。另有一位工程師決定為聯繫人列表實現插入排序算法。2013 年，Skype 實現了聯網，網絡用戶呈爆炸式增長，而且用戶數還在持續增長。因此這位工程師認為用插入排序按照用戶姓名來構建聯繫人列表，性能會更佳。
關於為什麼不單單使用默認排序算法這一問題，我們也經過了反覆討論。最後結論是，使用默認排序算法需要對實現進行適當的測試和相應基準測試，這可能需要更多的工作。我個人認為這樣做沒有多大意義，並且當時我們正處在項目階段，有很多時間，所以採用了基於聯繫人列表的插入排序算法。
在現實世界中，一定有一些情況，使用高效的排序算法非常重要，並且基於數據選擇使用的排序算法會更加有效。在執行大規模實時數據流並且為這些數據源構建實時可視化時，插入排序很有用。
如果涉及到存儲在不同節點上的大量數據，那麼「分而治之」的歸併排序算法比較合適。我自己沒有使用過這些算法，因此了解這幾種不同的算法之外，我仍然會標記一些自己沒有用過的排序算法。
哈希表和哈希：隨處常見
我最常用到的數據結構就是哈希表以及哈希函數了。從計數、重複檢測、緩存到分片（sharding）之類的分布式系統用例，都會用到這種很方便的工具。
除了數組之外，在很多情況下用哈希表和哈希函數都是非常合適的。幾乎每種語言都會用到這種數據結構，而且它的實現很簡單。
棧和隊列：偶爾用到
任何調試過具有堆棧追蹤的語言的人都非常熟悉這種數據結構。我在使用這種數據結構時遇到了一些問題，但調試和性能分析讓我慢慢熟悉了它。
我很少在自己的代碼中使用隊列這種數據結構，但卻在代碼庫、代碼 pop 和 push 中遇到過很多次。對於分析和配置 builds 的安裝瓶頸檢測器工具而言，我會使用 Python 堆隊列（heap queue）算法來讀優先隊列優化後的代碼。
加密算法：Uber
Uber 很早就使用了幾種語言和技術，並且加密（cryptography）並不能實現我們需要的穩定性。典型的示例就是 iOS 和安卓。來自客戶端用戶輸入的敏感信息在通過網絡發送之前需要加密，同時僅針對特定服務進行解密。
在某些情況下，我們必須自己構建加密 / 解密實現。但在缺少支持框架或沒有可用審核庫的情況下，我們需要對其進行正式的驗證和審核。
構建加密算法總是充滿樂趣。在實現加密算法上存在許多挑戰：你想不出一種實現加密技術的新算法。取而代之的是，你將採用適合案例的現有的已成文的標準，然後驗證並一遍又一遍地審核它。
這種情況就是在實現 AES 標準。這是一個有趣的挑戰。我們已經構建了一些移動端和網頁端的加密實現，其中我自己深入學習了高級加密標準（AEP）、哈希消息身份驗證碼（HMAC）以及 RSA 公鑰加密的詳細知識。
研究攻擊媒介（如消息篡改或拒絕服務的影響）是審核解決方案的一部分。驗證一系列加密步驟是否可以證明是安全的，這
也是一件有趣的事。
只要證明 Encrypt-and-MAC（EaM）、MAC-then-Encrypt（MtE）和 Encrypt-then-MAC（Etm）三者有一個是安全的即可，但這並不意味著其他的是不安全的。
概率論與預測：Uber 的 SubmitQueue
2016 年，我加入了 Uber。移動端最大的痛點是構建以及合併更改需要花費的時間。從構建和所有測試（單元、集成和端到端）開始，構建一個完整的運行大約需要 40 分鐘。我們在開發中投入了大約 300 個開發者。所有的更改必須在落地之前搭建完成。
我旁邊的開發者體驗團隊想解決以下問題，他們從兩個角度做到了。首先，他們加快了構建和測試過程，耗時不超過 30 分鐘；其次，他們的目標是每個人的變更應該花費 30 分鐘，現有時間的 95%。
但是合併衝突呢？讓我們對其進行預測，並相應地建立隊列。這就是他們通過創建衝突和推測圖所做的事情。
帶有層次化索引的六邊形網格：Uber
這是我沒有參與的最後一個項目，但是我發現並使用了基於它的工具。在這裡，我了解了一種新的數據結構：帶有層次化索引的六邊形網格。
Uber 要解決的最困難和最有趣的問題之一就是優化行程價格以及合作夥伴的調度。價格是動態的，驅動程序也在不斷變化。H3 是 Uber 工程師構建的網格系統，旨在以越來越細化的水平可視化和分析整個城市的數據。數據可視化結構就是帶有層次化索引的六邊形網格。
總結
這些是我多年來在多家公司中實際使用的算法和數據結構的重點。
要在一家高科技公司工作，你不需要了解流行算法或是外來數據結構的工作原理。你應該了解算法是什麼，並且能夠自己提出一些簡單的算法，例如貪婪算法。你還應該了解更多常見的基本數據結構，例如哈希表、隊列、棧等等。但是你不需要記住 Dijkstra 或者 A* 這樣特殊的算法。
你可以將它們作為參考，就像我實現加密算法時一樣。對待紅黑樹或 AVL 樹等一些不常見的數據結構也應如此。我從未用過這些數據結構。即使我用過，也不會反覆查看它們。我也從來沒有問過需要使用這些知識才能解決的問題，將來也不會。
我一直在尋求一些實際的編碼例子，因為實際的例子中會有很多好的解決方案，比如暴力枚舉、貪心算法或其他一些更複雜的算法。比如，有些問題，你只需要一個數組和一些 if/else 語句就可以解決問題，而無需任何複雜的數據結構。
現實情況是，許多團隊和公司都面臨算法的挑戰。應該看到，算法問題具有很大的吸引力，它們能夠在 45 分鐘或者更短的時間內給出信號，並且輕鬆地轉換問題。因此問題洩漏帶來的影響並不會很嚴重。
招聘也比較容易。因為你可以擁有 100 多個問題的問題庫，任何面試官都可以評估其中的任何一個。特別是在矽谷，聽到動態編程和特殊數據結構問題的情況越來越多。這些問題將有助於聘請強大的工程師，但同時也會導致將那些本不需了解一些複雜算法但卻非常優秀的人拒之門外。
原文連結：https://blog.pragmaticengineer.com/data-structures-and-algorithms-i-actually-used-day-to-day/