Guest User

Untitled

a guest
Aug 19th, 2019
70
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