binary-trees-naive-slice.go

// This is a quick and dirty conversion of https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-go-2.html
// to use slice as a container of tree.
// This version time:
//   real    0m3.946s
//   user    0m24.126s
//   sys     0m1.671s
// Original:
//   real    0m6.719s
//   user    1m8.281s
//   sys     0m0.862s

package main

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

type Tr struct {
	Left  int
	Right int
}

type TreeContainer []Tr

func (tc TreeContainer) Count(id int) int {
	t := tc[id]
	if t.Left == 0 {
		return 1
	}

	return 1 + tc.Count(t.Left) + tc.Count(t.Right)
}

type Tree struct {
	Left  *Tree
	Right *Tree
}

// Count the nodes in the given complete binary tree.
func (t *Tree) Count() int {
	// Only test the Left node (this binary tree is expected to be complete).
	if t.Left == nil {
		return 1
	}
	return 1 + t.Right.Count() + t.Left.Count()
}

func NewTC(tc TreeContainer, depth int) (TreeContainer, int) {
	if depth >= 0 {
		id := len(tc)
		tc = append(tc, Tr{})
		var l, r int
		tc, l = NewTC(tc, depth-1)
		tc, r = NewTC(tc, depth-1)

		tc[id] = Tr{Left: l, Right: r}
		return tc, id
	} else {
		return tc, 0
	}
}

// Create a complete binary tree of `depth` and return it as a pointer.
func NewTree(depth int) *Tree {
	if depth > 0 {
		return &Tree{Left: NewTree(depth - 1), Right: NewTree(depth - 1)}
	} else {
		return &Tree{}
	}
}

func Run(maxDepth int) {
	var wg sync.WaitGroup

	// Set minDepth to 4 and maxDepth to the maximum of maxDepth and minDepth +2.
	const minDepth = 4
	if maxDepth < minDepth+2 {
		maxDepth = minDepth + 2
	}

	// Create an indexed string buffer for outputing the result in order.
	outCurr := 0
	outSize := 3 + (maxDepth-minDepth)/2
	outBuff := make([]string, outSize)

	// Create binary tree of depth maxDepth+1, compute its Count and set the
	// first position of the outputBuffer with its statistics.
	wg.Add(1)
	go func() {
		//tree := NewTree(maxDepth + 1)
		tc, _ := NewTC(nil, maxDepth+1)
		//msg := fmt.Sprintf("stretch tree of depth %d\t check: %d",
		//	maxDepth+1,
		//	tree.Count())
		msg := fmt.Sprintf("stretch tree of depth %d\t check: %d, len: %d",
			maxDepth+1,
			tc.Count(0), len(tc))

		outBuff[0] = msg
		wg.Done()
	}()

	// Create a long-lived binary tree of depth maxDepth. Its statistics will be
	// handled later.
	//var longLivedTree *Tree
	var longLivedTree TreeContainer
	wg.Add(1)
	go func() {
		//longLivedTree = NewTree(maxDepth)
		longLivedTree, _ = NewTC(nil, maxDepth)
		wg.Done()
	}()

	// Create a lot of binary trees, of depths ranging from minDepth to maxDepth,
	// compute and tally up all their Count and record the statistics.
	for depth := minDepth; depth <= maxDepth; depth += 2 {
		iterations := 1 << (maxDepth - depth + minDepth)
		outCurr++

		wg.Add(1)
		//index := outCurr
		go func(depth, iterations, index int) {
			acc := 0
			for i := 0; i < iterations; i++ {
				// Create a binary tree of depth and accumulate total counter with its
				// node count.
				a, _ := NewTC(nil, depth)
				//a := NewTree(depth)
				//acc += a.Count()
				acc += a.Count(0)
			}
			msg := fmt.Sprintf("%d\t trees of depth %d\t check: %d",
				iterations,
				depth,
				acc)

			outBuff[index] = msg
			wg.Done()
		}(depth, iterations, outCurr)
	}

	wg.Wait()

	// Compute the checksum of the long-lived binary tree that we created
	// earlier and store its statistics.
	//msg = fmt.Sprintf("long lived tree of depth %d\t check: %d",
	//	maxDepth,
	//	longLivedTree.Count())
	msg := fmt.Sprintf("long lived tree of depth %d\t check: %d",
		maxDepth,
		longLivedTree.Count(0))
	outBuff[outSize-1] = msg

	// Print the statistics for all of the various tree depths.
	for _, m := range outBuff {
		fmt.Println(m)
	}
}

func main() {
	n := 0
	flag.Parse()
	if flag.NArg() > 0 {
		n, _ = strconv.Atoi(flag.Arg(0))
	}

	Run(n)
}