Go Slice vs Map

Slice 和 Map 是 Go 中的两种重要的数据类型。本文将记录我关于这两种数据结构性能的一些关键的发现。

在讨论性能方面之前，我们先来简单介绍一下 Slice 和 Map。

Slice：

Slice 是构建在数组之上的一种抽象数据结构。Slice 拥有一个指向数组开始位置的指针、数组长度以及 Slice 可以使用该数组的最大容量。Slice 可以按需增长或收缩。Slice 的增长通常包括为底层的数组重新分配内存。像 copy 和 append 这样的函数可以帮助增长数组。

Map：

Go 中的 Map 和其他语言类似（内部实现可能会有所不同）。Go 中的 Map 创建 bucket （每个 bucket 可以容纳 8 个键）。

性能统计：

我对这两种数据结构都进行了一些基准测试，结果记录如下。

TEST-1：查找 Slice 中的一个 INT 元素 vs 查找 Map 中的一个元素 -

这里，我们试着在一个长度为 n 的 Slice 中查找一个元素，并与 Map 中的键查找相比较。要查找 Slice 中的一个元素，我们将遍历该 Slice，然后进行简单的 if 来检查元素。至于 Map，我们简单查找键。在所有测试中，我都会寻找最坏的情况。

正如你所见的（不出所料），对于不同的 n，Map 查找是常数复杂度（O(1)）。然而，有趣的是，对于 n 较小的 Slice，简单的 for 循环和 if 比较花费的时间比 Map 少。较大的 n 如期望那样花费更多的时间。

结论：对于查找一个给定的键，我建议使用 Map。而对于一个较小的大小（n），使用 Slice 仍然是可以的。

TEST-2：查找 Slice 中的一个 STRING 元素 vs 查找 Map 中的一个字符串键 -

我们所进行的步骤与 TEST-1 完全相同，这里唯一的不同是，我们使用字符串（String）。

从上面的数据，我们看到，给定一个键，查找一个字符串（使用 Map），具有 O(1) 复杂度。对于字符串比较，Map 击败了 Slice。

结论：给定一个字符串类型的键进行查找，我推荐使用 Map。即使对于较小的 n ，使用 Map 也是不错的。

TEST-3： 给定索引，查找 Slice 元素。

如果我们知道索引，那么，在 Go 中查找 Slice 类似于在任何语言中查找数组，并且如它一样简单。

如上所示，Slice 的直接查找是 O(1) 固定增长率。

结论：直接查找都是常数复杂度，所以，假定你知道索引，那么使用哪个都无所谓。但是，假定索引已知，那么 Slice 或者数组查找仍然比 Map 查找快得多。

TEST-4：遍历 Slice vs 遍历 Map

这里，我试着遍历 Map 和 Slice，并且在循环内执行一个常量操作。总复杂度将保持为 O(N)。

如上所示，遍历 Slice 比遍历 Map 快了近 20 倍。原因是，跟 Map 不一样，Slice （通过数组抽象出来）是在一个连续的内存块上创建的。至于 Map，循环必须遍历键空间（在 Go 中称为 bucket），并且内存分配可能并不连续。这就是为什么每次运行的时候，遍历 Map 的结果以不同的顺序显示键值。

结论：如果要求是在整个元素列表上打印或者执行操作，而不是查找，那么 Slice 是最佳选择。出于上述原因，遍历 Map 会花费更多时间。

此外，请注意，就像对 Map 进行插入一样，Slice 上的 append 操作保证了 O(1) 复杂度，但是这是一种 摊销(amortized) 常量。append 可能偶尔需要为底层数组重新分配内存。

( * ) - 因为对于大 Map，Go 的基准函数超时，所以样本大小从 200 万缩减至 2000。

有关测试的细节：

源代码：

// m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap.go 

package slicemap

// 你可以取消打印行前的注释来看看结果（确认代码是否正常）。
// 但是对于基准测试，我们不关心打印的结果。我们关心的是它运行的时间

// import "fmt"

func RangeSliceInt(input []int, find int) (index int) {
        for index,value := range input {
                if (value == find) {
        //            fmt.Println("found at",index)
                        return index
                }
        }

        return -1
}


func RangeSliceIntPrint(input []int) {
        for _,_ = range input {
                continue
        }
}


func MapLookupInt(input map[int]int, find int) (key,value int) {
        if value,ok := input[find];ok {
        //        fmt.Println("found at", find,value)
                return find,value
        }
        return 0,0
}

