0

I was solving this Project Euler question. First I tried brute force and it took 0.5 seconds and then I tried the dynamic programming to utilize memoization expecting a huge improvement but I surprised that the result was 0.36 seconds.

After a little bit of googling I found out you can not use a pointer in a function (find_collatz_len) to an outside map data (memo). So each time the function below runs it copies over the entire dictionary. That sounds like a huge waste of processor power.

My question is what is a workaround so that I can use a pointer to a map outside the function to avoid the copying.

Here is my ugly code:

package main
//project euler 014 - longest collatz sequence

import (
    "fmt"
    "time"
)

func find_collatz_len(n int, memo map[int]int) int {
    counter := 1
    initital_value := n
    for n != 1 {
        counter++
        if n < initital_value {
            counter = counter + memo[n]
            break
        }
        if n%2 == 0 {
            n = int(float64(n)/2)
        } else {
            n = n*3+1
        }
    }
    memo[initital_value] = counter
    return counter
}

func main() {
    start := time.Now()
    max_length := 0
    number := 0
    current_length := 0
    memo := make(map[int]int)
    for i:=1; i<1_000_000; i++ {
        current_length = find_collatz_len(i, memo)
        if current_length > max_length {
            max_length = current_length 
            number = i
        }
    }
    fmt.Println(max_length, number)
    fmt.Println("Time:", time.Since(start).Seconds())
}
icza
  • 389,944
  • 63
  • 907
  • 827
Kolom
  • 217
  • 1
  • 11
  • 5
    *"So each time the function below runs it copies over the entire dictionary."* -- Nope, that's not what's happening. – mkopriva Oct 06 '21 at 10:34
  • 5
    There is no “map pointer issue”. You can use a pointer if you want, there’s just no reason to here. – JimB Oct 06 '21 at 11:12
  • @JimB but when I do it says something in lines of "the item is not scriptable" – Kolom Oct 06 '21 at 11:21
  • 4
    *"the item is not scriptable"* -- is not an actual error message from the Go compiler nor runtime so it's hard to determine what the actual error you've encountered is. And without knowing the actual error we can't provide suggestions how to fix it. – mkopriva Oct 06 '21 at 11:24
  • Could you try your code on the playground? https://play.golang.org It will not have arbitrary restrictions (modulo fake time and no filesystem and network access for, I hope, obvious reasons). – kostix Oct 06 '21 at 11:26
  • 2
    As far as optimization is concerned, you could use `make(map[int]int, 1_000_000)` to initialize the map to its final size and thereby avoid having the runtime grow the map dynamically. (this cuts the time by almost a half on my machine [from ~0.28 to ~0.16]) – mkopriva Oct 06 '21 at 11:28
  • 7
    Maps are already pointers under the hood. Passing a map value will pass a single pointer. As suggested by @mkopriva, initialize the map with the expected final capacity: `make(map[int]int, 1_000_000)`. This will reduce the runtime from 0.3 sec to 0.2 sec. You can also replace `int(float64(n)/2)` with `n/2`, as in the integer range you use, they give the same result. This will give you further 5% boost (0.19sec on my machine). – icza Oct 06 '21 at 11:31
  • 1
    "you can not use a pointer in a function (find_collatz_len) to an outside map data (memo)" - none of this is right. You can use a pointer to a map, but it's unnecessary, as a map is already a pointer under the hood. You can never take a pointer to a map *element*. Inside/outside function is irrelevant. – Adrian Oct 06 '21 at 13:20
  • Thanks @icza for clear explanation without beating me with your knowledge. Can you make that an answer so I can choose. By the way, I really don't understand negative votes on the question. SE is a weird place. – Kolom Oct 06 '21 at 16:54

1 Answers1

5

Maps are already pointers under the hood. Passing a map value will pass a single pointer. For details, see why slice values can sometimes go stale but never map values?

When creating a map without a capacity hint, a map is allocated with internal structure enough to store a relatively small number of entries (around 7). As the map grows, the implementation sometimes needs to allocate more memory and restructure (rehash) the map to accommodate more elements. This can be avoided if you initialize the map with the expected final capacity as suggested by @mkopriva:

memo := make(map[int]int, 1_000_000).

As a result, enough room will be allocated to store all entries (1_000_000 in your example), so a rehash will not happen during the lifetime of your app. This will reduce the runtime from 0.3 sec to 0.2 sec.

You can also replace int(float64(n)/2) with n/2, as in the integer range you use, they give the same result. This will give you further 5% boost (0.19 sec on my machine).

icza
  • 389,944
  • 63
  • 907
  • 827