4
\$\begingroup\$

For me, learning the basics of a new programming language is best done through some easy to intermediate challenges. Here's one that's rather well known and relatively simple - determine if a triangle is equilateral, isosceles, or scalene.

Here's my try in Golang. Since I'm totally new to Go, I'm pretty sure this can be improved. How can I get this code to be more, well, Go-like? On the bottom, there's a test suit (was not written by me thou).

// package triangle contains methods for determining if a triangle is equilateral, isosceles, or scalene
package triangle

import (
    "sort"
    "math"
)

type Kind int

const (
    NaT = 1 // not a triangle
    Equ = 2 // equilateral
    Iso = 3 // isosceles
    Sca = 4 // scalene
)

// KindForomSides checks if a triangle is equilateral, isosceles, or scalene
func KindFromSides(a, b, c float64) Kind {
    var k Kind

    if !IsTriangle(a, b, c) {
        k = NaT
        return k
    } else if a == b && a == c {
        k = Equ
        return k
    } else if a == b || a == c || b == c {
        k = Iso
        return k
    } else {
        k = Sca
        return k
    }
}

// IsTriangle checks for triangle inequality
func IsTriangle(a, b, c float64) bool {
    var sides []float64
    sides = append(sides, a, b, c)
    sort.Float64s(sides)
    sides[0], sides[1], sides[2] = a, b, c
    // Check if side values are not NaN or Infinity
    for _, value := range sides {
        if math.IsNaN(value) || math.IsInf(value, 0) {
            return false
        }
    }
    // Check if sides are not negative values
    if !(a > float64(0) && b > float64(0) && c > float64(0)) {
        return false
    }

    if a + b < c || b + c < a || c + a < b {
        return false
    }

    return true
}

The test suit.

package triangle

import (
    "math"
    "testing"
)

type testCase struct {
    want    Kind
    a, b, c float64
}

// basic test cases
var testData = []testCase{
    {Equ, 2, 2, 2},    // same length
    {Equ, 10, 10, 10}, // a little bigger
    {Iso, 3, 4, 4},    // last two sides equal
    {Iso, 4, 3, 4},    // first and last sides equal
    {Iso, 4, 4, 3},    // first two sides equal
    {Iso, 10, 10, 2},  // again
    {Iso, 2, 4, 2},    // a "triangle" that is just a line is still OK
    {Sca, 3, 4, 5},    // no sides equal
    {Sca, 10, 11, 12}, // again
    {Sca, 5, 4, 2},    // descending order
    {Sca, .4, .6, .3}, // small sides
    {Sca, 1, 4, 3},    // a "triangle" that is just a line is still OK
    {Sca, 5, 4, 6},    // 2a == b+c looks like equilateral, but isn't always.
    {Sca, 6, 4, 5},    // 2a == b+c looks like equilateral, but isn't always.
    {NaT, 0, 0, 0},    // zero length
    {NaT, 3, 4, -5},   // negative length
    {NaT, 1, 1, 3},    // fails triangle inequality
    {NaT, 2, 5, 2},    // another
    {NaT, 7, 3, 2},    // another
}

// generate cases with NaN and Infs, append to basic cases
func init() {
    nan := math.NaN()
    pinf := math.Inf(1)
    ninf := math.Inf(-1)
    nf := make([]testCase, 4*4*4)
    i := 0
    for _, a := range []float64{3, nan, pinf, ninf} {
        for _, b := range []float64{4, nan, pinf, ninf} {
            for _, c := range []float64{5, nan, pinf, ninf} {
                nf[i] = testCase{NaT, a, b, c}
                i++
            }
        }
    }
    testData = append(testData, nf[1:]...)
}

// Test that the kinds are not equal to each other.
// If they are equal, then TestKind will return false positives.
func TestKindsNotEqual(t *testing.T) {
    kindsAndNames := []struct {
        kind Kind
        name string
    }{
        {Equ, "Equ"},
        {Iso, "Iso"},
        {Sca, "Sca"},
        {NaT, "NaT"},
    }

    for i, pair1 := range kindsAndNames {
        for j := i + 1; j < len(kindsAndNames); j++ {
            pair2 := kindsAndNames[j]
            if pair1.kind == pair2.kind {
                t.Fatalf("%s should not be equal to %s", pair1.name, pair2.name)
            }
        }
    }
}

