实现基本遵循wiki 。
这是我实现基准测试的方法，在本例中，它是对 Put op 进行基准测试:
func BenchmarkRBTree(b *testing.B) {
for size := 0; size < 1000; size += 100 {
b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {
tree := NewRBTree(func(a, b interface{}) bool {
if a.(int) < b.(int) {
return true
}
return false
})
for i := 0; i < b.N; i++ {
for n := 0; n < size; n++ {
tree.Put(n, n)
}
}
})
}
}
基准测试结果:
BenchmarkRBTree/size-0-8 2000000000 0.49 ns/op 0 B/op 0 allocs/op
BenchmarkRBTree/size-100-8 200000 11170 ns/op 7984 B/op 298 allocs/op
BenchmarkRBTree/size-200-8 100000 26450 ns/op 15984 B/op 598 allocs/op
BenchmarkRBTree/size-300-8 50000 38838 ns/op 23984 B/op 898 allocs/op
BenchmarkRBTree/size-400-8 30000 55460 ns/op 31984 B/op 1198 allocs/op
BenchmarkRBTree/size-500-8 20000 62654 ns/op 39984 B/op 1498 allocs/op
BenchmarkRBTree/size-600-8 20000 80317 ns/op 47984 B/op 1798 allocs/op
BenchmarkRBTree/size-700-8 20000 91308 ns/op 55984 B/op 2098 allocs/op
BenchmarkRBTree/size-800-8 10000 106180 ns/op 63984 B/op 2398 allocs/op
BenchmarkRBTree/size-900-8 10000 121026 ns/op 71984 B/op 2698 allocs/op
ns/op的可视化折线图:
即使我增加了问题的规模:
BenchmarkRBTree/size-0-8 2000000000 0.50 ns/op 0 B/op 0 allocs/op
BenchmarkRBTree/size-10000-8 1000 1622187 ns/op 799989 B/op 29998 allocs/op
BenchmarkRBTree/size-20000-8 500 3693875 ns/op 1599994 B/op 59998 allocs/op
BenchmarkRBTree/size-30000-8 300 5693788 ns/op 2399998 B/op 89998 allocs/op
BenchmarkRBTree/size-40000-8 200 7663705 ns/op 3199998 B/op 119998 allocs/op
BenchmarkRBTree/size-50000-8 200 9869095 ns/op 3999997 B/op 149998 allocs/op
BenchmarkRBTree/size-60000-8 100 12133795 ns/op 4799999 B/op 179998 allocs/op
BenchmarkRBTree/size-70000-8 100 15422763 ns/op 5599999 B/op 209998 allocs/op
BenchmarkRBTree/size-80000-8 100 16140037 ns/op 6399998 B/op 239998 allocs/op
BenchmarkRBTree/size-90000-8 100 18161217 ns/op 7199997 B/op 269998 allocs/op
可视化图表:
您可以查看Playground中的代码，或一个冗长的版本:
type color uint32
const (
red color = iota
black
)
type rbnode struct {
c color
left *rbnode
right *rbnode
parent *rbnode
k, v interface{}
}
func (n *rbnode) color() color {
if n == nil {
return black
}
return n.c
}
func (n *rbnode) grandparent() *rbnode {
return n.parent.parent
}
func (n *rbnode) uncle() *rbnode {
if n.parent == n.grandparent().left {
return n.grandparent().right
}
return n.grandparent().left
}
func (n *rbnode) sibling() *rbnode {
if n == n.parent.left {
return n.parent.right
}
return n.parent.left
}
func (n *rbnode) maximumNode() *rbnode {
for n.right != nil {
n = n.right
}
return n
}
// RBTree is a red-black tree
type RBTree struct {
root *rbnode
len int
less Less
}
// Less returns true if a < b
type Less func(a, b interface{}) bool
// NewRBTree creates a red-black tree
func NewRBTree(less Less) *RBTree {
return &RBTree{less: less}
}
// Len returns the size of the tree
func (t *RBTree) Len() int {
return t.len
}
// Put stores the value by given key
func (t *RBTree) Put(key, value interface{}) {
var insertedNode *rbnode
new := &rbnode{k: key, v: value, c: red}
if t.root != nil {
node := t.root
LOOP:
for {
switch {
case t.less(key, node.k):
if node.left == nil {
node.left = new
insertedNode = node.left
break LOOP
}
node = node.left
case t.less(node.k, key):
if node.right == nil {
node.right = new
insertedNode = node.right
break LOOP
}
node = node.right
default: // =
node.k = key
node.v = value
return
}
}
insertedNode.parent = node
} else {
t.root = new
insertedNode = t.root
}
t.insertCase1(insertedNode)
t.len++
}
func (t *RBTree) insertCase1(n *rbnode) {
if n.parent == nil {
n.c = black
return
}
t.insertCase2(n)
}
func (t *RBTree) insertCase2(n *rbnode) {
if n.parent.color() == black {
return
}
t.insertCase3(n)
}
func (t *RBTree) insertCase3(n *rbnode) {
if n.uncle().color() == red {
n.parent.c = black
n.uncle().c = black
n.grandparent().c = red
t.insertCase1(n.grandparent())
return
}
t.insertCase4(n)
}
func (t *RBTree) insertCase4(n *rbnode) {
if n == n.parent.right && n.parent == n.grandparent().left {
t.rotateLeft(n.parent)
n = n.left
} else if n == n.parent.left && n.parent == n.grandparent().right {
t.rotateRight(n.parent)
n = n.right
}
t.insertCase5(n)
}
func (t *RBTree) insertCase5(n *rbnode) {
n.parent.c = black
n.grandparent().c = red
if n == n.parent.left && n.parent == n.grandparent().left {
t.rotateRight(n.grandparent())
return
} else if n == n.parent.right && n.parent == n.grandparent().right {
t.rotateLeft(n.grandparent())
}
}
func (t *RBTree) replace(old, new *rbnode) {
if old.parent == nil {
t.root = new
} else {
if old == old.parent.left {
old.parent.left = new
} else {
old.parent.right = new
}
}
if new != nil {
new.parent = old.parent
}
}
func (t *RBTree) rotateLeft(n *rbnode) {
right := n.right
t.replace(n, right)
n.right = right.left
if right.left != nil {
right.left.parent = n
}
right.left = n
n.parent = right
}
func (t *RBTree) rotateRight(n *rbnode) {
left := n.left
t.replace(n, left)
n.left = left.right
if left.right != nil {
left.right.parent = n
}
left.right = n
n.parent = left
}
// Get returns the stored value by given key
func (t *RBTree) Get(key interface{}) interface{} {
n := t.find(key)
if n == nil {
return nil
}
return n.v
}
func (t *RBTree) find(key interface{}) *rbnode {
n := t.root
for n != nil {
switch {
case t.less(key, n.k):
n = n.left
case t.less(n.k, key):
n = n.right
default:
return n
}
}
return nil
}
// Del deletes the stored value by given key
func (t *RBTree) Del(key interface{}) {
var child *rbnode
n := t.find(key)
if n == nil {
return
}
if n.left != nil && n.right != nil {
pred := n.left.maximumNode()
n.k = pred.k
n.v = pred.v
n = pred
}
if n.left == nil || n.right == nil {
if n.right == nil {
child = n.left
} else {
child = n.right
}
if n.c == black {
n.c = child.color()
t.delCase1(n)
}
t.replace(n, child)
if n.parent == nil && child != nil {
child.c = black
}
}
t.len--
}
func (t *RBTree) delCase1(n *rbnode) {
if n.parent == nil {
return
}
t.delCase2(n)
}
func (t *RBTree) delCase2(n *rbnode) {
sibling := n.sibling()
if sibling.color() == red {
n.parent.c = red
sibling.c = black
if n == n.parent.left {
t.rotateLeft(n.parent)
} else {
t.rotateRight(n.parent)
}
}
t.delCase3(n)
}
func (t *RBTree) delCase3(n *rbnode) {
sibling := n.sibling()
if n.parent.color() == black &&
sibling.color() == black &&
sibling.left.color() == black &&
sibling.right.color() == black {
sibling.c = red
t.delCase1(n.parent)
return
}
t.delCase4(n)
}
func (t *RBTree) delCase4(n *rbnode) {
sibling := n.sibling()
if n.parent.color() == red &&
sibling.color() == black &&
sibling.left.color() == black &&
sibling.right.color() == black {
sibling.c = red
n.parent.c = black
return
}
t.delCase5(n)
}
func (t *RBTree) delCase5(n *rbnode) {
sibling := n.sibling()
if n == n.parent.left &&
sibling.color() == black &&
sibling.left.color() == red &&
sibling.right.color() == black {
sibling.c = red
sibling.left.c = black
t.rotateRight(sibling)
} else if n == n.parent.right &&
sibling.color() == black &&
sibling.right.color() == red &&
sibling.left.color() == black {
sibling.c = red
sibling.right.c = black
t.rotateLeft(sibling)
}
t.delCase6(n)
}
func (t *RBTree) delCase6(n *rbnode) {
sibling := n.sibling()
sibling.c = n.parent.color()
n.parent.c = black
if n == n.parent.left && sibling.right.color() == red {
sibling.right.c = black
t.rotateLeft(n.parent)
return
}
sibling.left.c = black
t.rotateRight(n.parent)
}
最佳答案
基准测试实现错误，正确版本:
func BenchmarkRBTree_Put(b *testing.B) {
count := 0
grow := 1
for size := 0; size < 100000; size += 1 * grow {
if count%10 == 0 {
count = 1
grow *= 10
}
b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {
// prepare problem size
tree := NewRBTree(func(a, b interface{}) bool {
if a.(int) < b.(int) {
return true
}
return false
})
for n := 0; n < size-1; n++ {
tree.Put(n, n)
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
tree.Put(size, size) // only measure the last operation
}
})
count++
}
}
关于algorithm - 为什么我的红黑树实现基准测试显示线性时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57451610/