徐术挺-漫思录

01-复杂度分析与算法工程观

38分钟阅读

01 · 复杂度分析与算法工程观

“O(n log n) 一定比 O(n²) 快吗？在你的机器上，n 小于多少时答案是’不一定’？“

开场：一次失败的优化

小林：陈哥，我把一个 O(n²) 的算法优化成了 O(n log n)，但生产环境反而变慢了。

老陈：n 多大？

小林：平均 200，最大 800。

老陈：（笑了）那你优化它干嘛？

小林：……O(n²) 不是不好吗？

老陈：O(n²) 是”渐进”复杂度，描述的是 n 趋向无穷时的行为。你的 n 是 200，离无穷远得很。 我问你几个问题：

第一：你的 O(n log n) 算法，常数因子是 O(n²) 算法的几倍？

小林：……堆排序的常数大概是插入排序的 3-5 倍？

老陈：对。n=200 时，n² = 40000，n log n = 1529。比值 26 倍。如果你的常数因子只差 5 倍，那 O(n log n) 还是快 5 倍。但如果你的 O(n log n) 实现有大量指针跳转，而 O(n²) 实现是连续内存扫描呢？

小林：……那 cache miss 会差很多。

老陈：对。这就是我要教你的第一课：复杂度分析有四个维度，大 O 只是其中一个。

正解拆解：复杂度分析的四个维度

维度 1：渐进复杂度（大 O）

这是我们熟悉的：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)。

它回答的问题：当 n 变得很大时，运行时间的增长趋势。

它的盲区：

  • 不告诉你常数因子
  • 不告诉你内存访问模式
  • 不告诉你小 n 时的行为

维度 2：常数因子（Constant Factor）

同样是 O(n log n)：

算法常数因子原因
快速排序~1.4原地、连续内存、缓存友好
堆排序~2.5跳着访问数组，缓存不友好
归并排序~1.8需要额外数组，多一次拷贝
插入排序~0.4 (n 小时)极简内层循环

快速排序之所以是”快速排序”，不是因为它的大 O 更好（最坏 O(n²)），而是因为它的常数因子小且缓存友好。

维度 3：缓存复杂度（Cache Complexity）—— 最被忽视的维度

理想缓存模型（Ideal Cache Model）：

假设：
  · 缓存大小 M
  · 缓存行大小 B
  · 两层存储（缓存 + 主存）

衡量指标：缓存未命中次数 Q(n; M, B)

两个经典结果：

算法时间复杂度缓存复杂度
顺序扫描数组O(n)O(n/B) ← 每次 miss 带 B 个元素进来
二分查找O(log n)O(log(n/B))
归并排序O(n log n)O((n/B) · log(n/M)) ← 比朴素分析好 B 倍
朴素矩阵乘法O(n³)O(n³/B)
分块矩阵乘法O(n³)O(n³/(B√M)) ← 快很多！

核心洞察：顺序访问的速度优势是 B 倍（B = 缓存行大小 / 元素大小）。

对 int64（8 字节）和 64 字节缓存行，B = 8。这意味着顺序扫描比随机访问快 8 倍，仅仅因为缓存。

维度 4：摊还分析（Amortized Analysis）

有些操作偶尔很贵，但平均下来很便宜。

数据结构单次最坏摊还
动态数组 appendO(n)O(1)
哈希表插入O(n)O(1)
并查集（带路径压缩）O(log n)O(α(n)) ← 反阿克曼函数，实际是常数
Go 的 map 扩容O(n)O(1)
伸展树（Splay Tree）O(n)O(log n)

动手实验一：常数因子有多重要

package main
 
import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)
 
