trietst

README

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

Documentation

Index

• type TST
  • func (t *TST) Child(c byte) *TST
  • func (t *TST) ForEach(f func(s string, val interface{}))
  • func (t *TST) Get(s string) (val interface{})
  • func (t *TST) Set(s string, val interface{})
  • func (t *TST) Sub(s string) *TST
• type Trie
  • func (t *Trie) Child(c byte) *Trie
  • func (t *Trie) ForEach(f func(s string, val interface{}))
  • func (t *Trie) Get(s string) (val interface{})
  • func (t *Trie) Set(s string, val interface{})
  • func (t *Trie) Sub(s string) *Trie
• type TrieMO
  • func (t *TrieMO) Child(c byte) *TrieMO
  • func (t *TrieMO) ForEach(f func(s string, val interface{}))
  • func (t *TrieMO) Get(s string) (val interface{})
  • func (t *TrieMO) Set(s string, val interface{})
  • func (t *TrieMO) Sub(s string) *TrieMO

Types

type TST

type TST struct {
	Val interface{}
	// contains filtered or unexported fields
}

TST can be the root, and can be a sub-tree

func (*TST) Child

func (t *TST) Child(c byte) *TST

Child returns the child subtree of the current tree

func (*TST) ForEach

func (t *TST) ForEach(f func(s string, val interface{}))

func (*TST) Get

func (t *TST) Get(s string) (val interface{})

Get returns the value of string in the current tree

func (*TST) Set

func (t *TST) Set(s string, val interface{})

Set sets the value of string in the current tree

func (*TST) Sub

func (t *TST) Sub(s string) *TST

Sub returns the subtree of the current tree with specified prefix

type Trie

type Trie struct {
	Val interface{}
	// contains filtered or unexported fields
}

Trie can be the root, and can be a sub-tree

func (*Trie) Child

func (t *Trie) Child(c byte) *Trie

Child returns the child subtree of the current tree

func (*Trie) ForEach

func (t *Trie) ForEach(f func(s string, val interface{}))

func (*Trie) Get

func (t *Trie) Get(s string) (val interface{})

Get returns the value of string in the current tree

func (*Trie) Set

func (t *Trie) Set(s string, val interface{})

Set sets the value of string in the current tree

func (*Trie) Sub

func (t *Trie) Sub(s string) *Trie

Sub returns the subtree of the current tree with specified prefix

type TrieMO

type TrieMO struct {
	Val interface{}
	// contains filtered or unexported fields
}

TrieMO can be the root, and can be a sub-tree

func (*TrieMO) Child

func (t *TrieMO) Child(c byte) *TrieMO

Child returns the child subtree of the current tree

func (*TrieMO) ForEach

func (t *TrieMO) ForEach(f func(s string, val interface{}))

func (*TrieMO) Get

func (t *TrieMO) Get(s string) (val interface{})

Get returns the value of string in the current tree

func (*TrieMO) Set

func (t *TrieMO) Set(s string, val interface{})

Set sets the value of string in the current tree

func (*TrieMO) Sub

func (t *TrieMO) Sub(s string) *TrieMO

Sub returns the subtree of the current tree with specified prefix