From d28b47c43ef73efbe06f77acea077bee9ccec492 Mon Sep 17 00:00:00 2001 From: Paul Buetow Date: Sat, 5 Dec 2020 08:35:12 +0000 Subject: rename set to search --- Makefile | 4 +- search/balancedbst.go | 5 ++ search/bst.go | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++ search/elementary.go | 79 +++++++++++++++++++++++ search/set.go | 15 +++++ search/set_test.go | 130 ++++++++++++++++++++++++++++++++++++++ set/balancedbst.go | 5 -- set/bst.go | 171 -------------------------------------------------- set/elementary.go | 79 ----------------------- set/set.go | 15 ----- set/set_test.go | 130 -------------------------------------- 11 files changed, 402 insertions(+), 402 deletions(-) create mode 100644 search/balancedbst.go create mode 100644 search/bst.go create mode 100644 search/elementary.go create mode 100644 search/set.go create mode 100644 search/set_test.go delete mode 100644 set/balancedbst.go delete mode 100644 set/bst.go delete mode 100644 set/elementary.go delete mode 100644 set/set.go delete mode 100644 set/set_test.go diff --git a/Makefile b/Makefile index 805c341..854a379 100644 --- a/Makefile +++ b/Makefile @@ -10,8 +10,8 @@ sortbench: go test -run=xxx -bench=. ./sort | tee sortbench.out queuebench: go test -run=xxx -bench=. ./queue | tee queuebench.out -setbench: - go test -run=xxx -bench=. ./set | tee setbench.out +searchbench: + go test -run=xxx -bench=. ./search | tee searchbench.out profile: go test -run=xxx -bench=BenchmarkQuickSort ./sort -memprofile memprofile.out -cpuprofile cpuprofile.out go tool pprof cpuprofile.out diff --git a/search/balancedbst.go b/search/balancedbst.go new file mode 100644 index 0000000..12673c5 --- /dev/null +++ b/search/balancedbst.go @@ -0,0 +1,5 @@ +package set + +func NewBalancedBST() *BST { + return NewBST() +} diff --git a/search/bst.go b/search/bst.go new file mode 100644 index 0000000..0eecb9e --- /dev/null +++ b/search/bst.go @@ -0,0 +1,171 @@ +package set + +import "fmt" + +type node struct { + key int + val int + left *node + right *node +} + +func (n *node) String() string { + recurse := func(n *node) string { + if n == nil { + return "" + } + return n.String() + } + + return fmt.Sprintf("node{%d:%d,%s,%s}", + n.key, + n.val, + recurse(n.left), + recurse(n.right)) +} + +type BST struct { + root *node +} + +func NewBST() *BST { + return &BST{} +} + +func (t *BST) String() string { + if t.Empty() { + return "BST{}" + } + + return fmt.Sprintf("BST{%s}", t.root) +} + +func (t *BST) Empty() bool { + return t.root == nil +} + +func (t *BST) Set(key, val int) { + if t.Empty() { + t.root = &node{key, val, nil, nil} + return + } + ptr, _, err := t.search(&t.root, key) + switch err { + case nil: + // key already in the tree + return + case NotFound: + *ptr = &node{key, val, nil, nil} + return + default: + panic(err) + } +} + +func (t *BST) Get(key int) (int, error) { + _, n, err := t.search(&t.root, key) + if err != nil { + return 0, err + } + return n.val, nil +} + +func (t *BST) Del(key int) (int, error) { + ptr, n, err := t.search(&t.root, key) + if err != nil { + return 0, err + } + + // Case 1: n is leaf node + // Case 2: n has one child + // Case 3: n has two childs + + switch { + case n.left == nil: + if n.right == nil { + // I am a leaf node + *ptr = nil + return n.val, nil + } + // I have a right child + *ptr = n.right + return n.val, nil + + case n.right == nil: + // I have a left child + *ptr = n.left + return n.val, nil + default: + // I have two children! + + o, err := t.deleteMin(&n.right) + if err != nil { + return 0, err + } + + o.left = n.left + o.right = n.right + *ptr = o + + return n.val, nil + } +} + +func (t *BST) search(ptr **node, key int) (**node, *node, error) { + n := *ptr + if n == nil { + return ptr, nil, NotFound + } + + switch { + case key < n.key: + return t.search(&n.left, key) + case n.key < key: + return t.search(&n.right, key) + default: + return ptr, n, nil + } +} + +func (t *BST) deleteMin(ptr **node) (*node, error) { + ptr, n, err := t.min(ptr) + if err != nil { + return nil, err + } + + *ptr = n.right + n.right = nil + return n, nil +} + +func (t *BST) min(ptr **node) (**node, *node, error) { + n := *ptr + if n == nil { + return nil, nil, NotFound + } + + for { + if n.left == nil { + return ptr, n, nil + } + ptr = &n.left + n = *ptr + } +} + +/* +func (t *BST) max(ptr **node) (**node, *node, error) { + n := *ptr + if n == nil { + return nil, nil, NotFound + } + + for { + if n.right == nil { + return ptr, n, nil + } + ptr = &n.right + n = *ptr + } +} +*/ diff --git a/search/elementary.go b/search/elementary.go new file mode 100644 index 0000000..a9d367e --- /dev/null +++ b/search/elementary.go @@ -0,0 +1,79 @@ +package set + +type ElementaryElem struct { + key int + val int + next *ElementaryElem +} + +type Elementary struct { + root *ElementaryElem +} + +func NewElementary() *Elementary { + return &Elementary{} +} + +func (s *Elementary) Empty() bool { + return s.root == nil +} + +func (s *Elementary) Set(key int, val int) { + if s.Empty() { + s.root = &ElementaryElem{key, val, nil} + return + } + + elem := s.root + + for { + if elem.key == key { + elem.val = val + return + } + if elem.next == nil { + elem.next = &ElementaryElem{key, val, nil} + return + } + elem = elem.next + } +} + +func (s *Elementary) Get(key int) (int, error) { + elem := s.root + + for elem != nil { + if elem.key == key { + return elem.val, nil + } + elem = elem.next + } + + return 0, NotFound +} + +func (s *Elementary) Del(key int) (int, error) { + if s.Empty() { + return 0, NotFound + } + + if s.root.key == key { + defer func() { + s.root = s.root.next + }() + return s.root.val, nil + } + + elem := s.root + for elem.next != nil { + if elem.next.key == key { + defer func() { + elem.next = elem.next.next + }() + return elem.next.val, nil + } + elem = elem.next + } + + return 0, NotFound +} diff --git a/search/set.go b/search/set.go new file mode 100644 index 0000000..29bfad7 --- /dev/null +++ b/search/set.go @@ -0,0 +1,15 @@ +package set + +import "fmt" + +var ( + NotFound = fmt.Errorf("could not find entry") + NotImplemented = fmt.Errorf("method not implemented") +) + +type Set interface { + Empty() bool + Set(key int, val int) + Get(key int) (int, error) + Del(key int) (int, error) +} diff --git a/search/set_test.go b/search/set_test.go new file mode 100644 index 0000000..098947d --- /dev/null +++ b/search/set_test.go @@ -0,0 +1,130 @@ +package set + +import ( + "fmt" + "testing" + + "github.com/snonux/algorithms/ds" + "github.com/snonux/algorithms/sort" +) + +const factor int = 10 +const minLength int = 1 +const maxLength int = 10000 + +// Store results here to avoid compiler optimizations +var benchResult int + +func TestElementary(t *testing.T) { + for i := minLength; i <= maxLength; i *= factor { + test(NewElementary(), i, t) + } +} + +func TestBST(t *testing.T) { + for i := minLength; i <= maxLength; i *= factor { + test(NewBST(), i, t) + } +} + +func test(s Set, l int, t *testing.T) { + keys := ds.NewRandomArrayList(l, l) + randoms := ds.NewRandomArrayList(l, -1) + mapping := make(map[int]int, l) + + get := func(key int, del bool) int { + var val int + var err error + switch { + case del: + defer delete(mapping, key) + val, err = s.Del(key) + //t.Log("Del", key, val, err) + default: + val, err = s.Get(key) + //t.Log("Get", key, val, err) + } + + if mVal, ok := mapping[key]; ok { + if err != nil { + t.Error("Could not get element", key, val, mVal, err) + } + if mVal != val { + t.Error("Got wrong value for element", key, val, mVal) + } + return val + } + + if err == nil { + t.Error("Got element but expected not to", key, val) + } + return val + } + testGet := func(key int) int { return get(key, false) } + testDel := func(key int) int { return get(key, true) } + + testSet := func(key, val int) { + s.Set(key, val) + mapping[key] = val + //t.Log("Set", key, val) + testGet(key) + } + + t.Log("Set random key-values", l) + var prevKey int + for _, key := range sort.Shuffle(keys) { + testSet(key, randoms[key]) + testGet(prevKey) + prevKey = key + } + t.Log("Del random key-values", l) + for _, key := range sort.Shuffle(keys) { + testDel(key) + testGet(prevKey) + prevKey = key + } + if !s.Empty() { + t.Error("Expected set to be empty", l) + } +} + +func TestBalancedBST(t *testing.T) { + for i := minLength; i <= maxLength; i *= factor { + test(NewBalancedBST(), i, t) + } +} + +func BenchmarkElementary(t *testing.B) { + s := NewElementary() + for i := minLength; i <= maxLength; i *= factor { + benchmark(s, i, t) + } +} + +func BenchmarkBST(t *testing.B) { + s := NewBST() + for i := minLength; i <= maxLength; i *= factor { + benchmark(s, i, t) + } +} + +func BenchmarkBalancedBST(t *testing.B) { + s := NewBalancedBST() + for i := minLength; i <= maxLength; i *= factor { + benchmark(s, i, t) + } +} + +func benchmark(s Set, l int, b *testing.B) { + list := ds.NewRandomArrayList(l, -1) + + b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) { + b.ResetTimer() + for i, a := range list { + s.Set(a, i) + } + for _, a := range list { + benchResult, _ = s.Get(a) + } + }) +} diff --git a/set/balancedbst.go b/set/balancedbst.go deleted file mode 100644 index 12673c5..0000000 --- a/set/balancedbst.go +++ /dev/null @@ -1,5 +0,0 @@ -package set - -func NewBalancedBST() *BST { - return NewBST() -} diff --git a/set/bst.go b/set/bst.go deleted file mode 100644 index 0eecb9e..0000000 --- a/set/bst.go +++ /dev/null @@ -1,171 +0,0 @@ -package set - -import "fmt" - -type node struct { - key int - val int - left *node - right *node -} - -func (n *node) String() string { - recurse := func(n *node) string { - if n == nil { - return "" - } - return n.String() - } - - return fmt.Sprintf("node{%d:%d,%s,%s}", - n.key, - n.val, - recurse(n.left), - recurse(n.right)) -} - -type BST struct { - root *node -} - -func NewBST() *BST { - return &BST{} -} - -func (t *BST) String() string { - if t.Empty() { - return "BST{}" - } - - return fmt.Sprintf("BST{%s}", t.root) -} - -func (t *BST) Empty() bool { - return t.root == nil -} - -func (t *BST) Set(key, val int) { - if t.Empty() { - t.root = &node{key, val, nil, nil} - return - } - ptr, _, err := t.search(&t.root, key) - switch err { - case nil: - // key already in the tree - return - case NotFound: - *ptr = &node{key, val, nil, nil} - return - default: - panic(err) - } -} - -func (t *BST) Get(key int) (int, error) { - _, n, err := t.search(&t.root, key) - if err != nil { - return 0, err - } - return n.val, nil -} - -func (t *BST) Del(key int) (int, error) { - ptr, n, err := t.search(&t.root, key) - if err != nil { - return 0, err - } - - // Case 1: n is leaf node - // Case 2: n has one child - // Case 3: n has two childs - - switch { - case n.left == nil: - if n.right == nil { - // I am a leaf node - *ptr = nil - return n.val, nil - } - // I have a right child - *ptr = n.right - return n.val, nil - - case n.right == nil: - // I have a left child - *ptr = n.left - return n.val, nil - default: - // I have two children! - - o, err := t.deleteMin(&n.right) - if err != nil { - return 0, err - } - - o.left = n.left - o.right = n.right - *ptr = o - - return n.val, nil - } -} - -func (t *BST) search(ptr **node, key int) (**node, *node, error) { - n := *ptr - if n == nil { - return ptr, nil, NotFound - } - - switch { - case key < n.key: - return t.search(&n.left, key) - case n.key < key: - return t.search(&n.right, key) - default: - return ptr, n, nil - } -} - -func (t *BST) deleteMin(ptr **node) (*node, error) { - ptr, n, err := t.min(ptr) - if err != nil { - return nil, err - } - - *ptr = n.right - n.right = nil - return n, nil -} - -func (t *BST) min(ptr **node) (**node, *node, error) { - n := *ptr - if n == nil { - return nil, nil, NotFound - } - - for { - if n.left == nil { - return ptr, n, nil - } - ptr = &n.left - n = *ptr - } -} - -/* -func (t *BST) max(ptr **node) (**node, *node, error) { - n := *ptr - if n == nil { - return nil, nil, NotFound - } - - for { - if n.right == nil { - return ptr, n, nil - } - ptr = &n.right - n = *ptr - } -} -*/ diff --git a/set/elementary.go b/set/elementary.go deleted file mode 100644 index a9d367e..0000000 --- a/set/elementary.go +++ /dev/null @@ -1,79 +0,0 @@ -package set - -type ElementaryElem struct { - key int - val int - next *ElementaryElem -} - -type Elementary struct { - root *ElementaryElem -} - -func NewElementary() *Elementary { - return &Elementary{} -} - -func (s *Elementary) Empty() bool { - return s.root == nil -} - -func (s *Elementary) Set(key int, val int) { - if s.Empty() { - s.root = &ElementaryElem{key, val, nil} - return - } - - elem := s.root - - for { - if elem.key == key { - elem.val = val - return - } - if elem.next == nil { - elem.next = &ElementaryElem{key, val, nil} - return - } - elem = elem.next - } -} - -func (s *Elementary) Get(key int) (int, error) { - elem := s.root - - for elem != nil { - if elem.key == key { - return elem.val, nil - } - elem = elem.next - } - - return 0, NotFound -} - -func (s *Elementary) Del(key int) (int, error) { - if s.Empty() { - return 0, NotFound - } - - if s.root.key == key { - defer func() { - s.root = s.root.next - }() - return s.root.val, nil - } - - elem := s.root - for elem.next != nil { - if elem.next.key == key { - defer func() { - elem.next = elem.next.next - }() - return elem.next.val, nil - } - elem = elem.next - } - - return 0, NotFound -} diff --git a/set/set.go b/set/set.go deleted file mode 100644 index 29bfad7..0000000 --- a/set/set.go +++ /dev/null @@ -1,15 +0,0 @@ -package set - -import "fmt" - -var ( - NotFound = fmt.Errorf("could not find entry") - NotImplemented = fmt.Errorf("method not implemented") -) - -type Set interface { - Empty() bool - Set(key int, val int) - Get(key int) (int, error) - Del(key int) (int, error) -} diff --git a/set/set_test.go b/set/set_test.go deleted file mode 100644 index 098947d..0000000 --- a/set/set_test.go +++ /dev/null @@ -1,130 +0,0 @@ -package set - -import ( - "fmt" - "testing" - - "github.com/snonux/algorithms/ds" - "github.com/snonux/algorithms/sort" -) - -const factor int = 10 -const minLength int = 1 -const maxLength int = 10000 - -// Store results here to avoid compiler optimizations -var benchResult int - -func TestElementary(t *testing.T) { - for i := minLength; i <= maxLength; i *= factor { - test(NewElementary(), i, t) - } -} - -func TestBST(t *testing.T) { - for i := minLength; i <= maxLength; i *= factor { - test(NewBST(), i, t) - } -} - -func test(s Set, l int, t *testing.T) { - keys := ds.NewRandomArrayList(l, l) - randoms := ds.NewRandomArrayList(l, -1) - mapping := make(map[int]int, l) - - get := func(key int, del bool) int { - var val int - var err error - switch { - case del: - defer delete(mapping, key) - val, err = s.Del(key) - //t.Log("Del", key, val, err) - default: - val, err = s.Get(key) - //t.Log("Get", key, val, err) - } - - if mVal, ok := mapping[key]; ok { - if err != nil { - t.Error("Could not get element", key, val, mVal, err) - } - if mVal != val { - t.Error("Got wrong value for element", key, val, mVal) - } - return val - } - - if err == nil { - t.Error("Got element but expected not to", key, val) - } - return val - } - testGet := func(key int) int { return get(key, false) } - testDel := func(key int) int { return get(key, true) } - - testSet := func(key, val int) { - s.Set(key, val) - mapping[key] = val - //t.Log("Set", key, val) - testGet(key) - } - - t.Log("Set random key-values", l) - var prevKey int - for _, key := range sort.Shuffle(keys) { - testSet(key, randoms[key]) - testGet(prevKey) - prevKey = key - } - t.Log("Del random key-values", l) - for _, key := range sort.Shuffle(keys) { - testDel(key) - testGet(prevKey) - prevKey = key - } - if !s.Empty() { - t.Error("Expected set to be empty", l) - } -} - -func TestBalancedBST(t *testing.T) { - for i := minLength; i <= maxLength; i *= factor { - test(NewBalancedBST(), i, t) - } -} - -func BenchmarkElementary(t *testing.B) { - s := NewElementary() - for i := minLength; i <= maxLength; i *= factor { - benchmark(s, i, t) - } -} - -func BenchmarkBST(t *testing.B) { - s := NewBST() - for i := minLength; i <= maxLength; i *= factor { - benchmark(s, i, t) - } -} - -func BenchmarkBalancedBST(t *testing.B) { - s := NewBalancedBST() - for i := minLength; i <= maxLength; i *= factor { - benchmark(s, i, t) - } -} - -func benchmark(s Set, l int, b *testing.B) { - list := ds.NewRandomArrayList(l, -1) - - b.Run(fmt.Sprintf("random(%d)", l), func(b *testing.B) { - b.ResetTimer() - for i, a := range list { - s.Set(a, i) - } - for _, a := range list { - benchResult, _ = s.Get(a) - } - }) -} -- cgit v1.2.3