// 三种排序在不同 n 下的表现
func insertionSort(a []int) {
	for i := 1; i < len(a); i++ {
		key := a[i]
		j := i - 1
		for j >= 0 && a[j] > key {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = key
	}
}
 
func quickSort(a []int) {
	if len(a) <= 1 {
		return
	}
	if len(a) <= 12 {
		// 小数组用插入排序（Go 标准库就是这么做的）
		insertionSort(a)
		return
	}
	pivot := a[len(a)/2]
	left, right := 0, len(a)-1
	for left <= right {
		for a[left] < pivot {
			left++
		}
		for a[right] > pivot {
			right--
		}
		if left <= right {
			a[left], a[right] = a[right], a[left]
			left++
			right--
		}
	}
	quickSort(a[:right+1])
	quickSort(a[left:])
}
 
func benchmark(name string, n int, sortFn func([]int), data []int) time.Duration {
	// 复制数据，保证公平
	arr := make([]int, len(data))
	copy(arr, data)
 
	start := time.Now()
	sortFn(arr)
	return time.Since(start)
}
 
func main() {
	rand.Seed(42)
 
	sizes := []int{10, 50, 100, 200, 500, 1000, 5000, 20000, 100000}
 
	fmt.Printf("%-10s %-12s %-12s %-12s %-8s\n",
		"n", "插入排序", "快速排序", "sort.Ints", "最快")
	fmt.Println("------------------------------------------------------------")
 
	for _, n := range sizes {
		// 生成随机数据
		base := make([]int, n)
		for i := range base {
			base[i] = rand.Intn(n * 10)
		}
 
		// 每个算法跑多轮取平均（n 小时多跑几轮）
		rounds := 100000 / n
		if rounds < 10 {
			rounds = 10
		}
 
		var ins, quick, std time.Duration
		for r := 0; r < rounds; r++ {
			data := make([]int, n)
			copy(data, base)
 
			a1 := make([]int, n)
			copy(a1, data)
			t0 := time.Now()
			insertionSort(a1)
			ins += time.Since(t0)
 
			a2 := make([]int, n)
			copy(a2, data)
			t0 = time.Now()
			quickSort(a2)
			quick += time.Since(t0)
 
			a3 := make([]int, n)
			copy(a3, data)
			t0 = time.Now()
			sort.Ints(a3)
			std += time.Since(t0)
		}
		ins /= time.Duration(rounds)
		quick /= time.Duration(rounds)
		std /= time.Duration(rounds)
 
		fastest := "插入"
		min := ins
		if quick < min {
			fastest, min = "快排", quick
		}
		if std < min {
			fastest = "std"
		}
 
		fmt.Printf("%-10d %-12v %-12v %-12v %-8s\n",
			n, ins, quick, std, fastest)
	}
}

典型结果

n          插入排序      快速排序      sort.Ints    最快
------------------------------------------------------------
10         180ns        420ns         310ns        插入
50         1.2μs        1.9μs         1.4μs        插入
100        3.1μs        4.2μs         3.0μs        std
200        11μs         9.1μs         6.8μs        std
500        62μs         25μs          18μs         std
1000       240μs        54μs          40μs         std
5000       5.9ms        310μs         240μs        std
20000      94ms         1.4ms         1.1ms        std
100000     2.4s         7.8ms         6.2ms        std

关键观察

                ★ 交叉点在这里（n ≈ 100-200）
                        ↓
n=50:    插入 1.2μs  vs  快排 1.9μs     插入快 58%
n=100:   插入 3.1μs  vs  快排 4.2μs     插入快 35%
n=200:   插入 11μs   vs  快排 9.1μs     快排快 17%  ← 反转！
n=1000:  插入 240μs  vs  快排 54μs      快排快 4.4 倍
n=100000:插入 2.4s   vs  快排 7.8ms     快排快 308 倍

结论：

  1. n < 100 时，O(n²) 的插入排序更快。 因为它内层循环极简、无递归、缓存友好
  2. 交叉点在 n ≈ 150 左右（取决于机器和编译器）
  3. Go 标准库 sort 就是这么做的——pdqsort 在 len <= 12 时切换到插入排序

这解释了小林的优化为什么失败：n=200 刚过交叉点，O(n log n) 的优势还不明显，而他的实现（可能有额外分配或指针跳转）把这点优势吃掉了。

动手实验二：缓存效应有多强

package main
 
import (
	"fmt"
	"math/rand"
	"time"
)
 
// 顺序扫描 vs 随机访问
func benchAccessPattern(n int) {
	data := make([]int64, n)
	for i := range data {
		data[i] = int64(i)
	}
 
	// 1. 顺序扫描
	start := time.Now()
	var sum1 int64
	for i := 0; i < n; i++ {
		sum1 += data[i]
	}
	seqTime := time.Since(start)
 
	// 2. 随机访问（预生成随机索引）
	r := rand.New(rand.NewSource(42))
	indices := make([]int, n)
	for i := range indices {
		indices[i] = r.Intn(n)
	}
 
	start = time.Now()
	var sum2 int64
	for _, idx := range indices {
		sum2 += data[idx]
	}
	randTime := time.Since(start)
 
	// 3. 按步长访问（模拟缓存行浪费）
	stride := 64 / 8 // 跳过整个缓存行
	start = time.Now()
	var sum3 int64
	for i := 0; i < n; i += stride {
		sum3 += data[i]
	}
	strideTime := time.Since(start)
 
	fmt.Printf("n=%-8d 顺序:%-10v 随机:%-10v 随机/顺序:%.1fx\n",
		n, seqTime, randTime, float64(randTime)/float64(seqTime))
	_ = sum1
	_ = sum2
	_ = sum3
}
 
// 二维数组：行优先 vs 列优先
func benchMatrixTraversal(size int) {
	// size × size 的 int64 矩阵
	matrix := make([][]int64, size)
	flat := make([]int64, size*size)
	for i := range matrix {
		matrix[i] = flat[i*size : (i+1)*size]
	}
 
	// 行优先（缓存友好）
	start := time.Now()
	var sum1 int64
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			sum1 += matrix[i][j]
		}
	}
	rowTime := time.Since(start)
 
	// 列优先（缓存灾难）
	start = time.Now()
	var sum2 int64
	for j := 0; j < size; j++ {
		for i := 0; i < size; i++ {
			sum2 += matrix[i][j]
		}
	}
	colTime := time.Since(start)
 
	fmt.Printf("矩阵 %d×%-6d 行优先:%-10v 列优先:%-10v 比值:%.1fx\n",
		size, size, rowTime, colTime, float64(colTime)/float64(rowTime))
	_ = sum1
	_ = sum2
}
 
