Day 092 — 代码优化技巧 · 图解

优化思维框架

优化金字塔 (从重要到次要):

        ┌───────┐
        │ 算法  │  ← 最重要: O(n²) → O(n log n)
        ├───────┤
        │数据结构│  ← 关键: list → set/dict
        ├───────┤
        │ 循环  │  ← 减少迭代次数
        ├───────┤
        │ 缓存  │  ← 避免重复计算
        ├───────┤
        │ 细节  │  ← 微优化(最后考虑)
        └───────┘

数据结构性能对比

查找操作复杂度:
┌────────────┬─────────┬─────────┬─────────┐
│ 数据结构   │ 查找    │ 插入    │ 删除    │
├────────────┼─────────┼─────────┼─────────┤
│ list       │ O(n)    │ O(n)    │ O(n)    │
├────────────┼─────────┼─────────┼─────────┤
│ set        │ O(1)    │ O(1)    │ O(1)    │
├────────────┼─────────┼─────────┼─────────┤
│ dict       │ O(1)    │ O(1)    │ O(1)    │
├────────────┼─────────┼─────────┼─────────┤
│ deque      │ O(n)    │ O(1)    │ O(1)    │
└────────────┴─────────┴─────────┴─────────┘

选择指南:
• 需要快速查找 → set/dict
• 需要频繁头部插入 → deque
• 需要保持顺序 → list
• 需要键值对 → dict

循环优化策略

多次遍历 vs 单次遍历:

多次遍历 (3n 操作):
  ┌─────────────────────────────────────┐
  │ for item in data:                   │
  │     if item > max_val:              │
  │         max_val = item              │
  │ for item in data:                   │
  │     if item < min_val:              │
  │         min_val = item              │
  │ for item in data:                   │
  │     total += item                   │
  └─────────────────────────────────────┘

单次遍历 (n 操作):
  ┌─────────────────────────────────────┐
  │ for item in data:                   │
  │     if item > max_val:              │
  │         max_val = item              │
  │     if item < min_val:              │
  │         min_val = item              │
  │     total += item                   │
  └─────────────────────────────────────┘

缓存策略

无缓存 vs 有缓存:

无缓存 (fibonacci):
  fib(5) → fib(4) + fib(3)
  fib(4) → fib(3) + fib(2)
  fib(3) → fib(2) + fib(1)
  fib(2) → fib(1) + fib(0)
  
  重复计算: fib(3) 计算了 2 次
            fib(2) 计算了 3 次

有缓存 (lru_cache):
  fib(5) → fib(4) + fib(3)  ← 缓存 fib(4), fib(3)
  fib(4) → fib(3) + fib(2)  ← 缓存 fib(3), fib(2)
  fib(3) → fib(2) + fib(1)  ← 缓存 fib(2), fib(1)
  
  结果: 只计算一次!

字符串优化

字符串拼接 vs join:

字符串拼接 (O(n²)):
  result = ""
  for i in range(n):
      result += str(i)  # 每次创建新字符串!
  
  内存: [""]
       ["0"]
       ["01"]
       ["012"]
       ["0123"]
       ... O(n²) 内存操作

join (O(n)):
  parts = [str(i) for i in range(n)]
  result = "".join(parts)
  
  内存: ["0", "1", "2", ...]  # 一次性分配
       ["0123456789..."]      # 一次拼接

内存优化

列表 vs 生成器:

列表 (O(n) 内存):
  data = [i ** 2 for i in range(1000000)]
  
  内存: [0, 1, 4, 9, 16, ...]
       每个元素是 PyObject
       总内存: ~8MB

生成器 (O(1) 内存):
  data = (i ** 2 for i in range(1000000))
  
  内存: 生成器对象 (~100B)
       按需生成值
       总内存: ~100B

优化检查清单

优化检查清单:
┌─────────────────────────────────────────┐
│ 1. 算法复杂度                           │
│    └→ 是否可以用更好的算法？            │
├─────────────────────────────────────────┤
│ 2. 数据结构选择                         │
│    └→ list → set/dict 更合适吗？       │
├─────────────────────────────────────────┤
│ 3. 遍历次数                             │
│    └→ 能否减少循环次数？                │
├─────────────────────────────────────────┤
│ 4. 重复计算                             │
│    └→ 能否缓存结果？                    │
├─────────────────────────────────────────┤
│ 5. 内存使用                             │
│    └→ 是否有不必要的内存分配？          │
├─────────────────────────────────────────┤
│ 6. I/O 操作                             │
│    └→ 能否减少文件/网络操作？           │
└─────────────────────────────────────────┘

性能对比总结

优化效果对比:
┌─────────────────┬────────────┬────────────┬────────┐
│ 优化策略         │ 优化前     │ 优化后     │ 提速   │
├─────────────────┼────────────┼────────────┼────────┤
│ 列表→集合查找   │ O(n)       │ O(1)       │ 100x+  │
├─────────────────┼────────────┼────────────┼────────┤
│ 列表→双端队列   │ O(n) insert│ O(1) insert│ 10x+   │
├─────────────────┼────────────┼────────────┼────────┤
│ 多次→单次遍历   │ 3n 操作    │ n 操作     │ 3x     │
├─────────────────┼────────────┼────────────┼────────┤
│ 字符串拼接→join │ O(n²)      │ O(n)       │ 10x+   │
├─────────────────┼────────────┼────────────┼────────┤
│ 无缓存→LRU缓存  │ 指数时间   │ 线性时间   │ 1000x+ │
├─────────────────┼────────────┼────────────┼────────┤
│ 列表→生成器     │ O(n) 内存  │ O(1) 内存  │ 内存   │
└─────────────────┴────────────┴────────────┴────────┘