4
\$\begingroup\$

I tried to solve the Problem Euler 67 with golang, because I started to study Go recently.

This is my solution:

package main

import (
    "flag"
    "fmt"
    "io/ioutil"
    "os"
    "strconv"
    "strings"
    "time"
)

func calculateMaxPath(trianglePointer *[][]int, lines int) int {
    trisums := make([][]int, lines)
    triangle := *trianglePointer

    for row := lines - 1; row > -1; row-- {
        trisums[row] = make([]int, row+1)
        for col := 0; col < row+1; col++ {
            if row == lines-1 {
                trisums[row][col] = triangle[row][col]
            } else {
                if trisums[row+1][col] > trisums[row+1][col+1] {
                    trisums[row][col] = triangle[row][col] + trisums[row+1][col]
                } else {
                    trisums[row][col] = triangle[row][col] + trisums[row+1][col+1]
                }
            }
        }
    }

    return trisums[0][0]
}

func openFile() (*[][]int, int) {
    flag.Parse()

    ifile := flag.Arg(0)

    if len(ifile) == 0 {
        println("No File Specified")
        os.Exit(1)
    }

    content, err := ioutil.ReadFile(ifile)

    if err != nil {
        println("Error reading", ifile)
        os.Exit(1)
    }

    strRows := strings.Split(string(content), "\n")
    content = nil

    lines := 0
    for i := len(strRows) - 1; i > 0; i-- {
        if lines == 0 && strRows[i] != "" {
            lines = i + 1
            break
        }
    }

    var strs []string

    pyramid := make([][]int, lines)
    for row := 0; row < lines; row++ {
        strs = strings.Fields(strRows[row])
        pyramid[row] = make([]int, len(strs))

        for col := 0; col < len(strs); col++ {
            pyramid[row][col], _ = strconv.Atoi(strs[col])
        }
    }

    return &pyramid, lines
}

func main() {
    start := time.Now()

    pyramid, lines := openFile()

    greatestSum := calculateMaxPath(pyramid, lines)

    fmt.Printf("\nTotal sum: %v, Elapsed time: %v\n", greatestSum, time.Since(start))
}

What could be a better approach? Coud I use go routines to increase performance?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

I tried to solve the Problem Euler 67 with Go, because I started to study Go recently.

What could be a better approach? Could I use goroutines to increase performance?


Code should be correct, maintainable, robust, reasonably efficient, and, most importantly, readable.

I'm going to skip a full code review and narrowly focus my code review on the use of performance benchmarks. Go has several tools to measure performance, including the Go standard library testing package Benchmark type.


The elapsed time for the program is somewhat interesting but not very useful. Some results from running my program code and your program code several times to prime the Linux file buffer cache:

peterGo:

$ go run euler67.go
7273
175.641µs

Mdsp:

$ go run mdsp.go
Total sum: 7273, Elapsed time: 277.556µs

Here's how I benchmarked your Project Euler Problem 67 maximum sum path algorithm using p067_triangle.txt as input.

BenchmarkEuler67 measures overall (load and sum) performance while ignoring the effects of hardware (for example, HDD I/O), operating system (for example, cached disk data), and other extraneous effects. The triangle has 100 rows with a total of 5050 (= 100 * (100 + 1) / 2) elements.

$ go test euler67_test.go euler67.go -bench=. -benchmem
BenchmarkEuler67-4   13299   89766 ns/op   68440 B/op   210 allocs/op

These are benchmarks for BenchmarkEuler67 components.

$ go test euler67_test.go euler67.go -bench=. -benchmem
BenchmarkLoad-4      16959   70742 ns/op   68440 B/op   210 allocs/op
BenchmarkRow-4     1000000    1137 ns/op   896 B/op       1 allocs/op
BenchmarkSum-4       60830   19595 ns/op   0 B/op         0 allocs/op

BenchmarkLoad measures loading the in-memory text triangle values into a triangle of int slices.

BenchmarkRow measures parsing the text for the maximum (100 integer) triangle row into to a slice of Go ints. parseInts, a specialization, provides an improvement over strings.Fields for the loadTriangle function.

strings.Fields:

