performance - 为什么在 Golang 中迭代 map 比迭代 slice 慢得多？

Question

我在 Golang 中使用 map 实现了一个稀疏矩阵，我注意到在排除其他可能的原因之后，我的代码开始需要更长的时间才能完成此更改，似乎罪魁祸首是 map 本身的迭代。 Go Playground link (由于某种原因不起作用)。

package main

import (
    "fmt"
    "time"
    "math"
)

func main() {
    z := 50000000
    a := make(map[int]int, z)
    b := make([]int, z)

    for i := 0; i < z; i++ {
        a[i] = i
        b[i] = i
    }

    t0 := time.Now()
    for key, value := range a {
        if key != value { // never happens
            fmt.Println("a", key, value)
        }
    }
    d0 := time.Now().Sub(t0)

    t1 := time.Now()
    for key, value := range b {
        if key != value { // never happens
            fmt.Println("b", key, value)
        }
    }
    d1 := time.Now().Sub(t1)

    fmt.Println(
        "a:", d0,
        "b:", d1,
        "diff:", math.Max(float64(d0), float64(d1)) / math.Min(float64(d0), float64(d1)),
    )
}

迭代超过 50M 项会返回以下时间:

alix@local:~/Go/src$ go version
go version go1.3.3 linux/amd64
alix@local:~/Go/src$ go run b.go 
a: 1.195424429s b: 68.588488ms diff: 17.777154632611037

我想知道，与 slice 相比，为什么在 map 上迭代几乎要慢 20 倍？

Answer 1

这归结为内存中的表示。您对不同数据结构的表示和算法复杂性的概念有多熟悉？遍历数组或 slice 很简单。值在内存中是连续的。然而，遍历映射需要遍历键空间并查找哈希表结构。

map 的动态能力可以插入任何值的键，而不会占用分配稀疏数组的大量空间，并且尽管不如数组快，但可以在键空间上高效地进行查找，是为什么哈希表有时比数组更受欢迎，尽管数组(和 slice )在给定索引的情况下具有更快的“恒定”(O(1)) 查找时间。

这一切都取决于您是否需要这种或那种数据结构的特性，以及您是否愿意处理所涉及的副作用或陷阱。