1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
/* The Computer Language Benchmarks Game
* http://benchmarksgame.alioth.debian.org/
*
* based on Go program by The Go Authors.
* based on C program by Kevin Carson
* flag.Arg hack by Isaac Gouy
* modified by Jamil Djadala to use goroutines
* modified by Chai Shushan
*
*/
package main
import (
"flag"
"fmt"
"runtime"
"strconv"
"sync"
)
var minDepth = 4
var n = 20
func main() {
runtime.GOMAXPROCS(runtime.NumCPU() * 2)
flag.Parse()
if flag.NArg() > 0 {
n, _ = strconv.Atoi(flag.Arg(0))
}
maxDepth := n
if minDepth+2 > n {
maxDepth = minDepth + 2
}
stretchDepth := maxDepth + 1
check_l := bottomUpTree(0, stretchDepth).ItemCheck()
fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check_l)
longLivedTree := bottomUpTree(0, maxDepth)
result_trees := make([]int, maxDepth+1)
result_check := make([]int, maxDepth+1)
var wg sync.WaitGroup
for depth_l := minDepth; depth_l <= maxDepth; depth_l += 2 {
wg.Add(1)
go func(depth int) {
iterations := 1 << uint(maxDepth-depth+minDepth)
check := 0
for i := 1; i <= iterations; i++ {
check += bottomUpTree(i, depth).ItemCheck()
check += bottomUpTree(-i, depth).ItemCheck()
}
result_trees[depth] = iterations * 2
result_check[depth] = check
wg.Done()
}(depth_l)
}
wg.Wait()
for depth := minDepth; depth <= maxDepth; depth += 2 {
fmt.Printf("%d\t trees of depth %d\t check: %d\n",
result_trees[depth], depth, result_check[depth],
)
}
fmt.Printf("long lived tree of depth %d\t check: %d\n",
maxDepth, longLivedTree.ItemCheck(),
)
}
func bottomUpTree(item, depth int) *Node {
if depth <= 0 {
return &Node{item, nil, nil}
}
return &Node{item,
bottomUpTree(2*item-1, depth-1),
bottomUpTree(2*item, depth-1),
}
}
type Node struct {
item int
left, right *Node
}
func (self *Node) ItemCheck() int {
if self.left == nil {
return self.item
}
return self.item + self.left.ItemCheck() - self.right.ItemCheck()
}
|
