为什么 Go map 与 slice 性能在这里有 10 倍的速度差异

Question

我刚刚解决了 Project Euler 上的问题 23，但我注意到 map[int]bool 和 []bool 在性能方面存在很大差异。

我有一个总结一个数的真除数的函数：

func divisorsSum(n int) int {
    sum := 1
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            sum += i
            if n/i != i {
                sum += n / i
            }
        }
    }
    return sum
}

然后在主要我这样做：

func main() {
    start := time.Now()
    defer func() {
        elapsed := time.Since(start)
        fmt.Printf("%s\n", elapsed)
    }()

    n := 28123
    abundant := []int{}
    for i := 12; i <= n; i++ {
        if divisorsSum(i) > i {
            abundant = append(abundant, i)
        }
    }

    sums := map[int]bool{}
    for i := 0; i < len(abundant); i++ {
        for j := i; j < len(abundant); j++ {
            if abundant[i]+abundant[j] > n {
                break
            }
            sums[abundant[i]+abundant[j]] = true
        }
    }

    sum := 0
    for i := 1; i <= 28123; i++ {
        if _, ok := sums[i]; !ok {
            sum += i
        }
    }
    fmt.Println(sum)
}

这段代码在我的电脑上需要 450 毫秒。但是，如果我使用 bool 切片而不是像这样的 map 将主要代码更改为下面的代码：

func main() {
    start := time.Now()
    defer func() {
        elapsed := time.Since(start)
        fmt.Printf("%s\n", elapsed)
    }()

    n := 28123
    abundant := []int{}
    for i := 12; i <= n; i++ {
        if divisorsSum(i) > i {
            abundant = append(abundant, i)
        }
    }
    sums := make([]bool, n)
    for i := 0; i < len(abundant); i++ {
        for j := i; j < len(abundant); j++ {
            if abundant[i]+abundant[j] < n {
                sums[abundant[i]+abundant[j]] = true
            } else {
                break
            }
        }
    }
    sum := 0
    for i := 0; i < len(sums); i++ {
        if !sums[i] {
            sum += i
        }
    }
    fmt.Println(sum)
}

现在只需要 40 毫秒，低于以前速度的 1/10。我认为地图应该具有更快的查找速度。这里的性能差异是怎么回事？

Answer 1

您可以分析您的代码并查看，但总的来说，有两个主要原因：

1. 您sums在第二个示例中预先分配了所需的大小。这意味着它永远不必增长，而且所有这些都非常有效，没有 GC 压力，没有重新分配等。尝试提前创建具有所需大小的映射，看看它对事情的改进有多大。

2. 我不知道 Go 的哈希映射的内部实现，但总的来说，通过整数索引随机访问数组/切片是非常有效的，并且哈希表会在其上增加开销，特别是如果它对整数进行哈希处理（它可能会这样做以创造更好的分布）。