BenchmarkLoad-4      10000  114958 ns/op  153304 B/op   310 allocs/op

parseInts:

BenchmarkLoad-4      16959   70742 ns/op   68440 B/op   210 allocs/op

BenchmarkSum measures the fundamental maximum sum path algorithm performance: 19.6 microseconds. The maxPathSum function reduces memory bytes and allocations to zero by reusing the input for intermediate results.

Clearly, the major expense is loading the inefficient input into an efficient data structure for the maximum sum path algorithm.

To see how the code scales, here are benchmarks for a triangle with 1000 rows with a total of 500500 (= 1000 * (1000 + 1) / 2) elements.

BenchmarkEuler67-4     174   6810618 ns/op   5941675 B/op   2015 allocs/op
BenchmarkLoad-4        186   6399151 ns/op   5941685 B/op   2015 allocs/op
BenchmarkRow-4       93747     12505 ns/op      8192 B/op      1 allocs/op
BenchmarkSum-4        1916    622193 ns/op         0 B/op      0 allocs/op

6.8 milliseconds for 1000 rows is not unreasonable.

Improving performance is an iterative process and there is more that we can do, but is it worth it. The CPU, memory, and allocation numbers are small. Unless we expect many iterations, it doesn't seem like further optimization is worth much time, effort, and loss of readability.


euler67.go:

package main

import (
    "bufio"
    "flag"
    "fmt"
    "io"
    "os"
    "strconv"
    "time"
)

func parseInts(s string, buf []int) ([]int, error) {
    buf = buf[:0]
    inInt := false
    i := 0
    for j := 0; j <= len(s); j++ {
        if j == len(s) || ('0' > s[j] || s[j] > '9') {
            if inInt {
                n, err := strconv.Atoi(s[i:j])
                if err != nil {
                    return buf[:0], err
                }
                buf = append(buf, n)
            }
            inInt = false
        } else if !inInt {
            inInt = true
            i = j
        }
    }
    return buf, nil
}

func loadTriangle(r io.Reader) ([][]int, error) {
    var ta [][]int
    s := bufio.NewScanner(r)
    for s.Scan() {
        buf := make([]int, 0, len(ta)+1)
        row, err := parseInts(s.Text(), buf)
        if err != nil {
            return nil, err
        }
        if len(row) != len(ta)+1 {
            err := fmt.Errorf(
                "triangle: %d cols for row %d",
                len(row), len(ta)+1,
            )
            return nil, err
        }
        ta = append(ta, row)
    }
    if err := s.Err(); err != nil {
        return nil, err
    }
    return ta, nil
}

func maxPathSum(ta [][]int) int {
    for r := len(ta) - 2; r >= 0; r-- {
        r0, r1 := ta[r], ta[r+1]
        for c0 := range r0 {
            left, right := r1[c0], r1[c0+1]
            if left >= right {
                r0[c0] += left
            } else {
                r0[c0] += right
            }
        }
    }
    if len(ta) == 0 || len(ta[0]) == 0 {
        return 0
    }
    return ta[0][0]
}

func euler67(r io.Reader) (int, error) {
    ta, err := loadTriangle(r)
    if err != nil {
        return 0, err
    }
    return maxPathSum(ta), nil
}

func since(start time.Time) { fmt.Println(time.Since(start)) }

func main() {
    defer since(time.Now())

    flag.Parse()
    // https://projecteuler.net/project/resources/p067_triangle.txt
    // 100 rows 15.2 kB (15,150 bytes)
    filename := `p067_triangle.txt`
    if len(flag.Arg(0)) > 0 {
        filename = flag.Arg(0)
    }
    f, err := os.Open(filename)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer f.Close()

    sum, err := euler67(f)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    fmt.Println(sum)
}

euler67_test.go:

package main

import (
    "bufio"
    "bytes"
    "io/ioutil"
    "strings"
    "testing"
)

func BenchmarkEuler67(b *testing.B) {
    for N := 0; N < b.N; N++ {
        _, err := euler67(bytes.NewReader(benchData))
        if err != nil {
            b.Fatal(err)
        }
    }
}