func MapRangeInt(input map[int]int) {
        for _,_ = range input {
                continue
        }
}

func DirectSliceInt(input []int, index int) int {
        return input[index]
}

// 对于字符串 //

func RangeSliceString(input []string, find string) (index int) {
        for index,value := range input {
                if (value == find) {
                        // fmt.Println("found at",index)
                        return index
                }
        }
        return -1
}

func RangeSliceStringPrint(input []string) {
        for _,_ = range input {
                continue
        }
}

func MapLookupString(input map[string]string, find string) (key,value string) {
        if value,ok := input[find];ok {
//              fmt.Println("found at", find,value)
                return find,value
        }
        return "0", "0"
}


func MapRangeString(input map[string]string) {
        for _,_ = range input {
                continue
        }
}


func DirectSliceString(input []string, index int) string {
        return input[index]
}

// m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap_test.go

package slicemap

import (
        "testing"
        "strconv"
)

func Benchmark_TimeRangeSliceInt(b *testing.B) {
        b.StopTimer()
        input := make([]int, 100000, 500000)
        for i := 0; i < 100000; i++ {
                input[i] = i+10
        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for i := 0; i < b.N; i++ {
                RangeSliceInt(input, 100009)  // 对于最坏情况，检查最后一个元素
        }
}

func Benchmark_TimeDirectSliceInt(b *testing.B) {
        b.StopTimer()

        input := make([]int, 100000, 500000)
        for i := 0; i < 100000; i++ {
                input[i] = i+10
        }

        b.StartTimer()        

        b.N = 2000000  // 只是为了避免数百万次 fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for i := 0; i < b.N; i++ {
                DirectSliceInt(input, 99999)  // 直接检查索引值。o(1)。发送索引
        }
}

func Benchmark_TimeMapLookupInt(b *testing.B) {

        b.StopTimer()

        input := make(map[int]int)

        // 扔一些值到 Map 中
        for i := 1; i <=100000; i++ {
                input[i] = i+10
        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for k := 0; k < b.N; k++ { 
                MapLookupInt(input, 100000)
        }

        /*
        运行命令：
        go test -bench=Benchmark_TimeMapLookup
        */
}

func Benchmark_TimeSliceRangeInt(b *testing.B) {
        b.StopTimer()

        input := make([]int, 5, 10)
        for i := 0; i < 5; i++ {
                input[i] = i+10
        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for k := 0; k < b.N; k++ {
                RangeSliceIntPrint(input)
        }
}

func Benchmark_TimeMapRangeInt(b *testing.B) {
        b.StopTimer()

        input := make(map[int]int)
        // 扔一些值到 Map 中
        for i := 1; i <=100000; i++ {
                input[i] = i+10
        }

        b.StartTimer()

        b.N = 2000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for k := 0; k < b.N; k++ {
                MapRangeInt(input)
        }
}

// 测试字符串

func Benchmark_TimeRangeSliceString(b *testing.B) {
        b.StopTimer()

        input := make([]string, 100000, 500000)
        for i := 0; i < 100000; i++ {
                input[i] = strconv.FormatInt(int64(i+10),10)

        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for i := 0; i < b.N; i++ {
                RangeSliceString(input, "100009")  // 对于最坏情况，检查最后一个元素
        }
}

func Benchmark_TimeDirectSliceString(b *testing.B) {
        b.StopTimer()

        input := make([]string, 100000, 500000)
        for i := 0; i < 100000; i++ {
                input[i] = strconv.FormatInt(int64(i+10),10)
        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）
        for i := 0; i < b.N; i++ {
                DirectSliceString(input, 99999)  // 直接检查索引值。o(1)
        }
}

func Benchmark_TimeMapLookupString(b *testing.B) {
        b.StopTimer()

        input := make(map[string]string)

        // 扔一些值到 Map 中
        for i := 1; i <=100000; i++ {
                input[strconv.FormatInt(int64(i),10)] = strconv.FormatInt(int64(i+10),10)
        }

        b.StartTimer()

        b.N = 2000000  // 只是为了避免数百万次fmt.Println（以防你在 slicemap.go 包中进行 fmt.Println）

        for k := 0; k < b.N; k++ {
                MapLookupString(input, "100000")
        }

        /*

        运行：

        go test -bench=Benchmark_TimeMapLookupString

        */
}