匹配HTTP路由的最佳算法

-4

我正在構建自己的http路由器，我想知道什麼算法最適合以某種數據格式註冊路徑，然後以最快的方式將其與http路由請求進行匹配。我做了一個Radix Tree，速度相當快，與路線相匹配的時間不到1ms，但我沒有大量的路線註冊，我相信（無知）有更快的方法。匹配HTTP路由的最佳算法

例如，讓我們採取一些URI路徑：

/你好
/搜索
/支持
/用戶/資料/（串）
/用戶/資訊
/post /（int）/ view /（string）

我基數樹是這樣做的：

/    
    ├s    
    |├earch   
    |└upport 
    |  
    ├user\   
    | └info 
    | └profile/ 
    |    └:string 
    ├post\  
    |  └:int\/ 
    |   └/view/ 
    |    └/:string 
    └hello

怎麼看的這棵樹，你的東西，有什麼我可以做的更好？

感謝您的閱讀

來源

2014-07-16 Gaël Reyrol

你的問題有點不清楚。請向我們提供更完整的問題描述，幷包含一些代碼：工作代碼或僞代碼，概述您使用的算法。如果沒有這兩者，就很難爲您的問題提供有用的答案。 –

感謝您的建議 –

基數樹實際上是一種很好的實現方法。根據您實施節點的方式，您可能會以某些空間爲代價加速實現。

如果你定義一個節點：

Class Node 
{ 
    public string Name; 
    public List<Node> Children; 
}

然後，你必須做孩子們依次搜索，找到一個匹配段。如果任何節點的子節點數量相對較少，那很好。如果每個節點有大量的孩子，那麼您可能需要用Dictionary<string, Node>替換List<Node>。這將加快查找速度。

除此之外，我想不出你描述的情況更合適的數據結構。

來源

2014-07-16 17:19:58

在dictonnary中應該使用什麼類型的數據作爲字符串參考？避免任何衝突。 –

@Zevran：由於每個節點都有一個子字典，字符串就是該段。例如，在你的例子中，你有一個名爲「user」的頂級節點，它有子節點「info」和「profile」。因此，在頂級字典中，您將擁有「用戶」條目，並且在「用戶」節點中，子字典將具有鍵「info」和「profile」的條目。沒有衝突的機會，因爲字典都是分開的。 –

匹配HTTP路由的最佳算法

回答

相關問題