Updated getIndex() for 650% speed improvement in number breeding program.

Added 'value' field to number based on conjectures related to addition. See my
chapter 2 and 3 notes. This allowed a binary search of the universe rather than
a linear search.

Benchmarking command:
    time ./ch1-breeding-numbers -generations 13 -silent

Before:
    382.156u 3.945s 5:41.96 112.9%  0+0k 40+66io 7pf+0w

After:
    59.828u 3.247s 0:30.70 205.4%   0+0k 1+0io 0pf+0w

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index fbba0ec..58576cc 100644 (file)
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -9,6 +9,7 @@ import (
     "log"
     "os"
     "runtime/pprof"
+    "sort"
     "strconv"
 )
 
@@ -38,12 +39,14 @@ type surrealUniverse struct {
 }
 
 func (u *surrealUniverse) getIndex(num surrealNumber) int {
-    for i := 0; i < len(u.numbers); i++ {
-        if num.identifier == u.numbers[i].identifier {
-            return i
-        }
-    }
-    return -1 // This should be unreachable.
+    // Since getIndex() is only ever called on 'num' which already exists in
+    // the universe, we return the result directly, without bothering to
+    // confirm an exact match.
+    //
+    // Also, we can get away with a direct comparison of these floating point
+    // numbers since there will be an exact match, guaranteed since 'num' is
+    // already in the universe.
+    return sort.Search(u.cardinality(), func(i int) bool {return u.numbers[i].value >= num.value})
 }
 
 func (u *surrealUniverse) cardinality() int {
@@ -73,23 +76,26 @@ func (u *surrealUniverse) insert(num surrealNumber) {
     switch ancestorCount {
         case 0:
             if u.cardinality() == 0 {
+                num.value = 0.0
                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers, num)
             }
         case 1:
-            if num.leftSet.cardinality() == 1{
+            if num.leftSet.cardinality() == 1 {
                 index := u.getIndex(num.leftSet.members[0])
-                num.identifier = u.nextUniqueID
-                u.nextUniqueID++
                 if index+1 == u.cardinality() {
+                    num.value = u.numbers[u.cardinality()-1].value + 1.0
+                    num.identifier = u.nextUniqueID
+                    u.nextUniqueID++
                     u.numbers = append(u.numbers, num)
                 }
             } else {
                 index := u.getIndex(num.rightSet.members[0])
-                num.identifier = u.nextUniqueID
-                u.nextUniqueID++
                 if index == 0 {
+                    num.value = u.numbers[0].value - 1.0
+                    num.identifier = u.nextUniqueID
+                    u.nextUniqueID++
                     u.numbers = append(u.numbers[:1], u.numbers...)
                     u.numbers[0] = num
                 }
@@ -98,6 +104,7 @@ func (u *surrealUniverse) insert(num surrealNumber) {
             leftIndex := u.getIndex(num.leftSet.members[0])
             rightIndex := u.getIndex(num.rightSet.members[0])
             if leftIndex+1 == rightIndex {
+                num.value = (num.leftSet.members[0].value + num.rightSet.members[0].value) / 2
                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)
@@ -173,6 +180,7 @@ func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
 type surrealNumber struct {
     leftSet surrealSet
     rightSet surrealSet
+    value float64
     identifier uint
     generation int
 }
@@ -241,7 +249,7 @@ func main() {
     var universe surrealUniverse
     universe.nextUniqueID = 0
     fmt.Println("Seeding generation 0 by hand.")
-    universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0, 0})
+    universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0.0, 0, 0})
 
     // Breed however many generations of numbers were requested by the user and
     // add them all to the universe.
@@ -300,7 +308,7 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN
             var leftSet, rightSet surrealSet
             leftSet.insert(universe.numbers[i], universe)
             rightSet.insert(universe.numbers[j], universe)
-            newSurrealNumber := surrealNumber{leftSet,rightSet,0,generation}
+            newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,0,generation}
             numbers = append(numbers, newSurrealNumber)
         }
     }
@@ -308,9 +316,9 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN
     for i := 0; i < universe.cardinality(); i++ {
         var tempSet surrealSet
         tempSet.insert(universe.numbers[i], universe)
-        newSurrealNumber := surrealNumber{tempSet,surrealSet{},0,generation}
+        newSurrealNumber := surrealNumber{tempSet,surrealSet{},0.0,0,generation}
         numbers = append(numbers, newSurrealNumber)
-        newSurrealNumber = surrealNumber{surrealSet{},tempSet,0,generation}
+        newSurrealNumber = surrealNumber{surrealSet{},tempSet,0.0,0,generation}
         numbers = append(numbers, newSurrealNumber)
     }