为什么遍历地图比遍历 Golang 中的切片慢得多？

Question

我在 Golang 中使用地图实现了一个稀疏矩阵，我注意到我的代码开始需要更长的时间才能完成此更改，在排除其他可能的原因后，罪魁祸首似乎是地图本身的迭代。 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)),
    )
}

在以下时间迭代超过 5000 万个项目returns：

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

我想知道，为什么遍历地图的速度比切片慢将近 20 倍？

Answer 1

这归结为内存中的表示。您对不同数据结构的表示和算法复杂性的概念有多熟悉？遍历数组或切片很简单。值在内存中是连续的。但是遍历映射需要遍历键 space 并查找 hash-table 结构。

映射的动态能力可以插入任何值的键，而无需使用大量 space 分配稀疏数组，并且可以在键上高效地进行查找 space尽管不如数组快，这就是为什么哈希 table 有时比数组更受欢迎的原因，尽管数组（和切片）在给定索引的情况下具有更快的 "constant" (O(1)) 查找时间。

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

Answer 2

将我的评论作为答案似乎是合理的。您正在比较迭代性能的底层结构是散列 table 和数组 (https://en.wikipedia.org/wiki/Hash_table vs https://en.wikipedia.org/wiki/Array_data_structure)。 range抽象其实就是（推测，找不到代码）遍历所有key，访问每一个value，将两者赋值给k,v :=。如果您不熟悉在数组中访问它是恒定时间，因为您只需将 sizeof(type)*i 添加到起始指针即可获取项目。我不知道 golang 中 map 的内部结构是什么，但我知道它是内存表示，因此访问没有那么高效。

关于该主题的规范说明不多； http://golang.org/ref/spec#For_statements

如果我有时间查看地图范围的实现，slice/array我会提供更多技术细节。

为什么遍历地图比遍历 Golang 中的切片慢得多？

Why is iterating over a map so much slower than iterating over a slice in Golang?

performance

dictionary

go

sparse-matrix

slice