Chapter 11 Testing

Exercise 11.1: Write tests for thecharcountprogram in Section 4.3.

// skip, see 11.2.2 Testing a Command

Exercise 11.2: Write a set of tests forIntSet(§6.5) that checks that its behavior after each operation is equivalent to a set based on built-in maps. Save your implementation for benchmarking in Exercise 11.7.

func TestIntSet(t *testing.T) {
    var intset = NewIntSet()
    var hashset = NewHashSet()

    intset.Add(1)
    intset.Add(144)
    intset.Add(299)

    hashset.Add(1)
    hashset.Add(144)
    hashset.Add(299)

    if intset.String() != hashset.String() {
        t.Errorf("intset(%q) != hashset(%q)", intset.String(), hashset.String())
    }

    intset2 := NewIntSet()
    intset2.Add(42)

    hashset2 := NewHashSet()
    hashset2.Add(42)

    intset.UnionWith(intset2)
    hashset.UnionWith(hashset2)

    if intset.String() != hashset.String() {
        t.Errorf("intset(%q) != hashset(%q)", intset.String(), hashset.String())
    }
}

// Copyright © 2017 [email protected]∂∂∂∂
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/

// See page 165.

// Package intset provides a set of integers based on a bit vector.

package intset

import (
    "sort"
    "bytes"
    "fmt"
)

type HashSet map[int]bool

func NewHashSet() HashSet {
    return make(map[int]bool)
}

func (s HashSet) Has(x int) bool {
    return s[x]
}

func (s HashSet) Add(x int) {
    s[x] = true
}

func (s HashSet) UnionWith(t HashSet) {
    for k := range t {
        s[k] = true
    }
}

func (s HashSet) String() string {
    var buf bytes.Buffer
    var items []int
    for k := range s {
        items = append(items, k)
    }
    sort.Ints(items)
    buf.WriteByte('{')
    for i, k := range items {
        fmt.Fprintf(&buf, "%d", k)
        if i != len(items)-1 {
            buf.WriteByte(' ')
        }
    }
    buf.WriteByte('}')
    return buf.String()
}

Exercise 11.3: TestRandomPalindromesonly tests palindromes. Write a randomized test that generates and verifies non-palindromes.

func randomNonPalindrome(rng *rand.Rand) string {
    n := 30 + rng.Intn(31) // random length up to 60, at least of length 30
    runes := make([]rune, n)
    for i := 0; i < n; i++ {
        r := rune(rng.Intn(0x1000)) // random rune up to '\u0999'
        runes[i] = r
    }
    return "A" + string(runes) + "BCD"
}

Exercise 11.4: ModifyrandomPalindrometo exerciseIsPalindrome’s handling of punctuation and spaces.

// see book's example code
// Answer for Exercise 11.4: Modify randomPalindrome to exercise
// IsPalindrome's handling of punctuation and spaces.

// WARNING: the conversion r -> upper -> lower doesn't preserve
// the value of r in some cases, e.g., µ Μ, ſ S, ı I

// randomPalindrome returns a palindrome whose length and contents
// are derived from the pseudo-random number generator rng.
func randomNoisyPalindrome(rng *rand.Rand) string {
    n := rng.Intn(25) // random length up to 24
    runes := make([]rune, n)
    for i := 0; i < (n+1)/2; i++ {
        r := rune(rng.Intn(0x200)) // random rune up to \u99
        runes[i] = r
        r1 := r
        if unicode.IsLetter(r) && unicode.IsLower(r) {
            r = unicode.ToUpper(r)
            if unicode.ToLower(r) != r1 {
                fmt.Printf("cap? %c %c %c\n", r1, r, unicode.ToLower(r))
                // if not equal, restore
                r = r1
            }
        }
        runes[n-1-i] = r
    }
    return "?" + string(runes) + "!"
}

func TestRandomNoisyPalindromes(t *testing.T) {
    // Initialize a pseudo-random number generator.
    seed := time.Now().UTC().UnixNano()
    t.Logf("Random seed: %d", seed)
    rng := rand.New(rand.NewSource(seed))

    n := 0
    for i := 0; i < 1000; i++ {
        p := randomNoisyPalindrome(rng)
        if !IsPalindrome(p) {
            t.Errorf("IsNoisyPalindrome(%q) = false", p)
            n++
        }
    }
    fmt.Fprintf(os.Stderr, "fail = %d\n", n)
}

Exercise 11.5: ExtendTestSplitto use a table of inputs and expected outputs.

// Copyright © 2017 [email protected]
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/

package split_test

import (
    "testing"
    "strings"
)

func TestSplit(t *testing.T) {
    var tests = []struct {
        s, sep string
        want   int
    }{
        {"a:b:c", ":", 3},
        {"a b c", ":", 1},
        {"^a^b c", "^", 3},
    }
    for _, test := range tests {
        if got := len(strings.Split(test.s, test.sep)); got != test.want {
            t.Errorf("Split(%q,%q) returned %d words, want %d",
                test.s, test.sep, got, test.want)
        }
    }
}

Exercise 11.6: Write benchmarks to compare thePopCountimplementation in Section 2.6.2 with your solutions to Exercise 2.4 and Exercise 2.5. At what point does the table-based approach break even?

// Basically table-based is faster in every test cases.

Exercise 11.7: Write benchmarks forAdd,UnionWith, and other methods of*IntSet(§6.5) using large pseudo-random inputs. How fast can you make these methods run? How does the choice of word size affect performance? How fast isIntSetcompared to a set implementation based on the built-in map type?

// How fast can you make these methods run?

// How does the choice of word size affect performance?
// On 64bit platform, 32 and 64 word size has the same performance. 

// How fast is IntSet compared to a set implementation based on the build-in map type?
// It depends on input. If input is limited in a small range, say [1~MaxInt16), IntSet 
// is about several times faster(UnionWith is order of magnitude faster). But if input is 
// completed random within [1~MaxInt64), set implementation based built-in map is prefer.

Notes:

• The key to a good test is to start by implementing the concrete behavior that you want and only then use functions to simplify the code and eliminate repetition. Best results are rarely obtained by starting with a library of abstract, generic testing functions.