为什么在Golang中遍历map比遍历slice慢这么多？

Question

我正在使用 Golang 中的 map 实现稀疏矩阵，发现在这个改变后我的代码开始花费更长的时间来完成，在排除其他可能的原因后，似乎罪魁祸首是对 map 进行遍历。 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)),
    )
}

遍历5000万个项目的时间如下：

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倍？

- Alix Axel

---

为什么遍历 map 会明显变慢？切片只是连续的内存区域，而哈希表是一个更复杂的数据结构。 - JimB

显而易见的答案是底层结构是数组和哈希表。在一种情况下，您正在迭代键，并且（在范围抽象中）访问每个值。在另一种情况下，您正在遍历连续的内存块。 - evanmcdonnal

相关讨论：https://code.google.com/p/go/issues/detail?id=3885 - Alix Axel

Answer 1

这归结于内存中的表示方式。您对不同数据结构的表示和算法复杂度的概念有多熟悉？迭代数组或切片很简单。值在内存中是连续的。然而，迭代地图需要遍历键空间并进行散列表结构的查找。

散列表具有动态能力，可以插入任何值的键，而无需使用大量空间分配稀疏数组，并且虽然相对于数组来说，查找速度不够快，但在键空间上进行高效查找的事实是为什么有时会优先选择散列表而不是数组，尽管数组（和切片）在给定索引的情况下具有更快的“常数”(O(1))查找时间。

所有这一切都取决于您是否需要这种或那种数据结构的功能以及您是否愿意处理相关的副作用或陷阱。

- Nick

---

哈希表被认为是O(1)，但比数组具有更高的常数。索引数组的时间复杂度应该被正确定义为Θ(1)（大theta）。 - JimB

谢谢，我已经编辑过了。这已经有一段时间了，我有点模糊，但是完全正确。 - Nick

Answer 2

似乎把我的评论作为答案是有道理的。你比较迭代性能的底层结构是哈希表和数组 (https://en.wikipedia.org/wiki/Hash_table vs https://en.wikipedia.org/wiki/Array_data_structure)。范围抽象实际上（猜测，找不到代码）遍历所有键，访问每个值，并将两者分配给k,v :=。如果您不熟悉在数组中访问，它是常数时间，因为您只需将sizeof(type)*i添加到起始指针以获取该项。我不知道map在golang中的内部情况，但我知道足够的知识来知道它的内存表示和因此访问方式并不高效。

有关此主题的规格说明并不多见; http://golang.org/ref/spec#For_statements

如果我有时间查找地图和切片/数组的范围实现，我会提供更多技术细节。

- evanmcdonnal

---

这是一个很好的答案，更多地涉及了具体的golang细节。 - Nick