为什么迭代地图比在Golang中迭代切片要慢得多？

Question

我在Golang中使用地图实现了一个稀疏矩阵,我注意到我的代码在这个改变之后开始花了很长时间才完成,在消除了其他可能的原因之后,似乎罪魁祸首就是地图本身的迭代.Go Playground链接(由于某种原因不起作用).

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

我想知道,与切片相比,为什么在地图上迭代的速度几乎是20倍？

Answer 1

这归结为记忆中的表现.您对不同数据结构的表示和算法复杂性的概念有多熟悉？迭代数组或切片很简单.值在内存中是连续的.但是,迭代映射需要遍历密钥空间并对哈希表结构进行查找.

映射插入任意值的键而不占用大量空间来分配稀疏数组的动态能力,以及尽管没有数组那么快就可以在密钥空间上高效完成查找的事实,这就是散列表的原因虽然数组(和切片)在(O(1))给定索引时具有更快的"常量" 查找时间,但有时优先于数组.

这一切都取决于您是否需要这个或那个数据结构的功能,以及您是否愿意处理所涉及的副作用或陷阱.

Answer 2

将我的评论作为答案似乎是合理的.您正在比较的迭代性能的基础结构是哈希表和数组(https://en.wikipedia.org/wiki/Hash_table vs https://en.wikipedia.org/wiki/Array_data_structure).范围抽象实际上是(猜测,找不到代码)迭代所有密钥,访问每个值,并将两者分配给k,v :=.如果你不熟悉在数组中访问它是恒定的时间,因为你只需将sizeof(type)*i添加到起始指针以获取项目.我不知道golang中的map的内部是什么,但我知道它是内存表示,因此访问并不是那么有效.

关于这个主题的规范声明并不多; http://golang.org/ref/spec#For_statements

如果我找到时间来查找map和slice/array的范围实现,我会提出更多技术细节.