代码优化器技能

概述

在保持功能正确性的前提下，重构代码以降低时间与空间复杂度。重点关注 C++、Java 和 Python 中已被验证的优化模式。

核心原则：可量化地改善复杂度，并验证行为未发生变更。

适用场景

适用于所有与性能相关的工作：

• 运行缓慢、超时、内存问题
• 嵌套循环、重复查找
• 算法/数据结构选型
• 复杂度分析请求

尤其适用于以下情况：

• 用户明确提及“optimize”、“speed up”、“performance”等关键词
• 代码中存在 O(N²) 或更差的时间复杂度模式
• 竞赛编程中出现超时错误（TLE）
• 存在内存压力或 GC 开销过高的问题

快速参考表

优化工作流

每次优化均须严格遵循以下步骤：

优化进度：
- [ ] 步骤 1：识别当前复杂度
- [ ] 步骤 2：分析瓶颈来源
- [ ] 步骤 3：选择优化策略
- [ ] 步骤 4：实施最小化变更
- [ ] 步骤 5：验证复杂度是否改善
- [ ] 步骤 6：确认行为未发生变化

步骤 1：识别当前复杂度

• 统计循环嵌套深度
• 识别数据结构操作（查找、插入、遍历）
• 计算最坏情况下的操作次数
• 以大 O 表示法表达

步骤 2：分析瓶颈来源

步骤 3：选择优化策略

参见下方「算法选型决策树」。

步骤 4：实施最小化变更

• 每次仅做一项变更
• 不进行捆绑式重构
• 不执行“顺手优化”类改进

步骤 5：验证复杂度是否改善

• 重新计算大 O 复杂度
• 确认是否达成预期优化目标
• 使用逐步增大的输入规模进行测试

步骤 6：确认行为未发生变化

• 运行全部现有测试用例
• 手动验证边界情况
• 对比优化前后的输出结果

算法选型决策树

digraph algorithm_selection {
    rankdir=TB;

    "Nested loops identified?" [shape=diamond];
    "Lookup operation?" [shape=diamond];
    "Hash Tablen(O(1) lookup)" [shape=box, style=filled, fillcolor="#ccffcc"];
    "Range query?" [shape=diamond];
    "Tree/Heapn(O(log N) query)" [shape=box, style=filled, fillcolor="#ccffcc"];
    "Sliding pattern?" [shape=diamond];
    "Two Pointers/Windown(O(N))" [shape=box, style=filled, fillcolor="#ccffcc"];
    "Subproblem reuse?" [shape=diamond];
    "DP/Memoizationn(Polynomial)" [shape=box, style=filled, fillcolor="#ccffcc"];
    "Ordering needed?" [shape=diamond];
    "Pre-sort oncen(O(N log N))" [shape=box, style=filled, fillcolor="#ccffcc"];
    "Keep nested loopsn(document constraint)" [shape=box, style=filled, fillcolor="#ffcccc"];

    "Nested loops identified?" -> "Lookup operation?";
    "Lookup operation?" -> "Hash Tablen(O(1) lookup)" [label="yes"];
    "Lookup operation?" -> "Range query?";
    "Range query?" -> "Tree/Heapn(O(log N) query)" [label="yes"];
    "Range query?" -> "Sliding pattern?";
    "Sliding pattern?" -> "Two Pointers/Windown(O(N))" [label="yes"];
    "Sliding pattern?" -> "Subproblem reuse?";
    "Subproblem reuse?" -> "DP/Memoizationn(Polynomial)" [label="yes"];
    "Subproblem reuse?" -> "Ordering needed?";
    "Ordering needed?" -> "Pre-sort oncen(O(N log N))" [label="yes"];
    "Ordering needed?" -> "Keep nested loopsn(document constraint)" [label="no - inherent O(N^2)"];
}

决策说明：

常见反模式汇总

完整反模式详情：参见 references/anti-patterns.md

优化模式库：参见 references/optimization-patterns.md

完整示例：参见 references/examples.md

复杂度公式：参见 references/complexity-formulas.md

语言特异性速查提示

危险信号 — 立即暂停并深入调查

若你发现自己产生如下想法，请立即停止：

• “只要让它更快就行”，却未进行任何测量
• “这个优化很明显”，却未做任何分析
• “测试仍能通过，所以没问题”，却未检查复杂度变化
• “我稍后再优化”，但该代码处于热点路径（hot path）
• 完成优化后跳过验证环节

以上任一情形出现，均意味着：立即暂停。严格遵循既定工作流。

常见借口辨析

不应优化的情形

• 代码已达到 O(N) 或 O(N log N)，且性能表现可接受
• 在原型开发或探索阶段进行过早优化
• 虽已识别热点路径，但尚未开展实际性能测量
• 问题本身具有固有复杂度（例如：必须检查所有数对）

决策逻辑：何时需要主动提问

切勿对关键性能代码凭空猜测约束条件。应主动询问：

• “最大输入规模是多少？”
• “这是对延迟敏感还是对吞吐量敏感？”
• “是否存在需要考虑的内存限制？”
• “目标时间/空间复杂度是什么？”

性能验证

在宣称优化成功之前，必须完成以下验证：

各语言性能剖析命令：

C++：

g++ -O2 -pg solution.cpp -o solution
./solution input.txt
gprof solution gmon.out > analysis.txt

Java：

java -Xprof Solution

Python：

python -m cProfile -s tottime solution.py

伸缩性测试（Scaling test）：

for size in 100 1000 10000 100000; do
    time ./solution input_${size}.txt
done
# 预期：O(N) 应呈线性增长；O(N log N) 应呈近似线性对数增长
# 警告：若输入规模翻倍导致耗时增至约四倍，则表明仍为 O(N²)