Skip to content
forked from falmar/goradix

Radix Tree Implementation with Golang

License

Notifications You must be signed in to change notification settings

imdszxs/goradix

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

62 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

GoRadix Build Status Codecov

Radix Tree implementation written in Golang.

Thread Safety is optional. You will need to pass a boolean value when creating the Radix Tree

  • true: thread safe
  • false: non thread safe

Radix Tree

In computer science, a radix tree (also radix trie or compact prefix tree) is a data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent. - Wikipedia

Content

Usage:

Download: go get github.com/falmar/goradix

Import import "github.com/falmar/goradix"

Insert

// string required, value (optional)
func (r *Radix) Insert(s string, value ...interface{}){...}
package main

import "github.com/falmar/goradix"

func main() {
	radix := goradix.New(false)

  // Simple string insert
	radix.Insert("romanus")
	radix.Insert("romane")
	radix.Insert("romulus")
}

LookUp

// string required
func (r *Radix) LookUp(s string) (interface{}, error) {...} {...}
package main

import (
	"fmt"

	"github.com/falmar/goradix"
)

func main() {
	radix := goradix.New(false)
	radix.Insert("romanus", 1)
	radix.Insert("romane", 100)
	radix.Insert("romulus", 1000)

	value, err := radix.LookUp("romane")

	if err != nil { // No Match Found
		return
	}

	// Output: Found node, Value: 100
	fmt.Println("Found node, Value: ", value)
}

Remove

// string
func (r Radix) Remove(s string) (bool) {...}
package main

import (
	"fmt"

	"github.com/falmar/goradix"
)

func main() {
	radix := goradix.New(false)

	radix.Insert("romanus")
	radix.Insert("romane")
	radix.Insert("romulus")

	succeed := radix.Remove("romulus")

	fmt.Println(succeed) // true
}

AutoComplete

// string, bool required
func (r Radix) AutoComplete(s string, wholeWord bool) ([]string, error) {...}
package main

import (
	"fmt"

	"github.com/falmar/goradix"
)

func main() {
	radix := goradix.New(false)
	radix.Insert("romanus", 1)
	radix.Insert("romane", 100)
	radix.Insert("romulus", 1000)

	// Return remaining text
	words, err := radix.AutoComplete("ro", false)

	if err != nil { // No Match Found
		return
	}

	// Output: AutoComplete 'rom'; Words: [manus mane mulus]
	fmt.Printf("AutoComplete: '%s'; Words: %v\n", "ro", words)

	// Return whole words
	words, _ = radix.AutoComplete("ro", true)

	// Output: AutoComplete 'rom'; Words: [romanus romane romulus]
	fmt.Printf("AutoComplete: '%s'; Words: %v\n", "ro", words)
}

Benchmarks

Non Thread Safe
Go 1.6

BenchmarkInsertNTS-2	 1000000	      1736 ns/op	     279 B/op	       8 allocs/op
BenchmarkLookUpNTS-2	 2000000	       628 ns/op	       0 B/op	       0 allocs/op
BenchmarkRemoveNTS-2	 2000000	       562 ns/op	       0 B/op	       0 allocs/op
Go 1.7

BenchmarkInsertNTS-2   	 2000000	      1056 ns/op	     279 B/op	       8 allocs/op
BenchmarkLookUpNTS-2   	 3000000	       435 ns/op	       0 B/op	       0 allocs/op
BenchmarkRemoveNTS-2   	 3000000	       539 ns/op	       0 B/op	       0 allocs/op
Thread Safe
Go 1.6

BenchmarkInsertTS-2	 1000000	      1619 ns/op	     279 B/op	       8 allocs/op
BenchmarkLookUpTS-2	 1000000	      1018 ns/op	       0 B/op	       0 allocs/op
BenchmarkRemoveTS-2	 1000000	      1181 ns/op	       0 B/op	       0 allocs/op
Go 1.7

BenchmarkInsertTS-2   	 1000000	      1018 ns/op	     279 B/op	       8 allocs/op
BenchmarkLookUpTS-2   	 3000000	       553 ns/op	       0 B/op	       0 allocs/op
BenchmarkRemoveTS-2   	 2000000	       651 ns/op	       0 B/op	       0 allocs/op

Benchmark machine

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                2
On-line CPU(s) list:   0,1
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             2
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 62
Model name:            Intel(R) Xeon(R) CPU E5-2630L v2 @ 2.40GHz
Stepping:              4
CPU MHz:               2399.998
BogoMIPS:              4799.99
Virtualization:        VT-x
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              15360K
NUMA node0 CPU(s):     0,1

Contribution

Any contribution is more than welcome.

License

MIT.

About

Radix Tree Implementation with Golang

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Go 100.0%