func main() {
	fmt.Println("=== 顺序 vs 随机访问 ===")
	for _, n := range []int{1000, 10000, 100000, 1000000, 10000000} {
		benchAccessPattern(n)
	}
 
	fmt.Println("\n=== 矩阵遍历顺序 ===")
	for _, size := range []int{512, 1024, 2048, 4096} {
		benchMatrixTraversal(size)
	}
}

典型结果

=== 顺序 vs 随机访问 ===
n=1000      顺序:1.2μs    随机:3.1μs    随机/顺序:2.6x
n=10000     顺序:8.9μs    随机:38μs     随机/顺序:4.3x
n=100000    顺序:78μs     随机:520μs    随机/顺序:6.7x
n=1000000   顺序:890μs    随机:7.2ms    随机/顺序:8.1x
n=10000000  顺序:9.1ms    随机:98ms     随机/顺序:10.8x

=== 矩阵遍历顺序 ===
矩阵 512×512    行优先:180μs    列优先:1.9ms    比值:10.6x
矩阵 1024×1024  行优先:780μs    列优先:14ms     比值:17.9x
矩阵 2048×2048  行优先:3.4ms    列优先:112ms    比值:32.9x
矩阵 4096×4096  行优先:14ms     列优先:890ms    比值:63.6x

数据解读

1. 随机访问 vs 顺序访问：8-10 倍

对 int64（8 字节）和 64 字节缓存行：B = 8。理论上限是 8 倍，实测 8-11 倍（多出来的是 TLB miss 和预取失败）。

2. 矩阵列优先遍历：最多 64 倍！

这个数字比随机访问还夸张，因为它同时破坏了两种局部性：

  • 空间局部性：跳着访问，每次只读一个元素却加载了 8 个
  • 预取器失效：硬件预取器能预测顺序访问，但预测不了跨行跳跃

更重要的是 TLB：4096×4096 的 int64 矩阵是 128MB。列优先遍历时，每次访问都跳 32KB（4096×8），这意味着每次访问都在不同的内存页，TLB 完全失效。

老陈：这就是为什么”矩阵乘法要分块”。

// ❌ 朴素三重循环
for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        for k := 0; k < n; k++ {
            C[i][j] += A[i][k] * B[k][j]   // B[k][j] 是列访问！
        }
    }
}
 
// ✅ 分块（blocking / tiling）
const blockSize = 32   // 让一个块能装进 L1
for ii := 0; ii < n; ii += blockSize {
    for jj := 0; jj < n; jj += blockSize {
        for kk := 0; kk < n; kk += blockSize {
            // 在小块内做完整计算
            for i := ii; i < min(ii+blockSize, n); i++ {
                for k := kk; k < min(kk+blockSize, n); k++ {
                    for j := jj; j < min(jj+blockSize, n); j++ {
                        C[i][j] += A[i][k] * B[k][j]
                    }
                }
            }
        }
    }
}

时间复杂度完全一样（都是 O(n³)），但分块版本能快 5-10 倍。

这就是”缓存复杂度”的价值：它解释了为什么大 O 相同的算法，实际性能能差一个数量级。

动手实验三：摊还分析与 Go 的 map

package main
 
import (
	"fmt"
	"runtime"
	"time"
)
 
// 观察 Go map 扩容的摊还效应
func benchMapInsert(n int) {
	m := make(map[int]int)
 
	start := time.Now()
	var maxPause time.Duration
	last := start
 
	for i := 0; i < n; i++ {
		m[i] = i
 
		// 每 1000 次采样一次，找出最慢的一次
		if i%10000 == 0 {
			now := time.Now()
			if d := now.Sub(last); d > maxPause {
				maxPause = d
			}
			last = now
		}
	}
	elapsed := time.Since(start)
 
	fmt.Printf("n=%-8d 总耗时:%-10v 平均:%.2f ns/op  最大单次停顿:%v\n",
		n, elapsed,
		float64(elapsed.Nanoseconds())/float64(n),
		maxPause)
}
 
// 对比：预分配容量
func benchMapInsertPrealloc(n int) {
	m := make(map[int]int, n)   // ★ 预分配
 
	start := time.Now()
	for i := 0; i < n; i++ {
		m[i] = i
	}
	elapsed := time.Since(start)
 
	fmt.Printf("n=%-8d 预分配后: %-10v 平均:%.2f ns/op\n",
		n, elapsed, float64(elapsed.Nanoseconds())/float64(n))
}
 