func TestKind(t *testing.T) {
    for _, test := range testData {
        got := KindFromSides(test.a, test.b, test.c)
        if got != test.want {
            t.Fatalf("Triangle with sides, %g, %g, %g = %v, want %v",
                test.a, test.b, test.c, got, test.want)
        }
    }
}

func BenchmarkKind(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, test := range testData {
            KindFromSides(test.a, test.b, test.c)
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

few things to say,

the Kind constants can be declared using the iota keyword.

// Triangle kinds
const (
    NaT = iota // not a triangle
    Equ        // equilateral
    Iso        // isosceles
    Sca        // scalene
)

Some comments are broken btw, the linters will complain. Do you use one ? Using atom and the go-plus plugin, it lints out of the box. Something similar must exists for vscode, for example.

Also, the naming triangle.IsTriangle does look repetitive, it is preferably avoided.

The KindFromSides function can declare the return variable in the out signature parameter and set its default value to the default original else case. It is somewhat less complex, so somewhat preferred.

// KindFromSides checks if a triangle is equilateral, isosceles, or scalene
func KindFromSides(a,b,c float64) (k Kind) {
    k = Sca

    if !IsTriangle(a,b,c) {
        k = NaT
    } else if a == b && a == c {
        k = Equ
    } else if a == b || a == c || b == c {
        k = Iso
    }
    return k
}

You can also re arrange the constants declaration so Sca is the zero value


// Triangle kinds
const (
    Sca = iota // scalene
    NaT        // not a triangle
    Equ        // equilateral
    Iso        // isosceles
)

// KindFromSides checks if a triangle is equilateral, isosceles, or scalene
func KindFromSides(sides []float64) (k Kind) {
    a := sides[0]
    b := sides[1]
    c := sides[2]

    if !IsTriangle(sides) {
        k = NaT
    } else if a == b && a == c {
        k = Equ
    } else if a == b || a == c || b == c {
        k = Iso
    }
    return k
}

Although, imho, it is better written like this


// Triangle kinds
const (
    NaT = iota // not a triangle
    Equ        // equilateral
    Iso        // isosceles
    Sca        // scalene
)

// KindFromSides checks if a triangle is equilateral, isosceles, or scalene
func KindFromSides(sides []float64) (k Kind) {
    a := sides[0]
    b := sides[1]
    c := sides[2]

    if IsTriangle(sides) {
        k = Sca
        if a == b && a == c {
            k = Equ
        } else if a == b || a == c || b == c {
            k = Iso
        }
    }
    return k
}

The tests are OK, although you don't use any un-exported triangle symbol, so it should belong to the triangle_test package.

Now i ran the benchmark,

$ go test -bench=. -benchmem
goos: linux
goarch: amd64
pkg: test/triangle
BenchmarkKind-4       200000         11551 ns/op        5248 B/op        164 allocs/op
PASS
ok      test/triangle   2.432s

That is a lot of allocations for such thing.

I re run the benchmark, enabling the memory profiler,

$ go test -bench=. -benchmem -memprofile=mem.out

Then open it

$ go tool pprof mem.out 
File: triangle.test
Type: alloc_space
Time: Dec 15, 2019 at 8:16pm (CET)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 539.52MB, 100% of 539.52MB total
      flat  flat%   sum%        cum   cum%
  273.51MB 50.70% 50.70%   273.51MB 50.70%  sort.Float64s
  266.01MB 49.30%   100%   539.52MB   100%  test/triangle.IsTriangle
         0     0%   100%   539.52MB   100%  test/triangle.BenchmarkKind
         0     0%   100%   539.52MB   100%  test/triangle.KindFromSides
         0     0%   100%   539.52MB   100%  testing.(*B).launch
         0     0%   100%   539.52MB   100%  testing.(*B).runN
(pprof) list Float
Total: 539.52MB
ROUTINE ======================== sort.Float64s in /home/mh-cbon/.gvm/gos/go1.12.7/src/sort/sort.go
  273.51MB   273.51MB (flat, cum) 50.70% of Total
         .          .    306:// Ints sorts a slice of ints in increasing order.
         .          .    307:func Ints(a []int) { Sort(IntSlice(a)) }
         .          .    308:
         .          .    309:// Float64s sorts a slice of float64s in increasing order
         .          .    310:// (not-a-number values are treated as less than other values).
  273.51MB   273.51MB    311:func Float64s(a []float64) { Sort(Float64Slice(a)) }
         .          .    312:
         .          .    313:// Strings sorts a slice of strings in increasing order.
         .          .    314:func Strings(a []string) { Sort(StringSlice(a)) }
         .          .    315:
         .          .    316:// IntsAreSorted tests whether a slice of ints is sorted in increasing order.
(pprof) list IsTriangle
Total: 539.52MB
ROUTINE ======================== test/triangle.IsTriangle in /home/mh-cbon/gow/src/test/triangle/main.go
  266.01MB   539.52MB (flat, cum)   100% of Total
         .          .     35:}
         .          .     36:
         .          .     37:// IsTriangle checks for triangle inequality
         .          .     38:func IsTriangle(a, b, c float64) bool {
         .          .     39:   var sides []float64
  266.01MB   266.01MB     40:   sides = append(sides, a, b, c)
         .   273.51MB     41:   sort.Float64s(sides)
         .          .     42:   sides[0], sides[1], sides[2] = a, b, c
         .          .     43:   // Check if side values are not NaN or Infinity
         .          .     44:   for _, value := range sides {
         .          .     45:       if math.IsNaN(value) || math.IsInf(value, 0) {
         .          .     46:           return false
(pprof) exit

It shows this algorithm allocates twice, within triangle.IsTriangle, then within sort.Float64s.

Unfortunately, sort.Float64s allocation is not avoidable, unless you receive a sort.Float64 slice directly, but that might sound a bit awkward for the api signature.

In below proposal the allocation within IsTriangle function is removed by receiving directly a slice of float64s. To improve more the allocation and prevent false positive the tests are also updated.

main.go

// package triangle contains methods for determining if a triangle is equilateral, isosceles, or scalene
package triangle

import (
    "math"
    "sort"
)

// Kind of triangle
type Kind int

// Triangle kinds
const (
    NaT = iota // not a triangle
    Equ        // equilateral
    Iso        // isosceles
    Sca        // scalene
)

// KindFromSides checks if a triangle is equilateral, isosceles, or scalene
func KindFromSides(sides []float64) (k Kind) {
    k = Sca

    a := sides[0]
    b := sides[1]
    c := sides[2]

    if !IsTriangle(sides) {
        k = NaT
    } else if a == b && a == c {
        k = Equ
    } else if a == b || a == c || b == c {
        k = Iso
    }
    return k
}

// IsTriangle checks for triangle inequality
func IsTriangle(sides []float64) bool {
    // sides := []float64{a, b, c}

    // Check if side values are not NaN or Infinity
    for _, value := range sides {
        if math.IsNaN(value) || math.IsInf(value, 0) {
            return false
        }
    }
    sort.Float64s(sides)

    // sides[0], sides[1], sides[2] = a, b, c
    a, b, c := sides[0], sides[1], sides[2] // instead ?

    // Check if sides are not negative values
    if !(a > float64(0) && b > float64(0) && c > float64(0)) {
        return false
    }

    if a+b < c || b+c < a || c+a < b {
        return false
    }

    return true
}

main_test.go

package triangle

import (
    "math"
    "testing"
)

type testCase struct {
    want    Kind
    a, b, c float64
}

// basic test cases
var testData = []testCase{
    {Equ, 2, 2, 2},    // same length
    {Equ, 10, 10, 10}, // a little bigger
    {Iso, 3, 4, 4},    // last two sides equal
    {Iso, 4, 3, 4},    // first and last sides equal
    {Iso, 4, 4, 3},    // first two sides equal
    {Iso, 10, 10, 2},  // again
    {Iso, 2, 4, 2},    // a "triangle" that is just a line is still OK
    {Sca, 3, 4, 5},    // no sides equal
    {Sca, 10, 11, 12}, // again
    {Sca, 5, 4, 2},    // descending order
    {Sca, .4, .6, .3}, // small sides
    {Sca, 1, 4, 3},    // a "triangle" that is just a line is still OK
    {Sca, 5, 4, 6},    // 2a == b+c looks like equilateral, but isn't always.
    {Sca, 6, 4, 5},    // 2a == b+c looks like equilateral, but isn't always.
    {NaT, 0, 0, 0},    // zero length
    {NaT, 3, 4, -5},   // negative length
    {NaT, 1, 1, 3},    // fails triangle inequality
    {NaT, 2, 5, 2},    // another
    {NaT, 7, 3, 2},    // another
}

// generate cases with NaN and Infs, append to basic cases
func init() {
    nan := math.NaN()
    pinf := math.Inf(1)
    ninf := math.Inf(-1)
    nf := make([]testCase, 4*4*4)
    i := 0
    for _, a := range []float64{3, nan, pinf, ninf} {
        for _, b := range []float64{4, nan, pinf, ninf} {
            for _, c := range []float64{5, nan, pinf, ninf} {
                nf[i] = testCase{NaT, a, b, c}
                i++
            }
        }
    }
    testData = append(testData, nf[1:]...)
}

// Test that the kinds are not equal to each other.
// If they are equal, then TestKind will return false positives.
func TestKindsNotEqual(t *testing.T) {
    kindsAndNames := []struct {
        kind Kind
        name string
    }{
        {Equ, "Equ"},
        {Iso, "Iso"},
        {Sca, "Sca"},
        {NaT, "NaT"},
    }

    for i, pair1 := range kindsAndNames {
        for j := i + 1; j < len(kindsAndNames); j++ {
            pair2 := kindsAndNames[j]
            if pair1.kind == pair2.kind {
                t.Fatalf("%s should not be equal to %s", pair1.name, pair2.name)
            }
        }
    }
}

func TestKind(t *testing.T) {
    sides := make([]float64, 3)
    for _, test := range testData {
        sides[0] = test.a
        sides[1] = test.b
        sides[2] = test.c
        got := KindFromSides(sides)
        if got != test.want {
            t.Fatalf("Triangle with sides, %g, %g, %g = %v, want %v",
                test.a, test.b, test.c, got, test.want)
        }
    }
}

func BenchmarkKind(b *testing.B) {
    sides := make([]float64, 3)
    for i := 0; i < b.N; i++ {
        for _, test := range testData {
            sides[0] = test.a
            sides[1] = test.b
            sides[2] = test.c
            KindFromSides(sides)
        }
    }
}

Benchmark is now

$ go test -bench=. -benchmem -memprofile=mem.out
goos: linux
goarch: amd64
pkg: test/triangle
BenchmarkKind-4       500000          2728 ns/op         608 B/op         19 allocs/op
PASS
ok      test/triangle   1.397s
$ go tool pprof mem.out 
File: triangle.test
Type: alloc_space
Time: Dec 15, 2019 at 8:20pm (CET)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 301.01MB, 99.83% of 301.51MB total
Dropped 13 nodes (cum <= 1.51MB)
      flat  flat%   sum%        cum   cum%
  301.01MB 99.83% 99.83%   301.01MB 99.83%  sort.Float64s
         0     0% 99.83%   301.01MB 99.83%  test/triangle.BenchmarkKind
         0     0% 99.83%   301.01MB 99.83%  test/triangle.IsTriangle
         0     0% 99.83%   301.01MB 99.83%  test/triangle.KindFromSides
         0     0% 99.83%   301.01MB 99.83%  testing.(*B).launch
         0     0% 99.83%   301.51MB   100%  testing.(*B).runN
(pprof) exit

In below version, a type Triangle is defined as []float64, methods are attached to it, and sort.Sort* functions are replaced with specialized functions exposed by the package https://github.com/AlasdairF/Sort to reach 0 allocations.

main.go

// package triangle contains methods for determining if a triangle is equilateral, isosceles, or scalene
package triangle

import (
    "math"

    "github.com/AlasdairF/Sort/Float64"
)

type Triangle []float64

// Kind of triangle
type Kind int

// Triangle kinds
const (
    NaT = iota // not a triangle
    Equ        // equilateral
    Iso        // isosceles
    Sca        // scalene
)

func (sides Triangle) Kind() (k Kind) {
    a := sides[0]
    b := sides[1]
    c := sides[2]

    if sides.IsValid() {
        k = Sca
        if a == b && a == c {
            k = Equ
        } else if a == b || a == c || b == c {
            k = Iso
        }
    }
    return k
}

func (sides Triangle) IsValid() bool {
    // Check if side values are not NaN or Infinity
    for _, value := range sides {
        if math.IsNaN(value) || math.IsInf(value, 0) {
            return false
        }
    }
    sortFloat64.StableDesc(sides)

    a, b, c := sides[0], sides[1], sides[2] // instead ?

    // Check if sides are not negative values
    if !(a > float64(0) && b > float64(0) && c > float64(0)) {
        return false
    }

    if a+b < c || b+c < a || c+a < b {
        return false
    }

    return true
}

main_test.go

package triangle

import (
    "math"
    "testing"
)

type testCase struct {
    want    Kind
    a, b, c float64
}

// basic test cases
var testData = []testCase{
    {Equ, 2, 2, 2},    // same length
    {Equ, 10, 10, 10}, // a little bigger
    {Iso, 3, 4, 4},    // last two sides equal
    {Iso, 4, 3, 4},    // first and last sides equal
    {Iso, 4, 4, 3},    // first two sides equal
    {Iso, 10, 10, 2},  // again
    {Iso, 2, 4, 2},    // a "triangle" that is just a line is still OK
    {Sca, 3, 4, 5},    // no sides equal
    {Sca, 10, 11, 12}, // again
    {Sca, 5, 4, 2},    // descending order
    {Sca, .4, .6, .3}, // small sides
    {Sca, 1, 4, 3},    // a "triangle" that is just a line is still OK
    {Sca, 5, 4, 6},    // 2a == b+c looks like equilateral, but isn't always.
    {Sca, 6, 4, 5},    // 2a == b+c looks like equilateral, but isn't always.
    {NaT, 0, 0, 0},    // zero length
    {NaT, 3, 4, -5},   // negative length
    {NaT, 1, 1, 3},    // fails triangle inequality
    {NaT, 2, 5, 2},    // another
    {NaT, 7, 3, 2},    // another
}

// generate cases with NaN and Infs, append to basic cases
func init() {
    nan := math.NaN()
    pinf := math.Inf(1)
    ninf := math.Inf(-1)
    nf := make([]testCase, 4*4*4)
    i := 0
    for _, a := range []float64{3, nan, pinf, ninf} {
        for _, b := range []float64{4, nan, pinf, ninf} {
            for _, c := range []float64{5, nan, pinf, ninf} {
                nf[i] = testCase{NaT, a, b, c}
                i++
            }
        }
    }
    testData = append(testData, nf[1:]...)
}

// Test that the kinds are not equal to each other.
// If they are equal, then TestKind will return false positives.
func TestKindsNotEqual(t *testing.T) {
    kindsAndNames := []struct {
        kind Kind
        name string
    }{
        {Equ, "Equ"},
        {Iso, "Iso"},
        {Sca, "Sca"},
        {NaT, "NaT"},
    }

    for i, pair1 := range kindsAndNames {
        for j := i + 1; j < len(kindsAndNames); j++ {
            pair2 := kindsAndNames[j]
            if pair1.kind == pair2.kind {
                t.Fatalf("%s should not be equal to %s", pair1.name, pair2.name)
            }
        }
    }
}

func TestTriangleKind(t *testing.T) {
    tr := Triangle(make([]float64, 3))
    for _, test := range testData {
        tr[0] = test.a
        tr[1] = test.b
        tr[2] = test.c
        got := tr.Kind()
        if got != test.want {
            t.Fatalf("Triangle with sides, %g, %g, %g = %v, want %v",
                test.a, test.b, test.c, got, test.want)
        }
    }
}

func BenchmarkTriangleKind(b *testing.B) {
    tr := Triangle(make([]float64, 3))
    for i := 0; i < b.N; i++ {
        for _, test := range testData {
            tr[0] = test.a
            tr[1] = test.b
            tr[2] = test.c
            tr.Kind()
        }
    }
}

and the benchmark result,

$ go test -bench=Triangle -benchmem -memprofile=mem.out
goos: linux
goarch: amd64
pkg: test/triangle
BenchmarkTriangleKind-4       384340          2970 ns/op           0 B/op          0 allocs/op
PASS
ok      test/triangle   1.181s

The benchmarks shows a relative slower speed, it performed 384340 iterations, with each took 2970ns. That is because the cpu clock is reduced to prevent noise and energy consumtpion. if i am to let it go full speed, it shows:

$ go test -bench=Triangle -benchmem -memprofile=mem.out -count 4
goos: linux
goarch: amd64
pkg: test/triangle
BenchmarkTriangleKind-4      1374426           869 ns/op           0 B/op          0 allocs/op
BenchmarkTriangleKind-4      1383519           871 ns/op           0 B/op          0 allocs/op
BenchmarkTriangleKind-4      1376869           872 ns/op           0 B/op          0 allocs/op
BenchmarkTriangleKind-4      1374054           873 ns/op           0 B/op          0 allocs/op
PASS
ok      test/triangle   8.326s
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you very much for this comprehensive feedback! \$\endgroup\$ – baduker Dec 16 '19 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.