# 練習 24：URL 快速路由 > 原文：[Exercise 24: Fast URL Search](https://learncodethehardway.org/more-python-book/ex24.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 我們將結束數據結構和算法的部分，并將數據結構用于實際問題。我已經寫了幾個 Web 服務器，一個不斷出現的問題是，將 URL 路徑匹配到“動作”。你會在每個 Web 框架，Web 服務器，和必須基于層次化的鍵來“路由”信息的任何東西中發現此問題。當你的 Web 服務器收到URL `/do/this/stuff/`時，必須確定每個部分是否可能附加了某種操作或配置。如果你在`/do/`配置了 Web 應用程序，那么你的網絡服務器應該使用`/this/stuff/`做什么呢？是否認為它是失敗的，或將其傳遞給 Web 應用程序？如果`/do/this/`中有一個目錄怎么辦？而且，如何快速檢測到錯誤的 URL，因此你不必處理不存在的巨大請求？ 這種層次化的搜索經常出現，這是對你將算法和數據結構應用于問題的能力，以及性能分析能力進行測試的最佳測試。 ## 挑戰練習 首先，請確定你了解 URL 是什么以及如何使用。如果沒有，那么我建議你花時間去寫一個帶有一些復雜路由的小型 Flask 應用程序。這是你將要實現的路由。 接下來，你應該執行以下操作： + 創建一個簡單的基本的`URLRouter`類，你將為所有實現派生它。你應該可以對此`URLRouter`執行以下操作： + 添加一個帶有關聯對象的新 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 `創建`URLRouter `的子類，因為這樣最容易了。確保測試了下面這些事情： + 不同長度的隨機 URL 和路徑，在`TSTREE`和你搜索的內容里面。 + 在不同情況下只尋找部分路徑 + 完全不存在的路徑 + 存在和不存在的非常長的路徑 + 一旦你讓這個子類工作，并測試完畢，推廣你的測試，所以你可以在所有打算完成的實現中運行它。 + 然后，嘗試使用`DoubleLinkedList`，`BSTree`，`Dictionary`和 Python 的`dict`來實現。確保你的泛用測試適用于所有這些。 + 一旦完成了，開始分析這些實現的不同操作的性能。 目標是看看與其他數據結構相比，`TSTree`有多快。它可能會擊敗大多數東西，但也許 Python `dict`多數情況會贏，因為它針對 Python 進行了優化。你甚至可以為每個操作猜測，哪個數據結構具有最佳性能。 ## 研究性學習 + 我省略了`SuffixArray`，因為它類似于`TSTree`，但為了使用它，你必須添加相同的操作。實現它，然后看看`SuffixArray`如何比較。 + 研究你最喜歡的 Web 服務器或 Web 框架是如何實現的。你會發現很多使用 URL 人不知道什么是三叉搜索樹，盡管它對于常見操作非常有用。 ## 深入學習 如果你想深入了解算法和數據結構，我強烈推薦 Steven S. Skiena 的[《The Algorithm Design Manual》](http://amzn.to/2qIA3ai)一書。他的書使用 C，所以你可能需要先閱讀《笨辦法學 C》，以便能夠瀏覽它。除此之外，它是一本很好的書，因為它涵蓋了分析算法和數據結構的性能的理論和實現。