Closed yunyet closed 11 years ago
BenchmarkNoCompression 50000 31261 ns/op BenchmarkCompression 100000 17851 ns/op BenchmarkRegExpLoop 2000 749542 ns/op BenchmarkFixedAndRegExp 5000 516629 ns/op BenchmarkCacheRegExp 5000000 418 ns/op BenchmarkMapOnly 5000000 581 ns/op
So, I think trie
should be much improved if changed by map
instead of dealing char ony by one.
A map is definitely faster than this trie. But the whole pourpose of this trie is to support variable parts in the path. Like "/stock/:id" than would match "/stock/AAPL" for instance. (and gives you id="AAPL") It works by first making a prefix tree, char by char, and then "compressing" the tree when possible.
BTW, this package has been merged in https://github.com/ant0ine/go-json-rest, where it has been improved and specialized for the REST API use case.
Good work!
Thanks!
This test shows the chaos:
` func TestFindRouteMultipleMatches(t *testing.T) {
}
func (self *Trie) Travel() { fmt.Println("---------------") self.root.LFirstTravel("") }
func (self *node) LFirstTravel(tab string) { if self.Children == nil { return } tab = "\t" + tab for k, v := range self.Children { fmt.Printf("%s%v \n", tab, k) v.LFirstTravel(tab) } } `
And why compressed like this is more efficient than uncompressed according to your blog? So, map must be more efficient than trie.