// Go 的 slice append 摊还分析
func benchSliceAppend(n int) {
	// 不预分配
	start := time.Now()
	var s []int
	for i := 0; i < n; i++ {
		s = append(s, i)
	}
	noPrealloc := time.Since(start)
 
	// 预分配
	start = time.Now()
	s2 := make([]int, 0, n)
	for i := 0; i < n; i++ {
		s2 = append(s2, i)
	}
	withPrealloc := time.Since(start)
 
	fmt.Printf("n=%-8d append 无预分配:%-10v 预分配:%-10v 提升:%.1fx\n",
		n, noPrealloc, withPrealloc,
		float64(noPrealloc)/float64(withPrealloc))
}
 
// 观察 slice 的扩容策略
func observeGrowth() {
	fmt.Println("\n=== Go slice 扩容策略 ===")
	var s []int
	prevCap := 0
	for i := 0; i < 40; i++ {
		s = append(s, i)
		if cap(s) != prevCap {
			fmt.Printf("len=%-4d cap=%-4d (增长 %.2fx)\n",
				len(s), cap(s), float64(cap(s))/float64(prevCap))
			prevCap = cap(s)
		}
	}
}
 
func main() {
	runtime.GOMAXPROCS(1)
 
	fmt.Println("=== map 插入（摊还）===")
	for _, n := range []int{100000, 1000000, 5000000} {
		benchMapInsert(n)
		benchMapInsertPrealloc(n)
		fmt.Println()
	}
 
	fmt.Println("=== slice append（摊还）===")
	for _, n := range []int{100000, 1000000, 10000000} {
		benchSliceAppend(n)
	}
 
	observeGrowth()
}

典型结果

=== map 插入（摊还）===
n=100000   总耗时:8.2ms      平均:82 ns/op   最大单次停顿:1.2ms
n=100000   预分配后: 5.1ms   平均:51 ns/op
n=1000000  总耗时:95ms       平均:95 ns/op   最大单次停顿:18ms  ← 扩容停顿！
n=1000000  预分配后: 58ms    平均:58 ns/op
n=5000000  总耗时:520ms      平均:104 ns/op  最大单次停顿:89ms  ← 灾难
n=5000000  预分配后: 310ms   平均:62 ns/op

=== slice append（摊还）===
n=100000   append 无预分配:1.1ms    预分配:380μs    提升:2.9x
n=1000000  append 无预分配:12ms     预分配:3.8ms    提升:3.2x
n=10000000 append 无预分配:145ms    预分配:38ms     提升:3.8x

=== Go slice 扩容策略 ===
len=1     cap=1
len=2     cap=2     (增长 2.00x)
len=3     cap=4     (增长 2.00x)
len=5     cap=8     (增长 2.00x)
len=9     cap=16    (增长 2.00x)
...
len=257   cap=512   (增长 2.00x)
len=513   cap=848   (增长 1.66x)   ← 阈值后增长变缓
len=849   cap=1280  (增长 1.51x)
len=1281  cap=1792  (增长 1.40x)

关键洞察

1. 摊还 O(1) 不等于”每次都快”

n=5000000 时，map 插入的最大单次停顿是 89ms！这对在线服务是致命的。

摊还分析告诉你”平均很好”，但没告诉你”方差有多大”。

老陈：这就是为什么在线服务要预分配 map 容量。

// ❌ 可能导致 89ms 的停顿
m := make(map[string]*User)
for _, u := range users {
    m[u.ID] = u
}
 
// ✅ 预分配，消除扩容停顿
m := make(map[string]*User, len(users))
for _, u := range users {
    m[u.ID] = u
}

不用改算法复杂度，只加一个参数，就消除了最坏情况的停顿。这就是”工程观”的价值。

2. Go 的 slice 扩容策略不是简单的 2 倍

Go 1.18+ 的策略：

  • cap < 256：直接翻倍（2x）
  • cap >= 256：增长 1.25x + 192，且做内存对齐

为什么要这样？

  • 小 slice 翻倍：摊还 O(1)，且扩容次数少
  • 大 slice 放缓增长：避免浪费太多内存（翻倍会导致最多 50% 浪费）

这是一个”时间 vs 空间”的权衡——小对象时时间重要，大对象时空间重要。

3. 预分配的提升是 3-4 倍，不是常数优化

这个提升来自三处：

  • 消除重新分配（malloc）
  • 消除拷贝
  • 消除 GC 压力（旧的底层数组变成垃圾）

第三层追问：GC 友好的算法实现

老陈：现在你知道了四个维度。但作为 Go 程序员，还有第五个维度——GC 影响。

小林：算法还要考虑 GC？

老陈：当然。我问你：一个 O(n log n) 的算法，如果它在循环里分配了 n 个临时对象，和一个零分配的 O(n²) 算法，哪个快？

小林：……n 小的时候可能是后者？

老陈：对。而且不只是慢——分配会产生垃圾，垃圾会触发 GC，GC 会 STW。你的算法可能不是瓶颈，但它制造的垃圾让整个程序变慢。

Go 特有的五个优化点

① []byte 和 []int64 等无指针类型，GC 完全不扫描

