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())
}

CodePudding user response：

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).