drxvjnx58751 2019-08-11 16:12
浏览 152
已采纳

为什么我的红黑树实现基准显示线性时间复杂度?

The implementation basically follows wiki.

Here is how I implemented the benchmark, in this case, it is benchmarking 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)
                }
            }
        })
    }
}

The benchmark results:

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

A visual line chart of ns/op:

enter image description here

Even I increase the problem size:

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

Visual chart:

enter image description here

You can check the code in Playground, or a lengthy version:

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)
}
  • 写回答

1条回答 默认 最新

  • duanpa2143 2019-08-11 17:46
    关注

    The benchmark was wrongly implemented, a correct version:

    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++
        }
    }
    

    enter image description here

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