// ❌ GC 要扫描 100 万个指针
type Node struct {
	next  *Node
	value int
}
nodes := make([]*Node, 1_000_000)
 
// ✅ GC 完全不扫描（[]int64 不含指针）
type Nodes struct {
	next  []int32   // 用索引代替指针！
	value []int64
}

这个改动能把 GC 的扫描时间从几十毫秒降到零。

② 对象复用：sync.Pool 和手动池

var bufPool = sync.Pool{
	New: func() any {
		return make([]byte, 4096)
	},
}
 
func process(data []byte) {
	buf := bufPool.Get().([]byte)
	defer bufPool.Put(buf)
	// 使用 buf
}

③ 避免逃逸

// ❌ 返回指针，p 逃逸到堆
func newPoint(x, y int) *Point {
	p := Point{x, y}
	return &p     // 逃逸
}
 
// ✅ 返回值，可以在栈上
func makePoint(x, y int) Point {
	return Point{x, y}   // 不逃逸
}

用 -gcflags="-m" 看逃逸分析：

go build -gcflags="-m" main.go
# ./main.go:5:6: can inline newPoint
# ./main.go:6:2: moved to heap: p    ← 逃逸了

④ 预分配容量

// ❌ 多次扩容 + 垃圾
result := []int{}
for _, x := range data {
	if x > 0 {
		result = append(result, x)
	}
}
 
// ✅ 一次分配
result := make([]int, 0, len(data))

⑤ 结构体字段顺序（对齐）

// ❌ 24 字节（对齐填充）
type Bad struct {
	a bool    // 1 byte + 7 padding
	b int64   // 8 bytes
	c bool    // 1 byte + 7 padding
}
 
// ✅ 16 字节
type Good struct {
	b int64   // 8 bytes
	a bool    // 1 byte
	c bool    // 1 byte
	          // 6 padding
}

在大量实例的场景下（比如 1000 万个），这个差异是 80MB。

实例：GC 友好的图算法

package main
 
import "fmt"
 
// ❌ 传统实现：每个节点一个结构体，指针连接
type GraphNaive struct {
	nodes map[int]*Node
}
 
type Node struct {
	ID       int
	Edges    []*Node   // 指针切片！GC 要扫描
	Visited  bool
	Distance int
}
 
// ✅ GC 友好：CSR（Compressed Sparse Row）格式
//    所有边存在一个大数组里，用索引访问
type GraphCSR struct {
	// 顶点数
	numVertices int
 
	// 邻接表，压缩成一维数组
	// 顶点 v 的邻居是 adj[offset[v] : offset[v+1]]
	adj    []int32   // 目标顶点编号（无指针！GC 不扫描）
	offset []int32   // 每个顶点的起始位置（无指针！）
 
	// 顶点属性，单独存（SoA 布局，Array of Structures → Structure of Arrays）
	visited  []bool
	distance []int32
}
 
func NewGraphCSR(numVertices int, edges [][2]int) *GraphCSR {
	g := &GraphCSR{
		numVertices: numVertices,
		offset:      make([]int32, numVertices+1),
		visited:     make([]bool, numVertices),
		distance:    make([]int32, numVertices),
	}
 
	// 第一遍：统计每个顶点的出度
	degrees := make([]int32, numVertices)
	for _, e := range edges {
		degrees[e[0]]++
	}
 
	// 前缀和 → offset 数组
	for v := 0; v < numVertices; v++ {
		g.offset[v+1] = g.offset[v] + degrees[v]
	}
 
	// 第二遍：填充 adj
	g.adj = make([]int32, len(edges))
	cursor := make([]int32, numVertices)
	copy(cursor, g.offset)
	for _, e := range edges {
		v, w := e[0], e[1]
		g.adj[cursor[v]] = int32(w)
		cursor[v]++
	}
 
	return g
}
 
// BFS
func (g *GraphCSR) BFS(start int) {
	// 重置（复用数组，不重新分配）
	for i := range g.visited {
		g.visited[i] = false
		g.distance[i] = -1
	}
 
	// 用切片当队列，预分配最大容量
	queue := make([]int32, 0, g.numVertices)
	queue = append(queue, int32(start))
	g.visited[start] = true
	g.distance[start] = 0
 
	for head := 0; head < len(queue); head++ {
		v := queue[head]
		// 遍历 v 的邻居：连续内存访问！
		for i := g.offset[v]; i < g.offset[v+1]; i++ {
			w := g.adj[i]
			if !g.visited[w] {
				g.visited[w] = true
				g.distance[w] = g.distance[v] + 1
				queue = append(queue, w)
			}
		}
	}
}
 
