go - 为什么 Go map vs 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 slice 而不是像这样的映射:

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。我认为 map 应该有更快的查找速度。这里的性能差异是怎么回事？

Answer 1

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

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

2. 我不知道 Go 的 HashMap 的内部实现，但一般来说，通过整数索引随机访问数组/slice 非常高效，而哈希表会在其之上增加开销，尤其是如果它对整数进行哈希处理(这样做可能会创建更好的分布)。