README
¶
Immutable data structures for Go
- Based on a immutable persistent Hash Array Mapped Trie (HAMT)
- Minimal interface to the core HAMT implementation so that you can easily implement your own structures on top of it.
- Comes with some set and map implementations ready to go
- Inspired by Clojure's data structures
- Excellent performance (lookup is about the same as native go maps, insertion about 20% that of mutable native go maps.)
Example:
package main
import (
"fmt"
"github.com/rsms/go-immutable"
)
m := immutable.EmptyStrMap
m1 := m.Set("Hello", 123)
m2 := m.Set("Hello", 456).Set("Sun", 9)
m3 := m2.Del("Hello")
fmt.Printf("m1: %s\n", m1)
fmt.Printf("m2: %s\n", m2)
fmt.Printf("m3: %s\n", m3)
// Output:
// m1: {"Hello": 123}
// m2: {"Sun": 9, "Hello": 456}
// m3: {"Sun": 9}
Benchmark
TEST SAMPLES TIME PER ITERATION
BenchmarkHamtLookup_10 48042776 23.8 ns/op
BenchmarkHamtLookup_100 36947116 31.0 ns/op
BenchmarkHamtLookup_1000 32566189 34.8 ns/op
BenchmarkHamtLookup_10000 24775086 49.1 ns/op
BenchmarkGoMapLookup_10 69836985 16.3 ns/op
BenchmarkGoMapLookup_100 66960720 16.5 ns/op
BenchmarkGoMapLookup_1000 36865258 30.7 ns/op
BenchmarkGoMapLookup_10000 28110822 43.3 ns/op
BenchmarkHamtInsert_10 8019391 137.0 ns/op
BenchmarkHamtInsert_25 6851881 174.0 ns/op
BenchmarkHamtInsert_50 5419015 221.0 ns/op
BenchmarkHamtInsert_100 3860596 293.0 ns/op
BenchmarkHamtInsert_1000 2596484 469.0 ns/op
BenchmarkHamtInsert_5000 1892996 644.0 ns/op
BenchmarkGoMapInsert_10 17940093 66.5 ns/op
BenchmarkGoMapInsert_25 13996856 74.3 ns/op
BenchmarkGoMapInsert_50 14645752 83.3 ns/op
BenchmarkGoMapInsert_100 14309284 82.8 ns/op
BenchmarkGoMapInsert_1000 10754890 106.0 ns/op
BenchmarkGoMapInsert_5000 11948517 100.0 ns/op
Results are from a 2018 MacBook Pro.
BenchmarkHamt* and BenchmarkGo* are tests with same input using HAMT and native Go maps,
respectively.
Run these benchmarks yourself with ./dev -bench.
Keep in mind that HAMT is immutable and derivative data structure which requires lots of memory allocations, compared to the mutable in-place native go maps. I've chosen to compare the HAMT implementation with Go maps since Go maps are likely what you are familiar with. :-)
Documentation
¶
Overview ¶
Example (StrMap) ¶
m := EmptyStrMap
m1 := m.Set("Hello", 123)
m2 := m.Set("Hello", 456).Set("Sun", 9)
m3 := m2.Del("Hello")
fmt.Printf("m1: %s\n", m1)
fmt.Printf("m2: %s\n", m2)
fmt.Printf("m3: %s\n", m3)
Output: m1: {"Hello": 123} m2: {"Sun": 9, "Hello": 456} m3: {"Sun": 9}
Example (StrSet) ¶
s1 := EmptyStrSet
s2 := s1.Add("Robin")
s1 = s1.Add("Anne").Add("Frank")
s3 := s1.Del("Anne")
fmt.Printf("s1: %s\n", s1)
fmt.Printf("s2: %s\n", s2)
fmt.Printf("s3: %s\n", s3)
Output: s1: {Frank, Anne} s2: {Robin} s3: {Frank}
Index ¶
- Variables
- type HAMT
- type Set
- type StrKeyValue
- type StrMap
- func (m *StrMap) Del(key string) *StrMap
- func (m *StrMap) Get(key string) interface{}
- func (m *StrMap) GetCheck(key string) (interface{}, bool)
- func (m *StrMap) GoString() string
- func (m *StrMap) Has(key string) bool
- func (m *StrMap) Range(f func(key string, value interface{}) bool)
- func (m *StrMap) Set(key string, value interface{}) *StrMap
- func (m *StrMap) String() string
- type StrSet
- type StrValue
- type Value
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var EmptyHAMT = &HAMT{}
var EmptySet = &Set{0, EmptyHAMT}
The empty Set
var EmptyStrMap = &StrMap{0, EmptyHAMT}
The empty StrMap
var EmptyStrSet = &StrSet{0, EmptyHAMT}
The empty StrSet
Functions ¶
This section is empty.
Types ¶
type HAMT ¶
type HAMT struct {
// contains filtered or unexported fields
}
HAMT implements an immutable persistent Hash Array Mapped Trie
func (*HAMT) Insert ¶
Insert returns a new HAMT with value v. resized is decremented by 1 in case the operation replaced an existing entry.
func (*HAMT) Range ¶
Range calls f for every entry in the HAMT. If f returns false iteration stops. Returns the return value of f.
type Set ¶
type Set struct {
Len int // number of entries
// contains filtered or unexported fields
}
Set stores Value objects in a HAMT structure
type StrKeyValue ¶
type StrKeyValue struct {
StrValue
V interface{}
}
StrKeyValue is a type of Value with a string key and interface value
func NewStrKeyValue ¶
func NewStrKeyValue(key string, value interface{}) *StrKeyValue
func (*StrKeyValue) Equal ¶
func (e *StrKeyValue) Equal(b Value) bool
func (*StrKeyValue) Key ¶
func (e *StrKeyValue) Key() string
func (*StrKeyValue) SetKey ¶
func (e *StrKeyValue) SetKey(key string)
func (*StrKeyValue) SetValue ¶
func (e *StrKeyValue) SetValue(v interface{})
func (*StrKeyValue) String ¶
func (e *StrKeyValue) String() string
func (*StrKeyValue) Value ¶
func (e *StrKeyValue) Value() interface{}
type StrMap ¶
type StrMap struct {
Len int // number of entries
// contains filtered or unexported fields
}
StrMap stores string keys associated with any value in a HAMT structure
func (*StrMap) GetCheck ¶
GetCheck finds value for key and returns a boolean indicating success. Useful alternative to Get in case nil values are stored in the map.
func (*StrMap) GoString ¶
GoString returns a Go value representation in the format {{key, value}, ...}
func (*StrMap) Range ¶
Range iterates over all entries by calling f(k,v). If f returns false, iteration stops.
type StrSet ¶
type StrSet struct {
Len int // number of entries
// contains filtered or unexported fields
}
StrSet stores strings in a HAMT structure
type Value ¶
type Value interface {
// Hash should return a "as unique as possible" integer for the "key" of the value
Hash() uint
// Equal should return true if the other value's key is equivalent to the receiver
Equal(Value) bool
}
Value defines the operations that must be implemented for the value type of a HAMT
Source Files