7
\$\begingroup\$

This piece of code calculates the sum of all prime numbers below 1 million.

It stood out to me that the Ruby script is around 20% faster. I know that Go should be faster just for being a compiled language. So how can I make the Go code run faster than it already does?

I'm interested in solutions involving goroutines, pointers, both, etc.

In Go:

Execution time: ~4.6s

package main

import (
    "fmt"
    "time"
)

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

    // Create slice containing values from 0 to 1 million
    a := []int{}
    for i := 0; i < 1000000; i++ {
        a = append(a, i)
    }

    done := false
    factor := 1
    for !done {
        // Get the next factor to be used as a filter for slice `a` 
        factor = nextPrime(a, factor)

        var modified bool
        // Filtering slice `a`
        for i, v := range a {
            if v%factor == 0 && v > factor {
                a[i] = 0 // This is equivalent to eliminating the value
                modified = true
            }
        }

        if !modified {
            done = true
        }
    }

    var sum int
    for _, v := range a {
        sum += v
    }
    fmt.Println(sum - 1)

    t2 := time.Now()
    fmt.Println("Execution duration:", t2.Sub(t1))
}

// Doesn't return a prime literaly, but the least value to be used
// to filter out non prime numbers from an array or slice
func nextPrime(a []int, factor int) (newFactor int) {
    for _, v := range a {
        if v > factor {
            newFactor = v
            break
        }
    }
    return
}

In Ruby:

Execution time: ~3.5s

t1 = Time.now

def next_prime(a, t)
  a.each { |m| return m if m > t }
end

a=(2..999_999).to_a

complete = false

until complete
  t ||= 1
  t = next_prime(a, t)
  presize = a.size
  a.map! { |m| m%t == 0 && m > t ? nil : m }
  a.compact!
  complete = true if a.size == presize # when factoring stops shortening the array, we're done
end

r = 0
a.each { |m| r+=m }
puts r

t2 = Time.now
puts t2 - t1
\$\endgroup\$
  • \$\begingroup\$ @sargas Code Review regulars are generally not fond of "A vs. B" questions, as those are more likely to be relevant prior to the code being written (or implemented), as opposed to code review time. Mind you, we can still review your code, but it's possible you will get down-votes for this reason. \$\endgroup\$ – Phrancis Oct 22 '15 at 0:21
  • 1
    \$\begingroup\$ @sargas more or less what Phrancis said. I tend to simply ignore A vs B questions, but I knee jerked with a vote when I saw one in two different languages. I was going to vote to close as too broad because of it. I missed the part where you were only asking for a review of the Go. I added some quote blocks to clarify which code should be reviewed. Honestly, thanks for pinging me, because I was mistaken. \$\endgroup\$ – RubberDuck Oct 22 '15 at 0:25
  • \$\begingroup\$ @RubberDuck Thanks for helping me edit this into a more clear question. Should I still remove to Ruby portion of the question? I still thinks it is relevant since I'd like to know how I can improve the Go solution into a faster version. Perhaps using pointers rather than copies? \$\endgroup\$ – sargas Oct 22 '15 at 0:32
  • \$\begingroup\$ @sargas I'd leave it. You're right. It is relevant. Unfortunately, I don't know Go, so I won't be of much help on that front. Sorry again for my misunderstanding. \$\endgroup\$ – RubberDuck Oct 22 '15 at 0:33
  • 3
    \$\begingroup\$ @RubberDuck I can only thank you for the help and the positive attitude. \$\endgroup\$ – sargas Oct 22 '15 at 0:34
6
\$\begingroup\$

I don't know Ruby, and cannot infer how similar are the algorithms (if they are significantly different, there is no sense to compare performance). However I can point some performance problems in the code.

The range loop

    for i, v := range a {
        if v%factor == 0 && v > factor {
            a[i] = 0
            modified = true
        }
    }

does a lot of unnecessary tests. A (more controlled) for loop seems to suite better:

    for i := factor*factor; i < 10000000; i += factor {
        a[i] = 0
    }

The search for next prime starts from the very beginning of a - rendering the search effectively quadratic. There is no need to search an initial [0, factor] slice; start with factor + 1:

    for _, v := range a[factor + 1:] { 
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This solution got the execution time down to 54ms! I'm assuming i := factor*factor still causes the loop to revisit some indexes of a, but the revisits are way less than scanning the entire array? \$\endgroup\$ – sargas Oct 22 '15 at 5:11

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.