From 213fa8b5b4ce7a2531f07197927b3b4c06a2714b Mon Sep 17 00:00:00 2001 From: Aaron Taylor Date: Sat, 15 May 2021 18:40:08 -0700 Subject: [PATCH] 'go fmt' pass on number breeding program. --- chapter-1-experiments/ch1-breeding-numbers.go | 570 +++++++++--------- 1 file changed, 285 insertions(+), 285 deletions(-) diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go index c5baa14..a2b8d34 100644 --- a/chapter-1-experiments/ch1-breeding-numbers.go +++ b/chapter-1-experiments/ch1-breeding-numbers.go @@ -4,12 +4,12 @@ package main import ( - "flag" - "fmt" - "log" - "os" - "runtime/pprof" - "sort" + "flag" + "fmt" + "log" + "os" + "runtime/pprof" + "sort" ) // ============================================================================= @@ -31,85 +31,85 @@ import ( // ============================================================================= type surrealUniverse struct { - // The elements in this slice are stored in order according to Axiom 3. - // Thus, numbers[0] < numbers[1] < ... < numbers[n]. - numbers []surrealNumber - nextUniqueID uint + // The elements in this slice are stored in order according to Axiom 3. + // Thus, numbers[0] < numbers[1] < ... < numbers[n]. + numbers []surrealNumber + nextUniqueID uint } func (u *surrealUniverse) getIndex(num surrealNumber) int { - // 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}) + // 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 { - return len(u.numbers) + return len(u.numbers) } func (u *surrealUniverse) insert(num surrealNumber) { - // Before we can insert a number into the universe, we must first determine - // if it is newly discovered. We do this by looking at its ancestors, all - // guaranteed to be on the number line by construction, finding three - // cases: - // - // 1. There are zero ancestors. - // We have rediscovered 0 and can abort the insertion unless creating - // a brand new universe. - // - // 2. There is one ancestor. - // If the number extends the number line, it is new, otherwise it will - // be similar to a form with two ancestors and should be ignored since - // the two ancestor form is a better visual representation. - // - // 3. There are two ancestors. - // The number is only new if both ancestors are side-by-side on the - // number line. - - ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality() - 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 { - index := u.getIndex(num.leftSet.members[0]) - 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]) - 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 - } - } - case 2: - 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:]...) - u.numbers[rightIndex] = num - } - } + // Before we can insert a number into the universe, we must first determine + // if it is newly discovered. We do this by looking at its ancestors, all + // guaranteed to be on the number line by construction, finding three + // cases: + // + // 1. There are zero ancestors. + // We have rediscovered 0 and can abort the insertion unless creating + // a brand new universe. + // + // 2. There is one ancestor. + // If the number extends the number line, it is new, otherwise it will + // be similar to a form with two ancestors and should be ignored since + // the two ancestor form is a better visual representation. + // + // 3. There are two ancestors. + // The number is only new if both ancestors are side-by-side on the + // number line. + + ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality() + 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 { + index := u.getIndex(num.leftSet.members[0]) + 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]) + 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 + } + } + case 2: + 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:]...) + u.numbers[rightIndex] = num + } + } } // ============================================================================= @@ -121,173 +121,173 @@ func (u *surrealUniverse) insert(num surrealNumber) { // This function implements Axiom 3 and is the root of all other comparisons. func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool { - // By construction, no number in this program will ever have more than one - // element in its right or left sets, nor will those elements be of a form - // other than that 'registered' with the universe. That allows direct - // comparisons using the surrealNumber.identifier field via u.getIndex(). - - // --------------------------------- - - // First we implement the check "no member of the first number's left set - // is greater than or equal to the second number". - if numA.leftSet.cardinality() == 1 { - if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) { - return false - } - } - - // Now we implement the check "no member of the second number's right set - // is less than or equal to the first number". - if numB.rightSet.cardinality() == 1 { - if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) { - return false - } - } - - return true + // By construction, no number in this program will ever have more than one + // element in its right or left sets, nor will those elements be of a form + // other than that 'registered' with the universe. That allows direct + // comparisons using the surrealNumber.identifier field via u.getIndex(). + + // --------------------------------- + + // First we implement the check "no member of the first number's left set + // is greater than or equal to the second number". + if numA.leftSet.cardinality() == 1 { + if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) { + return false + } + } + + // Now we implement the check "no member of the second number's right set + // is less than or equal to the first number". + if numB.rightSet.cardinality() == 1 { + if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) { + return false + } + } + + return true } func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool { - if u.isRelated(numA, numB) && u.isRelated(numB, numA) { - return true - } - return false + if u.isRelated(numA, numB) && u.isRelated(numB, numA) { + return true + } + return false } func (u *surrealUniverse) equal(left, right surrealNumber) bool { - return u.isSimilar(left, right) + return u.isSimilar(left, right) } func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool { - return u.isRelated(left, right) + return u.isRelated(left, right) } func (u *surrealUniverse) lessThan(left, right surrealNumber) bool { - return u.lessThanOrEqual(left, right) && !u.equal(left, right) + return u.lessThanOrEqual(left, right) && !u.equal(left, right) } func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool { - return !u.lessThan(left, right) + return !u.lessThan(left, right) } func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool { - return !u.isRelated(left, right) + return !u.isRelated(left, right) } // ============================================================================= type surrealNumber struct { - leftSet surrealSet - rightSet surrealSet - value float64 - identifier uint - generation int + leftSet surrealSet + rightSet surrealSet + value float64 + identifier uint + generation int } type surrealSet struct { - members []surrealNumber + members []surrealNumber } func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool { - for i := 0; i < len(s.members); i++ { - if u.equal(num, s.members[i]) { - return true - } - } - return false + for i := 0; i < len(s.members); i++ { + if u.equal(num, s.members[i]) { + return true + } + } + return false } func (s *surrealSet) cardinality() int { - return len(s.members) + return len(s.members) } func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) { - if !s.isMember(num, u) { - s.members = append(s.members, num) - } + if !s.isMember(num, u) { + s.members = append(s.members, num) + } } func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) { - for i := 0; i < len(s.members); i++ { - if u.equal(num, s.members[i]) { - s.members[i] = s.members[len(s.members)-1] - s.members = s.members[:len(s.members)-1] - } - } + for i := 0; i < len(s.members); i++ { + if u.equal(num, s.members[i]) { + s.members[i] = s.members[len(s.members)-1] + s.members = s.members[:len(s.members)-1] + } + } } // ============================================================================= func main() { - // Flags to enable various performance profiling options. - cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU 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. - totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.") - flag.Parse() - if *totalGenerations < 1 { - log.Fatal("ERROR: The argument to '-generations' must be greater than zero.") - } - remainingGenerations := *totalGenerations - 1 - - // Setup any CPU performance profiling requested by the user. This will run - // throughout program execution. - if *cpuProfile != "" { - cpuProFile, err := os.Create(*cpuProfile) - if err != nil { - log.Fatal("ERROR: Unable to open CPU profiling output file:", err) - } - pprof.StartCPUProfile(cpuProFile) - defer pprof.StopCPUProfile() - } - - // Build a universe to contain all the surreal numbers we breed. - // Seed it by hand with the number zero as generation-0. - var universe surrealUniverse - universe.nextUniqueID = 0 - fmt.Println("Seeding generation 0 by hand.") - 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. - fmt.Printf("Breeding Generation:") - for generation := 1; generation <= remainingGenerations; generation++ { - // Give the user some idea of overall progress during long jobs. - if generation != 1 { - fmt.Printf(",") - } - fmt.Printf(" %d", generation) - - // 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(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. - if !(*suppressOutput) { - for i := 0; i < universe.cardinality(); i++ { - printlnNumber(universe.numbers[i]) - } - } - fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.") - fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.") + // Flags to enable various performance profiling options. + cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU 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. + totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.") + flag.Parse() + if *totalGenerations < 1 { + log.Fatal("ERROR: The argument to '-generations' must be greater than zero.") + } + remainingGenerations := *totalGenerations - 1 + + // Setup any CPU performance profiling requested by the user. This will run + // throughout program execution. + if *cpuProfile != "" { + cpuProFile, err := os.Create(*cpuProfile) + if err != nil { + log.Fatal("ERROR: Unable to open CPU profiling output file:", err) + } + pprof.StartCPUProfile(cpuProFile) + defer pprof.StopCPUProfile() + } + + // Build a universe to contain all the surreal numbers we breed. + // Seed it by hand with the number zero as generation-0. + var universe surrealUniverse + universe.nextUniqueID = 0 + fmt.Println("Seeding generation 0 by hand.") + 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. + fmt.Printf("Breeding Generation:") + for generation := 1; generation <= remainingGenerations; generation++ { + // Give the user some idea of overall progress during long jobs. + if generation != 1 { + fmt.Printf(",") + } + fmt.Printf(" %d", generation) + + // 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(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. + if !(*suppressOutput) { + for i := 0; i < universe.cardinality(); i++ { + printlnNumber(universe.numbers[i]) + } + } + fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.") + fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.") } // ============================================================================= @@ -296,86 +296,86 @@ 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 { - // 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++ { - for j := 0; j < universe.cardinality(); j++ { - var leftSet, rightSet surrealSet - leftSet.insert(universe.numbers[i], universe) - rightSet.insert(universe.numbers[j], universe) - 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.0,0,generation} - numbers = append(numbers, newSurrealNumber) - newSurrealNumber = surrealNumber{surrealSet{},tempSet,0.0,0,generation} - numbers = append(numbers, newSurrealNumber) - } - - return numbers + // 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++ { + for j := 0; j < universe.cardinality(); j++ { + var leftSet, rightSet surrealSet + leftSet.insert(universe.numbers[i], universe) + rightSet.insert(universe.numbers[j], universe) + 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.0, 0, generation} + numbers = append(numbers, newSurrealNumber) + newSurrealNumber = surrealNumber{surrealSet{}, tempSet, 0.0, 0, generation} + numbers = append(numbers, newSurrealNumber) + } + + 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 { - // Is the number in reduced form? - if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 { - return false - } - - // Is the number valid per Axiom 2? - if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 { - for i := 0; i < candidate.leftSet.cardinality(); i++ { - for j := 0; j < candidate.leftSet.cardinality(); j++ { - // Since candidates are drawn from the universe, this comparison is allowed. - if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) { - return false - } - } - } - } - - return true + // Is the number in reduced form? + if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 { + return false + } + + // Is the number valid per Axiom 2? + if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 { + for i := 0; i < candidate.leftSet.cardinality(); i++ { + for j := 0; j < candidate.leftSet.cardinality(); j++ { + // Since candidates are drawn from the universe, this comparison is allowed. + if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) { + return false + } + } + } + } + + return true } func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) { - for i := 0; i < len(numbers); i++ { - universe.insert(numbers[i]) - } + for i := 0; i < len(numbers); i++ { + universe.insert(numbers[i]) + } } // Pretty print a number, indenting to indicate generation. func printlnNumber(num surrealNumber) { - for i := 0; i < num.generation; i++ { - fmt.Printf(".\t\t") - } - fmt.Printf("%s = ", toBase26(num.identifier)) - fmt.Printf("<") - if num.leftSet.cardinality() == 0 { - fmt.Printf("---") - } else { - fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier)) - } - fmt.Printf("|") - if num.rightSet.cardinality() == 0 { - fmt.Printf("---") - } else { - fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier)) - } - fmt.Printf(">") - fmt.Printf("\n") + for i := 0; i < num.generation; i++ { + fmt.Printf(".\t\t") + } + fmt.Printf("%s = ", toBase26(num.identifier)) + fmt.Printf("<") + if num.leftSet.cardinality() == 0 { + fmt.Printf("---") + } else { + fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier)) + } + fmt.Printf("|") + if num.rightSet.cardinality() == 0 { + fmt.Printf("---") + } else { + fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier)) + } + fmt.Printf(">") + fmt.Printf("\n") } // This function is a total hack, intended only to avoid printing identifiers @@ -383,21 +383,21 @@ func printlnNumber(num surrealNumber) { // specific 'real' numbers yet. Instead, print them with [a-z] as base-26 // integers. func toBase26(num uint) (base26String []byte) { - // For alignment reasons, we never print more than three digits. Thus, any - // number greater than (26^3)-1 is out of range. - if num >= 26*26*26 { - base26String = []byte("xxx") - } else { - var firstByte, secondByte, thirdByte byte - thirdByte = byte((num % 26) + uint('a')); - num = num / 26; - secondByte = byte((num % 26) + uint('a')); - num = num / 26; - firstByte = byte((num % 26) + uint('a')); - num = num / 26; - base26String = append(base26String, firstByte) - base26String = append(base26String, secondByte) - base26String = append(base26String, thirdByte) - } - return base26String + // For alignment reasons, we never print more than three digits. Thus, any + // number greater than (26^3)-1 is out of range. + if num >= 26*26*26 { + base26String = []byte("xxx") + } else { + var firstByte, secondByte, thirdByte byte + thirdByte = byte((num % 26) + uint('a')) + num = num / 26 + secondByte = byte((num % 26) + uint('a')) + num = num / 26 + firstByte = byte((num % 26) + uint('a')) + num = num / 26 + base26String = append(base26String, firstByte) + base26String = append(base26String, secondByte) + base26String = append(base26String, thirdByte) + } + return base26String } -- 2.20.1