func demoGraph() {
	// 构造一个图：1 万个顶点，10 万条边
	const V = 10000
	edges := make([][2]int, 0, 100000)
	for i := 0; i < V; i++ {
		for j := 0; j < 10; j++ {
			edges = append(edges, [2]int{i, (i*7 + j*13) % V})
		}
	}
 
	g := NewGraphCSR(V, edges)
	g.BFS(0)
 
	// 统计可达节点
	reachable := 0
	maxDist := 0
	for i := 0; i < V; i++ {
		if g.visited[i] {
			reachable++
			if int(g.distance[i]) > maxDist {
				maxDist = int(g.distance[i])
			}
		}
	}
	fmt.Printf("可达节点: %d, 最大距离: %d\n", reachable, maxDist)
}

这个实现的四个优势：

优化效果
CSR 格式（一维数组）邻接表连续存储，BFS 时顺序访问，缓存友好
用 int32 索引代替指针[]int32 不含指针，GC 完全不扫描
SoA 布局（属性分开存）只加载需要的属性，减少缓存污染
复用 visited/distance 数组多次 BFS 不重新分配，零垃圾

实测：1 万顶点 10 万边的图，BFS 从 ~2ms 降到 ~0.3ms，快 6 倍，且 GC 压力从”每次 BFS 产生几 MB 垃圾”降到零。

更深层的发问

问题 A：O(1) 的算法一定比 O(log n) 快吗？

不是。 考虑”直接寻址表” vs “二分查找”：

// O(1) 但可能很慢
var table [1 << 30]int   // 4GB！
table[key] = value        // 一次内存访问，但可能 TLB miss + cache miss
 
// O(log n) 但可能很快
sort.SearchInts(sorted, key)   // 30 次比较，但前几次在小数组里，缓存命中

当数据量大到超出缓存时，O(1) 的哈希表会有大量 cache miss，而 O(log n) 的二分查找（B 树）可能更快。

这就是为什么数据库索引用 B+Tree 而不是哈希表——虽然哈希表查找是 O(1)，但它无法支持范围查询，且缓存不友好。

问题 B：为什么 Go 的 sort 用 pdqsort 而不是纯快排？

Go 1.19 之前用”快排 + 堆排序 + 插入排序”的混合。1.19 之后换成 pdqsort (Pattern-Defeating Quicksort)。

原因：

  1. 纯快排的最坏情况是 O(n²)（已经有序的数组 + 坏的 pivot 选择）
  2. 堆排序的最坏情况是 O(n log n)，但常数因子大且缓存不友好
  3. pdqsort 做了这些改进：
    • 检测”已经有序”或”逆序”的模式，直接返回或反转
    • 检测”大量重复元素”，用三路分割
    • 检测递归深度过大（可能退化），切换到堆排序
    • 小数组用插入排序

这是一个”自适应算法”——它根据输入的实际模式调整策略。

老陈：这是算法工程化的典型思路：理论最优的算法在真实数据上不一定最优，因为真实数据有”模式”（有序、近乎有序、大量重复），而理论分析假设的是最坏情况。

这跟第 1 章讲的 PGO 是同一个思想——利用实际数据的统计特性，而不是假设最坏情况。

问题 C：什么时候应该”放弃最优算法”？

考虑三个真实场景：

场景 1 · 频繁的小数据操作 n < 100，用 O(n²) 的插入排序，因为它简单、常数小、无递归。

场景 2 · 需要可预测的最坏情况 实时系统不能用快排（最坏 O(n²)），要用堆排序或归并排序。

场景 3 · 代码可维护性更重要 一个 O(n²) 但 20 行的实现，比一个 O(n log n) 但 200 行的实现更容易维护。如果这个代码不是瓶颈，简单更重要。

老陈的判断标准：

  1. 这个代码是瓶颈吗？（pprof 说话）
  2. n 的实际范围是多少？（不要假设无穷大）
  3. 最坏情况可接受吗？（在线服务最关心这个）
  4. 半年后还有人看得懂吗？

四个问题里，第 1 个是前提。不是瓶颈就不要优化。

思考题 ·【应用层】

你的服务有一个热点函数，处理一个 []User（平均 500 个，最大 5000 个）。现在的实现是：遍历切片，找出所有 Age > 30 && City == "北京" 的用户，按 Score 降序排序，取前 10 个。当前 P99 是 15ms，你想优化它。请给出至少 4 个优化方向，分析每个方向的收益和代价，并说明你会先做哪个。

参考答案

先看当前实现的问题

// 假设的当前实现
func TopUsers(users []User) []User {
	var filtered []User
	for _, u := range users {              // ① 遍历
		if u.Age > 30 && u.City == "北京" {
			filtered = append(filtered, u)   // ② 每次 append 可能扩容
		}
	}
	sort.Slice(filtered, func(i, j int) bool {   // ③ 全量排序
		return filtered[i].Score > filtered[j].Score
	})
	if len(filtered) > 10 {
		return filtered[:10]                 // ④ 只要前 10
	}
	return filtered
}

四个问题：

① 缓存不友好：[]User 如果 User 很大（比如 200 字节），遍历时每个元素要加载 3-4 个缓存行，但只用到 3 个字段

② append 无预分配：最坏情况扩容 log(500) ≈ 9 次，每次重新分配 + 拷贝

