X-Git-Url: http://git.subgeniuskitty.com/surreal-numbers/.git/blobdiff_plain/7a986617de3ef35f23402db1b507c57ca1879cfb..7757890d8346c126a73043f0ca3660996d35c02d:/chapter-1-experiments/ch1-breeding-numbers.go diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go index fbba0ec..c5baa14 100644 --- a/chapter-1-experiments/ch1-breeding-numbers.go +++ b/chapter-1-experiments/ch1-breeding-numbers.go @@ -9,7 +9,7 @@ import ( "log" "os" "runtime/pprof" - "strconv" + "sort" ) // ============================================================================= @@ -38,12 +38,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 +75,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 +103,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 +179,7 @@ func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool { type surrealNumber struct { leftSet surrealSet rightSet surrealSet + value float64 identifier uint generation int } @@ -214,7 +221,7 @@ func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) { func main() { // Flags to enable various performance profiling options. cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.") - memProfilePrefix := flag.String("memprofileprefix", "", "Filename PREFIX for saving memory profile output.") + memProfile := flag.String("memprofile", "", "Filename for saving memory profile output.") suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.") // Obtain termination conditions from user. @@ -241,7 +248,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. @@ -253,27 +260,24 @@ func main() { } fmt.Printf(" %d", generation) - // First generate all possible reduced form symbols per Axiom 1. - potentialNumbers := permuteExistingNumbers(generation, universe) - // Now prune out any symbols which are NOT valid numbers per Axiom 2. - validNumbers := pruneInvalidNumbers(potentialNumbers, universe) + // First generate all possible new numbers in this generation. + potentiallyNewNumbers := permuteExistingNumbers(generation, universe) // Attempt to add the new numbers to the universe. Any duplicates will // be weeded out in the attempt. - addNumbersToUniverse(validNumbers, &universe) - - // Setup any memory profiling requested by the user. This will snapshot - // the heap at the end of every generation. - if *memProfilePrefix != "" { - memProFile, err := os.Create(*memProfilePrefix + "-gen" + strconv.Itoa(generation) + ".mprof") - if err != nil { - log.Fatal("ERROR: Unable to write heap profile to disk:", err) - } - pprof.WriteHeapProfile(memProFile) - memProFile.Close() - } + addNumbersToUniverse(potentiallyNewNumbers, &universe) } fmt.Printf(".\n") + // Setup any memory profiling requested by the user. This will snapshot + // the heap only at this point, after all numbers were generated. + if *memProfile != "" { + memProFile, err := os.Create(*memProfile) + if err != nil { + log.Fatal("ERROR: Unable to open heap profile output file:", err) + } + pprof.WriteHeapProfile(memProFile) + memProFile.Close() + } // Print the number line with generation on the horizontal axis and // magnitude on the vertical axis. @@ -292,7 +296,11 @@ func main() { // right sets. This covers all the reduced form permutations. Any longer // permutations will be similar to one of the reduced forms. func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber { - var numbers []surrealNumber + // Profiling indicates that most calls to growSlice() and memMove() + // originate in this function. Allocating a sufficiently large slice + // upfront results in 2x speed improvement and 1/3 reduction in heap usage. + numberOfPermutations := ((universe.cardinality()+1) * (universe.cardinality()+1)) - 1 + numbers := make([]surrealNumber, 0, numberOfPermutations) // First build permutations with 1 element in each set. for i := 0; i < universe.cardinality(); i++ { @@ -300,33 +308,25 @@ 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} - numbers = append(numbers, newSurrealNumber) + newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,0,generation} + if isValidSurrealNumber(newSurrealNumber, universe) { + numbers = append(numbers, newSurrealNumber) + } } } // Now build permutations with one empty set and one 1-element set. 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) } return numbers } -func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber { - var numbers []surrealNumber - for i := 0; i < len(candidates); i++ { - if isValidSurrealNumber(candidates[i], universe) { - numbers = append(numbers, candidates[i]) - } - } - return numbers -} - // Although a non-reduced-form number is technically valid, for the purposes of // this program we're declaring it invalid. func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool {