解决方法 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

地图已经是引擎盖下的指针。传递映射值将传递单个指针。有关详细信息，请参阅为什么切片值有时会过时，但永远不会映射值？创建没有容量提示的映射时，分配的映射具有足够的内部结构来存储相对较少的条目（大约 7 个）。随着映射的增长，实现有时需要分配更多内存并重新构建（重新哈希）映射以容纳更多元素。如果使用预期的最终容量初始化映射，则可以避免@mkopriva：memo&nbsp;:=&nbsp;make(map[int]int,&nbsp;1_000_000).因此，将分配足够的空间来存储所有条目（在你的示例中），因此在应用的生存期内不会发生重新哈希。这会将运行时间从 0.3 秒减少到 0.2 秒。1_000_000您也可以将 替换为 ，因为在您使用的整数范围内，它们会给出相同的结果。这将进一步提高5%（在我的机器上为0.19秒）。int(float64(n)/2)n/2