Documentation ¶
Overview ¶
Package treap implements a persistent treap (tree/heap combination).
https://en.wikipedia.org/wiki/Treap
A treap is a binary search tree for storing ordered distinct values (duplicates not allowed). In addition, each node actually a random priority field which is stored in heap order (i.e. all children have lower priority than the parent)
This provides the basis for efficient immutable ordered Set operations. See the ordered map example for how this can be used as an ordered map
Much of this is based on "Fast Set Operations Using Treaps" by Guy E Blelloch and Margaret Reid-Miller: https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf
Benchmark ¶
The most interesting benchmark is the performance of insert where a single random key is inserted into a 5k sized map. As the example shows, the treap structure does well here as opposed to a regular persistent map (which involves full copying). This benchmark does not take into account the fact that the regular maps are not sorted unlike treaps.
The intersection benchmark compares the case where two 10k sets with 5k in common being interesected. The regular persistent array is about 30% faster but this is still respectable showing for treaps.
$ go test --bench=. -benchmem goos: darwin goarch: amd64 pkg: github.com/perdata/treap BenchmarkInsert-4 1000000 2347 ns/op 1719 B/op 36 allocs/op BenchmarkInsertRegularMap-4 2000 890745 ns/op 336311 B/op 8 allocs/op BenchmarkIntersection-4 500 3125772 ns/op 1719838 B/op 35836 allocs/op BenchmarkIntersectionRegularMap-4 500 2436519 ns/op 718142 B/op 123 allocs/op BenchmarkUnion-4 1000 1451047 ns/op 939846 B/op 19580 allocs/op BenchmarkDiff-4 500 3280823 ns/op 1742080 B/op 36298 allocs/op PASS
Example (OrderedMap) ¶
package main import ( "fmt" "github.com/perdata/treap" "math/rand" ) type pair struct { key, value interface{} } type comparer func(kv1, kv2 pair) int func (c comparer) Compare(v1, v2 interface{}) int { return c(v1.(pair), v2.(pair)) } type Map struct { *treap.Node treap.Comparer } func NewMap(keyCompare treap.Comparer) Map { c := comparer(func(v1, v2 pair) int { return keyCompare.Compare(v1.key, v2.key) }) return Map{nil, c} } func (m Map) Get(key interface{}) (interface{}, bool) { n := m.Find(pair{key, nil}, m.Comparer) if n == nil { return nil, false } return n.Value.(pair).value, true } func (m Map) Set(key, value interface{}) Map { node := &treap.Node{pair{key, value}, rand.Intn(1000000), nil, nil} n := m.Node.Union(node, m.Comparer, true) return Map{n, m.Comparer} } func (m Map) Delete(key interface{}) Map { n := m.Node.Delete(pair{key, nil}, m.Comparer) return Map{n, m.Comparer} } func (m Map) ForEach(fn func(key, value interface{})) { m.Node.ForEach(func(v interface{}) { p := v.(pair) fn(p.key, p.value) }) } func (m Map) Count() int { result := 0 m.Node.ForEach(func(_ interface{}) { result++ }) return result } func main() { rand.Seed(42) m := NewMap(IntComparer{}) fmt.Println("Count:", m.Count()) m = m.Set(52, "hello") m = m.Set(53, "world") m = m.Set(52, "Hello") m.ForEach(func(k, v interface{}) { fmt.Println("[", k, "] =", v) }) fmt.Println("Count:", m.Count()) old := m.Set(500, 500) m = m.Delete(53) fmt.Println(m.Get(53)) fmt.Println(old.Get(53)) fmt.Println(old.Get(52)) fmt.Println(old.Get(500)) }
Output: Count: 0 [ 52 ] = Hello [ 53 ] = world Count: 2 <nil> false world true Hello true 500 true
Index ¶
- type Comparer
- type Node
- func (n *Node) Delete(v interface{}, c Comparer) *Node
- func (n *Node) Diff(other *Node, c Comparer) *Node
- func (n *Node) Find(v interface{}, c Comparer) *Node
- func (n *Node) ForEach(fn func(v interface{}))
- func (n *Node) Intersection(other *Node, c Comparer) *Node
- func (n *Node) Split(v interface{}, c Comparer) (left, mid, right *Node)
- func (n *Node) Union(other *Node, c Comparer, overwrite bool) *Node
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparer ¶
type Comparer interface {
Compare(left, right interface{}) int
}
Comparer compares two values. The return value is zero if the values are equal, negative if the first is smaller and positive otherwise.
type Node ¶
Node is the basic recursive treap data structure
func (*Node) ForEach ¶
func (n *Node) ForEach(fn func(v interface{}))
ForEach does inorder traversal of the treap
func (*Node) Intersection ¶
Intersection returns a new treap with all the common values in the two treaps.
see https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf "Fast Set Operations Using Treaps"
by Guy E Blelloch and Margaret Reid-Miller.
The algorithm is a very slight variation on that.