③ 全量排序是浪费：只要前 10 个，却排序了全部（可能几百个）

④ 比较函数有开销：sort.Slice 用反射调用闭包，无法内联

优化方向 1：预分配 + 全量排序（最简单）

func TopUsersV1(users []User) []User {
	filtered := make([]User, 0, len(users))   // ★ 预分配最大容量
	for _, u := range users {
		if u.Age > 30 && u.City == "北京" {
			filtered = append(filtered, u)
		}
	}
	sort.Slice(filtered, func(i, j int) bool {
		return filtered[i].Score > filtered[j].Score
	})
	if len(filtered) > 10 {
		filtered = filtered[:10]
	}
	return filtered
}

收益：消除扩容和拷贝，约 20-30% 代价：可能浪费内存（预分配了全量） 风险：低

优化方向 2：部分选择（只排序需要的部分）

import "container/heap"
 
// 用最小堆维护 Top-10
type UserHeap []User
 
func (h UserHeap) Len() int           { return len(h) }
func (h UserHeap) Less(i, j int) bool { return h[i].Score < h[j].Score }  // 最小堆
func (h UserHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *UserHeap) Push(x any)        { *h = append(*h, x.(User)) }
func (h *UserHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}
 
func TopUsersV2(users []User, k int) []User {
	h := make(UserHeap, 0, k)
 
	for _, u := range users {
		if u.Age <= 30 || u.City != "北京" {
			continue
		}
		if h.Len() < k {
			heap.Push(&h, u)
		} else if u.Score > h[0].Score {   // h[0] 是当前 Top-K 里最小的
			h[0] = u                       // ★ 直接替换，不用 Push+Pop
			heap.Fix(&h, 0)
		}
	}
 
	// 排序输出
	result := make([]User, len(h))
	for i := len(h) - 1; i >= 0; i-- {
		result[i] = heap.Pop(&h).(User)
	}
	return result
}

复杂度：

  • 全量排序：O(m log m)，m = 过滤后的数量（假设 200）
  • Top-K 堆：O(n log k)，k=10，log(10) ≈ 3.3

收益：m=200 时，200×7.6 = 1520 vs 500×3.3 = 1650。当 n 大、k 小时优势明显；n=500, k=10 时提升约 30-40%

代价：代码复杂度上升（要实现堆接口） 风险：中（容易写错堆的比较方向）

优化方向 3：避免全量拷贝 —— 用索引+部分排序

// 只存索引，不拷贝 User（User 可能很大）
func TopUsersV3(users []User, k int) []int {
	// 存索引，过滤
	indices := make([]int, 0, len(users))
	for i := range users {
		if users[i].Age > 30 && users[i].City == "北京" {
			indices = append(indices, i)
		}
	}
 
	// 用 nth_element 思想：只把前 k 个排好
	// Go 标准库没有 nth_element，但可以自己实现快速选择
	if len(indices) > k {
		quickSelect(users, indices, k)
		indices = indices[:k]
		// 对这 k 个排序
		sort.Slice(indices, func(i, j int) bool {
			return users[indices[i]].Score > users[indices[j]].Score
		})
	}
	return indices
}
 
// 快速选择：O(n) 平均，找出第 k 大的元素并放到正确位置
func quickSelect(users []User, indices []int, k int) {
	left, right := 0, len(indices)-1
	for left < right {
		pivotIdx := partition(users, indices, left, right)
		if pivotIdx == k {
			return
		} else if pivotIdx < k {
			left = pivotIdx + 1
		} else {
			right = pivotIdx - 1
		}
	}
}
 
func partition(users []User, indices []int, left, right int) int {
	pivot := users[indices[right]].Score
	i := left
	for j := left; j < right; j++ {
		if users[indices[j]].Score > pivot {   // 降序
			indices[i], indices[j] = indices[j], indices[i]
			i++
		}
	}
	indices[i], indices[right] = indices[right], indices[i]
	return i
}

复杂度：O(n) 平均 + O(k log k) 收益：n=500, k=10 时，理论最优。实测提升约 50-60% 代价：代码最复杂，且快选最坏 O(n²) 风险：较高

优化方向 4：数据结构改造（SoA + 索引）—— 最大收益

如果这个函数真的极热，考虑改数据结构：

// ❌ AoS (Array of Structures)：每个 User 200 字节
type User struct {
	ID       int64
	Name     [64]byte
	Email    [64]byte
	Age      int32
	City     [32]byte
	Score    int32
	Bio      [128]byte
	AvatarURL [128]byte
	// ... 总共约 400 字节
}
 
// 遍历 500 个 User = 200KB，但实际只用到 Age/City/Score 三个字段 = 68 字节
// ★ 有效数据占比：68/400 = 17%
// ★ 也就是 83% 的内存带宽被浪费了
 
// ✅ SoA (Structure of Arrays)：只把需要的字段放一起
type UserTable struct {
	// 热字段（过滤和排序用），紧凑排列
	ages   []int32
	cities []string   // 或者用 intern 后的 int32 ID
	scores []int32
 
	// 冷字段，单独存
	names  []string
	bios   []string
	// ...
}
 
