The Computer Language
Benchmarks Game

binary-trees Go #8 program

source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 *
 * contributed by Edward McFarlane
 * modified by Red Forks 
 */

package main

import (
   "flag"
   "fmt"
   "os"
   "runtime"
   "strconv"
   "sync"
)

type Node struct {
   left, right *Node
   value       int
}

func (root *Node) createTree(rootNodeValue, treeDepth int) {
   root.value = rootNodeValue

   if treeDepth > 0 {
      if root.left == nil {
         root.left = &Node{}
         root.right = &Node{}
      }

      root.left.createTree(2*rootNodeValue-1, treeDepth-1)
      root.right.createTree(2*rootNodeValue, treeDepth-1)

   } else if root.left != nil {
      root.left = nil
      root.right = nil
   }
}

func (root *Node) computeTreeChecksum() int {
   if root.left != nil {
      return root.left.computeTreeChecksum() - root.right.computeTreeChecksum() + root.value
   }
   return root.value
}

func main() {
   flag.Parse()
   n, err := strconv.Atoi(flag.Arg(0))
   if err != nil {
      os.Exit(1)
   }

   minDepth := 4
   maxDepth := n
   if minDepth+2 > n {
      maxDepth = minDepth + 2
   }

   {
      stretchTree := &Node{}
      stretchTree.createTree(0, maxDepth+1)

      fmt.Printf("stretch tree of depth %d\t check: %d\n", maxDepth+1, stretchTree.computeTreeChecksum())
   }

   longLivedTree := &Node{}
   longLivedTree.createTree(0, maxDepth)

   var wg sync.WaitGroup
   work := make(chan int, 2)
   buf := make([]string, maxDepth+1)
   cpus := runtime.NumCPU()

   wg.Add(cpus)
   for i := 0; i < cpus; i++ {
      go func() {
         defer wg.Done()

         var ok bool
         var depth, iterations, check, i int

         treeRoot := &Node{}

         for {
            depth, ok = <-work
            if !ok {
               return
            }

            iterations = 1 << uint(maxDepth-depth+minDepth)

            check = 0
            for i = 0; i < iterations; i++ {
               treeRoot.createTree(i, depth)
               check += treeRoot.computeTreeChecksum()
               treeRoot.createTree(-i, depth)
               check += treeRoot.computeTreeChecksum()
            }

            buf[depth] = fmt.Sprintf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check)
         }
      }()
   }

   for depth := minDepth; depth <= maxDepth; depth += 2 {
      work <- depth
   }

   close(work)
   wg.Wait()

   for depth := minDepth; depth <= maxDepth; depth += 2 {
      fmt.Print(buf[depth])
   }

   fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.computeTreeChecksum())
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
go version go1.9 linux/amd64


Thu, 18 Feb 2016 19:05:45 GMT

MAKE:
/usr/local/src/go/bin/go build -o binarytrees.go-8.go_run
0.63s to complete and log all make actions

COMMAND LINE:
./binarytrees.go-8.go_run 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1