作者tonytonyjan (南洋大兜虫)
看板Programming
标题[问题] URL Routing 适合的演算法
时间Sat May 2 00:11:53 2015
不知道大家觉得针对网址路由的问题，
觉得使用 Trie 适合，还是 B+ tree、TS-Tree 亦或是单纯 hash 比较好呢？
我看 c9s 开发的 r3, 与 pux 分别使用 trie 和 indexed array 去解，
但不明白其中的奥秘。
乍看是觉得 indexed array 可以得到 O(1) 的效能，而 trie 则是省空间。
例如：/users/tony, /users/tom, /users/toto 这三个路径若用 trie 的话，
前缀可以共用节点。
但是现在记忆体越来越大，对於网址路由这件事情，真的有需要用到 trie
来解吗？
抑或 trie 有哪些神奇之处是我还没有察觉的？
any idea？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.219.118.91
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Programming/M.1430496717.A.E95.html
※ 编辑: tonytonyjan (61.219.118.91), 05/02/2015 00:25:24
1F：推 abcdefghi: 不能只看O(),也要算cache miss penalty 114.44.188.208 05/02 10:47