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

Question

我正在解决这个欧拉计划问题。首先，我尝试了蛮力，花了0.5秒，然后我尝试了动态编程来利用记忆，期望有巨大的改进，但我惊讶地发现结果是0.36秒。经过一点点谷歌搜索，我发现你不能在函数（find_collatz_len）中使用指针来访问外部地图数据（备忘录）。因此，每次运行下面的函数时，它都会复制整个字典。这听起来像是对处理器能力的巨大浪费。我的问题是，什么是解决方法，以便我可以使用指向函数外部映射的指针来避免复制。这是我的丑陋代码：package main//project euler 014 - longest collatz sequenceimport (    "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

地图已经是引擎盖下的指针。传递映射值将传递单个指针。有关详细信息，请参阅为什么切片值有时会过时，但永远不会映射值？

创建没有容量提示的映射时，分配的映射具有足够的内部结构来存储相对较少的条目（大约 7 个）。随着映射的增长，实现有时需要分配更多内存并重新构建（重新哈希）映射以容纳更多元素。如果使用预期的最终容量初始化映射，则可以避免@mkopriva：

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

因此，将分配足够的空间来存储所有条目（在你的示例中），因此在应用的生存期内不会发生重新哈希。这会将运行时间从 0.3 秒减少到 0.2 秒。1_000_000

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