为什么 Go 中遍历 slice 可能比遍历 map 慢？

Question

我正在 leetcode 上做著名的最长连续序列问题，并提出了两个可行的解决方案。它们仅一行不同，因此此代码适用于两者：

type void struct{}

func longestConsecutive(nums []int) int {
    max_seq := 0
    numSet := make(map[int]void, len(nums))

    for _, n := range nums {
        numSet[n] = void{}
    }

    for n := range numSet {  << the Map version
    for _, n := range nums { << the Slice version

        if _, prev_exists := numSet[n-1]; !prev_exists {
            for i := 1; ; i++ {
                if _, next_exists := numSet[n+i]; !next_exists {
                    max_seq = max(max_seq, i)
                    break
                }
            }
        }
    }
    return max_seq
}

两种解决方案都可以工作并占用大约 11-12 MB 内存，但速度截然不同：

Slice 版本

1832 毫秒
84 毫秒 地图一

我运行了几次，首先认为这是由于服务器端的延迟，但没有任何改变，每次迭代切片大约慢 20 倍。这对我来说是违反直觉的，因为切片基于数组，与哈希映射相比，它的简单内部结构应该使循环非常快。我一定是在这里弄错了并且想理解。请帮忙！

Answer 1

我修改了你的代码，使其成为一个合适的独立 Go 程序：

package main

import "fmt"

type void struct{}

func longestConsecutive(nums []int) int {
        max_seq := 0
        numSet := make(map[int]void, len(nums))

        for _, n := range nums {
                numSet[n] = void{}
        }

        for n := range numSet { // the Map version
                //for _, n := range nums { // the Slice version

                if _, prev_exists := numSet[n-1]; !prev_exists {
                        for i := 1; ; i++ {
                                if _, next_exists := numSet[n+i]; !next_exists {
                                        max_seq = max(max_seq, i)
                                        break
                                }
                        }
                }
        }
        return max_seq
}

func main() {
        nums := make([]int, 100000000)
        fmt.Println(longestConsecutive(nums))
}

使用

Elvish benchmark

 命令

使用上面的地图版本运行它，始终会产生以下结果：

978.307533ms ± 17.886602ms (min 962.874042ms, max 1.011999458s, 5 runs) 使用切片变体运行该代码会产生以下结果：

2.285335308s ± 23.038738ms (min 2.262168083s, max 2.325792667s, 5 runs) 因此地图变体大约快了 2.3 倍。不是您报告的大约 21.8 倍。显然，差异将取决于

nums

 切片的实际内容。这就是为什么包含这些细节很重要。我的示例的所有值都相同（“零”值）。据推测，您的代码实际上以值不相同的方式初始化 

nums

 切片。