如果路由都只是 url 字符串完全匹配的,我可以用 hashmap ,理想情况 O(1) 复杂度。
但是我想在 url 匹配中支持 通配符,那么最简单的实现方法,我就直接用正则了,但是匹配复杂度就变成 O(n)了,这样感觉不是很好。。。
如何解决这个问题
巴扎黑2017-04-18 09:50:46
ルーティング アドレスを保存するためにツリーを使用してみてはいかがでしょうか?
図に示すように、各ボックスはマップです
/user/111/profile/books/222 をリクエストするときは、最初に URL を分割してください
['/' , '111' , 'profile' , 'books' , '222']
まず最初の層に / ノードがあるかどうかを検索します
次に 111 ノードがあるかどうかを検索します2 番目のレイヤーにない場合は、 * ノード
を入力し、検索した 3 番目のレイヤーにプロファイル ノード
があるかどうかを確認します。
PHP中文网2017-04-18 09:50:46
https://github/bephp/router
このプロジェクトは正規表現を使用せず、URLを「/」で切り取ってツリー構造に保存します。
ルートをマッピングする場合、それはツリーを横断することと等価であり、複雑さは O (log n) です。
プロジェクトは PHP で実装されていますが、コードは非常に小さいです。理解しやすいはずです。
黄舟2017-04-18 09:50:46
ルーティングにおける正規表現によって示される柔軟性は、他のテクノロジーで置き換えるのが困難です。通常のルールを使用してパフォーマンスを最適化することもできます。原理は非常に簡単で、通常のルールを組み合わせて、どの
が通常の一致結果に基づいて決定されるかということです。たとえば、
があります。/user/{pid}/profile
/ニュース
/product/{pid}
/product/{pid}/comment/{cid}
4つのルート
正規表現 #^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#
を使用して
キャプチャ結果にそれぞれ 1、0、2、3 グループが含まれている場合、1 番目から 4 番目のルートがそれぞれ一致したことがわかります。正規表現を何らかのコードと自動的にマージし、キャプチャ グループ => ルーティング マッピングの数を割り当てることで、複数の正規表現を 1 つの一致に対してマージできます
ここでは、(?|)
を使用してキャプチャ グループをリセットする方法を紹介します
参考 http://nikic.github.io/2014/0...