練習 24：URL 快速路由
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
我們將結束數據結構和算法的部分巾遭，并將數據結構用于實際問題。我已經寫了幾個 Web 服務器，一個不斷出現(xiàn)的問題是，將 URL 路徑匹配到“動作”。你會在每個 Web 框架咐熙，Web 服務器，和必須基于層次化的鍵來“路由”信息的任何東西中發(fā)現(xiàn)此問題。當你的 Web 服務器收到URL /do/this/stuff/時箩做，必須確定每個部分是否可能附加了某種操作或配置。如果你在/do/配置了 Web 應用程序妥畏，那么你的網絡服務器應該使用/this/stuff/做什么呢邦邦？是否認為它是失敗的，或將其傳遞給 Web 應用程序醉蚁？如果/do/this/中有一個目錄怎么辦燃辖？而且，如何快速檢測到錯誤的 URL网棍，因此你不必處理不存在的巨大請求黔龟？
這種層次化的搜索經常出現(xiàn)，這是對你將算法和數據結構應用于問題的能力滥玷，以及性能分析能力進行測試的最佳測試氏身。
挑戰(zhàn)練習
首先，請確定你了解 URL 是什么以及如何使用惑畴。如果沒有蛋欣，那么我建議你花時間去寫一個帶有一些復雜路由的小型 Flask 應用程序。這是你將要實現(xiàn)的路由如贷。
接下來陷虎，你應該執(zhí)行以下操作：
- 創(chuàng)建一個簡單的基本的
URLRouter類到踏，你將為所有實現(xiàn)派生它。你應該可以對此URLRouter執(zhí)行以下操作：- 添加一個帶有關聯(lián)對象的新 URL尚猿。
- 獲取 URL 的完全匹配窝稿。搜索
/DO/THIS/STUFF/只返回正好是它的東西。 - 獲取 URL 的最佳匹配谊路。搜索
/DO/THIS/STUFF/將匹配/DO/讹躯，如果這是唯一的匹配。 - 獲取以此 URL 開頭的所有對象缠劝。
- 獲取 URL 的最短匹配對象潮梯。搜索
/DO/THIS/STUFF/會返回/DO/而不是/DO/THIS/。 - 獲取 URL 的最長匹配對象惨恭。搜索
/DO/THIS/STUFF/將返回/DO/THIS/而不是/DO/秉馏。
- 使用
TSTree創(chuàng)建URLRouter的子類，因為這樣最容易了脱羡。確保測試了下面這些事情：- 不同長度的隨機 URL 和路徑萝究，在
TSTREE和你搜索的內容里面。 - 在不同情況下只尋找部分路徑
- 完全不存在的路徑
- 不同長度的隨機 URL 和路徑萝究，在
- 存在和不存在的非常長的路徑
- 一旦你讓這個子類工作锉罐，并測試完畢帆竹，推廣你的測試，所以你可以在所有打算完成的實現(xiàn)中運行它脓规。
- 然后栽连，嘗試使用
DoubleLinkedList，BSTree侨舆，Dictionary和 Python 的dict來實現(xiàn)秒紧。確保你的泛用測試適用于所有這些。 - 一旦完成了挨下，開始分析這些實現(xiàn)的不同操作的性能熔恢。
目標是看看與其他數據結構相比，TSTree有多快臭笆。它可能會擊敗大多數東西叙淌，但也許 Python dict多數情況會贏，因為它針對 Python 進行了優(yōu)化愁铺。你甚至可以為每個操作猜測凿菩，哪個數據結構具有最佳性能。
研究性學習
- 我省略了
SuffixArray帜讲，因為它類似于TSTree衅谷，但為了使用它，你必須添加相同的操作似将。實現(xiàn)它获黔，然后看看SuffixArray如何比較蚀苛。 - 研究你最喜歡的 Web 服務器或 Web 框架是如何實現(xiàn)的。你會發(fā)現(xiàn)很多使用 URL 人不知道什么是三叉搜索樹玷氏，盡管它對于常見操作非常有用堵未。
深入學習
如果你想深入了解算法和數據結構，我強烈推薦 Steven S. Skiena 的《The Algorithm Design Manual》一書盏触。他的書使用 C渗蟹，所以你可能需要先閱讀《笨辦法學 C》，以便能夠瀏覽它赞辩。除此之外雌芽，它是一本很好的書，因為它涵蓋了分析算法和數據結構的性能的理論和實現(xiàn)辨嗽。
