2
\$\begingroup\$

Solved one of the easiest problems from acm.timus.ru.

1001. Reverse Root

The input stream contains a set of integer numbers Aᵢ (0 ≤ Aᵢ ≤ 10¹⁸). The numbers are separated by any number of spaces and line breaks. A size of the input stream does not exceed 256 KB.

For each number Aᵢ from the last one till the first one you should output its square root. Each square root should be printed in a separate line with at least four digits after decimal point.

I would like to know why my solution is relatively slow (execution time is 1s) and uses so much memory (7 072 KB)? Compared to C++: 0.093s and 408 KB of memory.


package main

import "fmt"
import "math"

var a []int64

func main() {
    for {
        var x int64
        k, _ := fmt.Scan(&x)
        if k != 1 {
            break
        }
        a = append(a,x)
    }
    n := len(a)

    for n > 0 {
        n--
        fmt.Printf("%.4f\n", math.Sqrt(float64(a[n])))
    }
}

Is the significantly larger resource consumption due to garbage collection and imported libraries or just my code is inefficient?

\$\endgroup\$
2
0
\$\begingroup\$

A benchmark is a scientific experiment.

An essential feature of a scientific experiment is that it be reproducible.

You do not provide any C++ code. You do provide some Go code. You do not define your methods for measuring CPU and memory. You provide some undefined CPU and memory measurements.

Your Go code looks inefficient.


1001. Reverse Root

The input stream contains a set of integer numbers Aᵢ (0 ≤ Aᵢ ≤ 10¹⁸). The numbers are separated by any number of spaces and line breaks. A size of the input stream does not exceed 256 KB.

For each number Aᵢ from the last one till the first one you should output its square root. Each square root should be printed in a separate line with at least four digits after decimal point.


Compare my Go code (revroot.go) to your slower Go code (revroot.ivan.go):

$ ls -s -h revroot.in.data
256K revroot.in.data
$

$ go build revroot.go && time ./revroot < revroot.in.data > revroot.out.data
real    0m0.007s
user    0m0.007s
sys     0m0.000s
$ go build revroot.go && time ./revroot < revroot.in.data > revroot.out.data
real    0m0.008s
user    0m0.008s
sys     0m0.000s
$ ls -s -h revroot.out.data
208K revroot.out.data
$

$ go build revroot.ivan.go && time ./revroot.ivan < revroot.in.data > revroot.out.data
real    0m0.251s
user    0m0.141s
sys     0m0.113s
$ go build revroot.ivan.go && time ./revroot.ivan < revroot.in.data > revroot.out.data
real    0m0.245s
user    0m0.147s
sys     0m0.100s
$ ls -s -h revroot.out.data
208K revroot.out.data
$

revroot.go:

package main

import (
    "bufio"
    "fmt"
    "io"
    "math"
    "os"
    "strconv"
)

func RevRoot(in io.Reader, out io.Writer) error {
    var a []float64

    s := bufio.NewScanner(in)
    s.Split(bufio.ScanWords)
    for s.Scan() {
        i, err := strconv.ParseUint(s.Text(), 10, 64)
        if err != nil {
            return err
        }
        a = append(a, math.Sqrt(float64(i)))
    }
    if err := s.Err(); err != nil {
        return err
    }

    w, ok := out.(*bufio.Writer)
    if !ok {
        w = bufio.NewWriter(out)
    }
    defer w.Flush()
    buf := make([]byte, 0, 32)
    for n := len(a) - 1; n >= 0; n-- {
        buf = strconv.AppendFloat(buf[:0], a[n], 'f', 4, 64)
        buf = append(buf, '\n')
        _, err := w.Write(buf)
        if err != nil {
            return err
        }
    }
    err := w.Flush()
    if err != nil {
        return err
    }

    return nil
}

func main() {
    err := RevRoot(os.Stdin, os.Stdout)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
    }
    return
}

revroot.ivan.go:

package main

import "fmt"
import "math"

var a []int64

func main() {
    for {
        var x int64
        k, _ := fmt.Scan(&x)
        if k != 1 {
            break
        }
        a = append(a, x)
    }
    n := len(a)

    for n > 0 {
        n--
        fmt.Printf("%.4f\n", math.Sqrt(float64(a[n])))
    }
}

In Go, to measure performance we run benchmarks. We exclude I/O and other OS functions.

$ go test revroot_test.go revroot.go -run=! -bench=. -benchmem
BenchmarkRevRoot-4   249   4775861 ns/op   833577 B/op   13202 allocs/op
$ 

My RevRoot function takes 4,775,861 nanoseconds (0.004,775,861 seconds) for 13,177 square roots.

revroot_test.go:

package main

import (
    "bytes"
    "io/ioutil"
    "math/rand"
    "strconv"
    "strings"
    "testing"
)

func BenchmarkRevRoot(b *testing.B) {
    buf := bytes.NewBuffer(make([]byte, 0, 256*1024))
    r := rand.New(rand.NewSource(42))
    for {
        buf.WriteString(strconv.Itoa(r.Int()))
        buf.WriteString("\n")
        if buf.Len() > 256*1024-256 {
            break
        }
    }
    data := buf.String()

    b.ResetTimer()
    for N := 0; N < b.N; N++ {
        err := RevRoot(strings.NewReader(data), ioutil.Discard)
        if err != nil {
            b.Fatal(err)
        }
    }
}
\$\endgroup\$

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.