go-trie-tst

Trie and Ternary Search Tree implemented in Golang

Trie outperforms TST slightly in CPU time, but costs much much more memory according to heap pprof. So I think TST is more suitable in production.

Performance

CPU Profile:

Trie    200000	      9964 ns/op
TST     200000	     10339 ns/op

Heap Profile:

(pprof) top50
1221.12MB of 1222.12MB total (99.92%)
Dropped 42 nodes (cum <= 6.11MB)
      flat  flat%   sum%        cum   cum%
 1193.62MB 97.67% 97.67%  1193.62MB 97.67%  github.com/xiaonanln/go-trie-tst.(*Trie).Set.func1
   27.50MB  2.25% 99.92%    27.50MB  2.25%  github.com/xiaonanln/go-trie-tst.(*TST).Child
         0     0% 99.92%    27.50MB  2.25%  github.com/xiaonanln/go-trie-tst.(*TST).Set
         0     0% 99.92%    27.50MB  2.25%  github.com/xiaonanln/go-trie-tst.(*TST).Set.func1
         0     0% 99.92%  1193.62MB 97.67%  github.com/xiaonanln/go-trie-tst.(*Trie).Set
         0     0% 99.92%  1221.12MB 99.92%  main.testRoutine
         0     0% 99.92%  1222.12MB   100%  runtime.goexit

Usage

import "github.com/xiaonanln/go-trie-tst"

var tr trietst.TST // create a TST
tr.Set("", 0) // set "" to 0
tr.Set("abc", 3) // set "abc" to 3
tr.Get("") // == 0
tr.Get("a") // == nil
tr.Get("ab") // == nil
tr.Get("abc") // == 3

subtr = tr.Sub("ab") // get sub TST under "ab"
subtr.Get("") // == nil
subtr.Get("a") // == nil
subtr.Get("b") // == nil
subtr.Get("c") // == 3, because "abc" == 3