解决 Go 的地图指针问题

Go 中，使用地图指针时，每次函数调用都会复制整个地图，造成性能浪费。解决方法是使用预期的最终容量初始化地图，避免重新哈希。例如，使用 memo := make(map[int]int, 1_000_000) 初始化地图，可以将运行时间从 0.3 秒减少到 0.2 秒。此外，将 int(float64(n)/2) 替换为 n/2 可以进一步提升性能。

我正在解决这个 project euler 问题。首先我尝试了暴力破解，花了 0.5 秒，然后我尝试了动态编程来利用记忆化，期望有巨大的改进，但令我惊讶的是结果是 0.36 秒。

经过一番谷歌搜索后，我发现您不能在函数（find_collat​​z_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())
}

正确答案

地图已经是引擎盖下的指针。传递映射值将传递单个指针。详情见why slice values can sometimes go stale but never map values?

当创建没有容量提示的映射时，映射会分配足够的内部结构来存储相对少量的条目（大约 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 秒）。

今天关于《解决 Go 的地图指针问题》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！