SHARE
TWEET

Untitled

a guest Aug 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "os"
  6.     "runtime"
  7.     "strconv"
  8. )
  9.  
  10. type node struct {
  11.     left  *node
  12.     right *node
  13. }
  14.  
  15. type result struct {
  16.     depth int
  17.     sum   int
  18. }
  19.  
  20. var ch chan result
  21. var results []int
  22.  
  23. func (n *node) Checksum() int {
  24.     if n.left == nil {
  25.         return 1
  26.     }
  27.     return n.left.Checksum() + n.right.Checksum() + 1
  28. }
  29.  
  30. func NewNode(depth int) *node {
  31.     n := new(node)
  32.  
  33.     if depth > 0 {
  34.         n.left = NewNode(depth - 1)
  35.         n.right = NewNode(depth - 1)
  36.     }
  37.  
  38.     return n
  39. }
  40.  
  41. func ManyTrees(iterations, depth int) {
  42.     sum := 0
  43.  
  44.     var n *node
  45.     for i := 0; i < iterations; i++ {
  46.         n = NewNode(depth)
  47.         sum += n.Checksum()
  48.     }
  49.  
  50.     ch <- result{
  51.         depth: depth,
  52.         sum:   sum,
  53.     }
  54. }
  55.  
  56. func main() {
  57.     minDepth := 4
  58.     maxDepth := minDepth + 2
  59.  
  60.     if len(os.Args) == 2 {
  61.         val, err := strconv.Atoi(os.Args[1])
  62.         if err == nil {
  63.             maxDepth = val
  64.         }
  65.     }
  66.  
  67.     ch = make(chan result, runtime.NumCPU())
  68.     defer close(ch)
  69.     results = make([]int, maxDepth+1)
  70.  
  71.     // Stretch tree
  72.     stretch := NewNode(maxDepth + 1)
  73.     fmt.Printf("stretch tree of depth %d\t check: %d\n", maxDepth+1, stretch.Checksum())
  74.  
  75.     // Long lived tree for later use
  76.     long := NewNode(maxDepth)
  77.  
  78.     // Lots of trees in parallel
  79.     c := 0
  80.     for i := minDepth; i <= maxDepth; i += 2 {
  81.         c++
  82.         go ManyTrees(1<<uint(maxDepth-i+minDepth), i)
  83.     }
  84.     for i := 0; i < c; i++ {
  85.         r := <-ch
  86.         results[r.depth] = r.sum
  87.     }
  88.  
  89.     for i := minDepth; i <= maxDepth; i += 2 {
  90.         fmt.Printf("%d\t trees of depth %d\t check: %d\n", 1<<uint(maxDepth-i+minDepth), i, results[i])
  91.     }
  92.  
  93.     // Long lived tree stats
  94.     fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, long.Checksum())
  95. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top