Advent of Code 2020第1天：为何O(n²)实现比O(n)方案运行更快？

现象 #

针对Advent of Code 2020第1天的题目实现了两种解法：

• p1解法理论时间复杂度为O(n)
• p2解法理论时间复杂度为O(n²)
  实测基准测试结果显示，复杂度更高的p2运行速度反而更快，基准测试数据如下：

BenchmarkP1   ​    12684         92239 ns/op
BenchmarkP2         3161         90705 ns/op

原因分析 #

这个结果和理论复杂度的差异是常数开销导致的，具体原因如下：

• p1使用了哈希表（map）存储数据，哈希计算、碰撞处理、动态扩容都有额外的高常数开销
• p2使用切片存储数据，遍历切片时数据存储在连续内存空间，CPU缓存命中率极高，遍历操作的常数开销极低
• 该题的输入规模仅为200个左右的数字，n²的总运算量只有4万次左右，这个量级的运算对现代CPU来说可以在极短时间内完成，远低于哈希表操作的总开销
• 两个解法都包含文件读取、字符串转整数的公共逻辑，这部分开销占总耗时的比例较高，进一步抹平了算法逻辑部分的理论复杂度差异

实现代码 #

O(n)解法p1 #

// O(n) 解法
func p1(value int) (int, int){
    m := make(map[int]int)

    f, err := os.Open("nums.txt")
    printError(err)
    defer f.Close()
    scanner := bufio.NewScanner(f)

    for scanner.Scan() {
        intVar, err := strconv.Atoi(scanner.Text())
        printError(err)
        m[intVar]=intVar
    }

    for _, key := range m {
        l, ok := m[value-key]
        if ok {
            return l, key
        }
    }
    return 0, 0
}

O(n²)解法p2 #

// O(n²) 解法
func p2(value int) (int, int){
    var data []int

    f, err := os.Open("nums.txt")
    printError(err)
    defer f.Close()
    scanner := bufio.NewScanner(f)

    for scanner.Scan() {
        intVar, err := strconv.Atoi(scanner.Text())
        printError(err)
        data= append(data, intVar)
    }

    for ki, i := range data {
        for kj, j := range data {
            if ki != kj && i+j == value {
                return i , j
            }
        }
    }
    return 0, 0
}

内容的提问来源于stack exchange，提问作者NBW