解决方法 Go 的地图指针问题

Question

我正在解决这个欧拉项目的问题。首先我尝试了蛮力，它花了0.5秒，然后我尝试了动态规划，利用记忆期望一个巨大的改进，但我惊讶的是，结果是0.36秒。

经过一点谷歌搜索，我发现你不能在函数(find_collatz_len)中使用指针到外部地图数据(备忘录)。所以每次下面的函数运行时，它都会复制整个字典。这听起来像是对处理器功率的巨大浪费。

我的问题是什么是一个解决方案，这样我就可以使用一个指针到函数外的映射，以避免复制。

这是我的丑陋代码:

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

Answer 1

映射在底层已经是指针了。传递一个map值将传递一个指针。有关详细信息，请参见为什么切片值有时会过时，而映射值永远不会过时?

当创建一个没有容量提示的映射时，一个映射被分配了足够的内部结构来存储相对较少的条目(大约7个)。随着映射的增长，实现有时需要分配更多的内存和重构(重新散列)映射以容纳更多的元素。如果使用@mkopriva:

所建议的预期最终容量初始化映射，则可以避免这种情况。

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

因此，将分配足够的空间来存储所有条目(在您的示例中为1_000_000)，因此在应用程序的生命周期内不会发生重散列。这将使运行时间从0.3秒减少到0.2秒。

您也可以将int(float64(n)/2)替换为n/2，因为在您使用的整数范围内，它们会给出相同的结果。这将给你进一步5%的提升(0.19秒在我的机器上)。