Source file
test/bench/go1/binarytree_test.go
1
2
3
4
5
6
7
8 package go1
9
10 import "testing"
11
12 type binaryNode struct {
13 item int
14 left, right *binaryNode
15 }
16
17 func bottomUpTree(item, depth int) *binaryNode {
18 if depth <= 0 {
19 return &binaryNode{item: item}
20 }
21 return &binaryNode{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)}
22 }
23
24 func (n *binaryNode) itemCheck() int {
25 if n.left == nil {
26 return n.item
27 }
28 return n.item + n.left.itemCheck() - n.right.itemCheck()
29 }
30
31 const minDepth = 4
32
33 func binarytree(n int) {
34 maxDepth := n
35 if minDepth+2 > n {
36 maxDepth = minDepth + 2
37 }
38 stretchDepth := maxDepth + 1
39
40 check := bottomUpTree(0, stretchDepth).itemCheck()
41
42
43 longLivedTree := bottomUpTree(0, maxDepth)
44
45 for depth := minDepth; depth <= maxDepth; depth += 2 {
46 iterations := 1 << uint(maxDepth-depth+minDepth)
47 check = 0
48
49 for i := 1; i <= iterations; i++ {
50 check += bottomUpTree(i, depth).itemCheck()
51 check += bottomUpTree(-i, depth).itemCheck()
52 }
53
54 }
55 longLivedTree.itemCheck()
56
57 }
58
59 func BenchmarkBinaryTree17(b *testing.B) {
60 for i := 0; i < b.N; i++ {
61 binarytree(17)
62 }
63 }
64
View as plain text