func BenchmarkLoad(b *testing.B) {
    for N := 0; N < b.N; N++ {
        _, err := loadTriangle(bytes.NewReader(benchData))
        if err != nil {
            b.Fatal(err)
        }
    }
}

func BenchmarkRow(b *testing.B) {
    var last string
    s := bufio.NewScanner(bytes.NewReader(benchData))
    for s.Scan() {
        last = s.Text()
    }
    if err := s.Err(); err != nil {
        b.Fatal(err)
    }
    cols := len(strings.Fields(last))
    b.ResetTimer()

    for N := 0; N < b.N; N++ {
        buf := make([]int, 0, cols)
        _, err := parseInts(last, buf)
        if err != nil {
            b.Fatal(err)
        }
    }
}

func BenchmarkSum(b *testing.B) {
    for N := 0; N < b.N; N++ {
        b.StopTimer()
        ta, err := loadTriangle(bytes.NewReader(benchData))
        if err != nil {
            b.Fatal(err)
        }
        b.StartTimer()
        _ = maxPathSum(ta)
    }
}

var benchData = func() []byte {
    // https://projecteuler.net/project/resources/p067_triangle.txt
    // 100 rows 15.2 kB (15,150 bytes)
    filename := `p067_triangle.txt`
    data, err := ioutil.ReadFile(filename)
    if err != nil {
        panic(err)
    }
    return data
}()
\$\endgroup\$
1
\$\begingroup\$

I'll skip the performance part of the review which is already deeply covered by peterSO's answer.

Instead let's focus on reviewing the actual code you've provided.

println

print and println builtin functions are a nice way to add debug statements to your code while developing. They don't require an import statement and are a always there in the global namespace.

But.

This functions best used for debugging. There is a good standard way to output text and it lives in the fmt package. Idiomatic Go code should use functions from fmt:

fmt.Println("Wubba Lubba Dub Dub")

Actually I guess print and println landed in the Go when there was no great IDE support, no goimports utility and these functions were introduced to overcome the need to manually add import statements at the top of every file you wish to debug. But that time is long gone.

I suggest you to stick to functions from fmt package. print and println may be considered only for debugging.

A note on stderr

After println call you are using os.Exit(1) to exit your program with non-zero return code.

All error text outputted before the exit should go to stderr. This is already handled by println function internally.

To have this desired behavior with fmt package you can use fmt.Fprintln(os.Stderr, ...).

*[][]int

Most of the time you don't to pass slices by reference. Slices are already a reference type and should be passed by value. It won't trigger a full slice copy.

Also, see this Stack Overflow answer, that describes slice's internals a bit.

Program arguments

You are using functions from flag package in openFile. Better use them in the main and pass filename as argument to openFile; that's more common.

Also, don't forget to check count of provided arguments with flag.NArg as you expect exactly one.

Check this:

if len(ifile) == 0 {
        println("No File Specified")
        os.Exit(1)
}

You are using len(ifile) == 0 test to see that there is no filename provided. But you don't check the upper bound. What if the user calls your program with several arguments?

Sure, it will work just fine taking only the first one.

But does the user expect exactly this behavior when the rest of the arguments are silently discarded?

I bet not.

So I suggest you to check that exactly one argument is specified:

if flag.NArgs() != 1 {
        fmt.Fprintf("usage: euler67 filename")
        os.Exit(1)
}

After this you don't need to test for empty string from flag.Arg(0). Actually empty string will be only in case the user directly called the program with empty argument:

$ euler67 ''

To handle this simply call os.Open (or ioutil.ReadFile in your case) and check the error.

A bit more on error handling

Instead of calling os.Exit(1) in the middle of the random function you can return the error back to main and exit there.

The benefit of this is hardly visible in the small code base but it is a good practice to stick to and will save you later as the code grows.

Remember: return errors and let the caller decide how to handle them. In case of a total failure or when your function name is prefixed with Must call panic. Actually, better never call panic unless you Must.


For a sample rewrite you can check peterSO's answer.

Just remember, in the strive for performance don't forget about correctness ^.^

After all, if it isn't "right", it doesn't matter much how quickly it delivers the wrong results.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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