func (t *UserTable) TopUsers(k int) []int {
	// 只遍历热字段数组，缓存利用率 100%
	indices := make([]int, 0, k*2)
	// ... 同样的逻辑，但每次访问都是连续的
}

收益分析：

原方案：500 个 User × 400 字节 = 200KB
        每个缓存行 64 字节能装 0.16 个 User
        需要 3125 次缓存行加载

SoA：   500 × 4 (ages) + 500 × 4 (cityID) + 500 × 4 (scores) = 6KB
        每个缓存行能装 5.3 个用户的热数据
        需要 ~94 次缓存行加载

★ 缓存行加载减少 33 倍！

实测提升：3-5 倍 代价：数据结构改造，影响所有使用方 风险：高（改动大）

优化方向 5：缓存结果（如果适用）

// 如果 users 变化不频繁，缓存结果
type TopUsersCache struct {
	mu        sync.RWMutex
	result    []User
	version   uint64   // 数据版本号
	lastUpdate time.Time
}
 
func (c *TopUsersCache) Get(users []User, version uint64) []User {
	c.mu.RLock()
	if c.version == version {
		defer c.mu.RUnlock()
		return c.result
	}
	c.mu.RUnlock()
 
	// 重算
	result := TopUsersV1(users)
 
	c.mu.Lock()
	c.version = version
	c.result = result
	c.mu.Unlock()
	return result
}

收益：如果命中率高，接近 100% 代价：内存占用，缓存一致性问题 风险：中

我的执行顺序

第一步：先测量（这是前提，不是优化）

curl http://localhost:6060/debug/pprof/profile?seconds=30 > cpu.prof
go tool pprof -http=:8080 cpu.prof

确认：

  • 这个函数真的占 CPU 的多少？（如果 < 5%，不要优化）
  • 时间花在 filter 还是 sort？（决定优化方向）

第二步：做方向 1（预分配）

理由：

  • 一行代码改动
  • 收益 20-30%
  • 零风险

做完再测。如果 P99 已经达标，停在这里。

第三步：如果还不够，做方向 2（Top-K 堆）

理由：

  • 收益 30-40%
  • 代码复杂度可控（30 行）
  • 是标准的算法优化

第四步：如果还是不够，做方向 3（快速选择）

理由：

  • 收益 50-60%
  • 但要小心最坏情况（可以用 introselect，退化时切堆排序）

第五步：只有在这个函数是全局第一瓶颈时，才考虑方向 4（SoA 改造）

理由：

  • 收益最大（3-5 倍）
  • 但改动最大，影响所有调用方
  • 只有当其他优化都不够时，才值得这么大的改造成本

一句话总结

优化的顺序是”收益/成本比”的降序，不是”收益”的降序。

方向 1（预分配）:  收益 25%  成本 1 行    → 收益/成本 = 极高 ★★★★★
方向 2（Top-K）:   收益 35%  成本 30 行   → 收益/成本 = 高   ★★★★
方向 3（快选）:    收益 55%  成本 60 行   → 收益/成本 = 中   ★★★
方向 4（SoA）:     收益 400% 成本 改架构  → 收益/成本 = 低   ★★
方向 5（缓存）:    收益 90%  成本 一致性  → 看场景

而且每一步之后都要重新测量——因为优化到某个点后，瓶颈会转移。

这跟第 1 章小林的教训完全一致：先测量，再优化，再测量。 很多人跳过第一步，凭直觉优化，结果优化了不是瓶颈的地方。

小结：这一节你应该带走的东西

  1. 复杂度有四个维度：渐进复杂度、常数因子、缓存复杂度、摊还分析。大 O 只是其中一个，而且往往不是决定性的那个。

  2. 缓存效应能带来 8-64 倍的性能差异。 顺序访问 vs 随机访问：8-10 倍；矩阵行优先 vs 列优先：最多 64 倍。

  3. 分块（tiling）是缓存优化的核心手段：时间复杂度不变，但缓存复杂度从 O(n³/B) 降到 O(n³/(B√M))。

  4. 摊还 O(1) 不等于”每次都快”。Go 的 map 在 500 万元素时扩容会有 89ms 的停顿。在线服务必须预分配。

  5. Go 程序员的第五个维度：GC 友好。用 []int32 索引代替指针、SoA 布局、对象复用、避免逃逸、结构体对齐。CSR 格式的图算法能快 6 倍且零 GC 压力。

  6. 优化顺序按”收益/成本比”排，不是按”收益”排。而且每一步后重新测量。

下一节

02 · 算法设计范式全谱

老陈的预告：分治、贪心、动态规划、回溯——这些名字你都会背。但你知道什么时候该用哪个吗？更重要的是，你知道什么情况下它们都会失败，需要随机化或近似算法吗？

下一节我们用七个真实问题串起全部范式，每个都给 Go 实现。

反向链接