12. MapCoder：用类比和检索辅助代码生成

背景

人类程序员解决新问题时，通常会先回忆有没有见过类似的题目。见过类似的，就拿过来参考，调整细节；没见过，才从头推导。这个过程依赖经验和记忆，也是有经验的程序员比新手快的原因之一。

MapCoder（Islam et al., 2024）把这个思路引入了多 Agent 代码生成框架：先检索类似问题，再类比解法，再生成代码。

四个 Agent 的分工

MapCoder 的工作流由四个 Agent 顺序执行：

1. 检索 Agent（Retrieval Agent）

从一个预先构建的问题库里，找出和当前问题最相似的几个已解决问题。相似度可以用语义向量检索，也可以用关键词匹配。

检索的结果是一组"参考问题 + 参考解法"对：

当前问题：给定数组，找出所有乘积为负数的子数组数量

参考问题 1：给定数组，找出所有和为正数的子数组数量
参考解法 1：前缀和 + 哈希表，时间复杂度 O(n)

参考问题 2：给定数组，找出乘积最大的子数组
参考解法 2：动态规划，维护当前最大值和最小值

2. 类比 Agent（Analogy Agent）

把检索到的参考解法和当前问题放在一起，让 LLM 分析：这些解法里有哪些思路可以迁移到当前问题？

[类比 Agent 的分析]
参考问题 2 用动态规划维护乘积的最大值和最小值，
这个思路可以迁移：对于乘积的正负性，同样需要同时追踪
当前子数组的最大正乘积和最大负乘积（绝对值最大的负数），
因为负数乘以负数会变正。

这一步的目的是把参考解法的核心思想提炼出来，而不是直接复制代码。

3. 规划 Agent（Planning Agent）

根据类比 Agent 提炼的思路，制定当前问题的解题计划，用伪代码或自然语言描述算法步骤：

解题计划：
1. 初始化 max_prod = 1, min_prod = 1, count = 0
2. 遍历数组每个元素 x：
   a. 更新 max_prod = max(x, max_prod * x, min_prod * x)
   b. 更新 min_prod = min(x, max_prod * x, min_prod * x)
   c. 如果 max_prod < 0，说明当前子数组乘积为负，count += 1
3. 返回 count
注意：步骤 2a 和 2b 需要用临时变量避免提前覆盖

4. 编码 Agent（Coding Agent）

根据规划 Agent 的计划，生成最终的代码：

def count_negative_product_subarrays(nums):
    max_prod = 1
    min_prod = 1
    count = 0
    for x in nums:
        candidates = (x, max_prod * x, min_prod * x)
        new_max = max(candidates)
        new_min = min(candidates)
        max_prod, min_prod = new_max, new_min
        if max_prod < 0:
            count += 1
    return count

检索库的构建

MapCoder 的检索库通常来自：

已有的代码题目数据集（LeetCode、Codeforces 等）
训练集里的例题
人工整理的算法模板库

库的质量对结果影响很大。如果检索到的参考问题和当前问题相关性低，类比 Agent 生成的分析就没有意义，后续的规划和编码也容易偏离。

实验结果

论文在 HumanEval、MBPP 和 CodeContests 上的对比：

方法	HumanEval	MBPP	CodeContests
GPT-4 直接生成	86.6%	80.1%	6.4%
AlphaCodium	85.7%	—	—
MapCoder（GPT-4）	93.9%	83.1%	11.5%

在竞赛级别的编程题（CodeContests）上，MapCoder 比直接生成提升明显。这类题目往往需要特定的算法技巧，检索到类似题目并类比解法，比从零推导更稳定。

类比机制的实际价值

MapCoder 的核心假设是：相似问题的解法可以迁移。这个假设在某些情况下成立，在另一些情况下不成立。

成立的情况：问题涉及已知的算法模式（动态规划、图搜索、双指针等），检索到同类型题目后，解法的结构可以直接复用。

不成立的情况：题目有独特的约束条件，看起来和某个已知问题相似，但核心难点完全不同。这时候错误的类比会把 Agent 引向错误的方向，比硬想还差。

这也是为什么 MapCoder 在 HumanEval 这种相对标准的题目上提升明显，但在更新颖的竞赛题上提升幅度有限——题越新，越难找到真正相关的参考。

和其他多 Agent 方法的对比

方法	角色分工依据	外部知识	适合场景
AgentCoder	代码 vs 测试	无	有测试标准的任务
MapCoder	检索→类比→规划→编码	题目库	有参考题目可检索的场景
AlphaCodium	理解→测试→迭代	无	有明确输入输出的任务

MapCoder 对外部知识库有依赖，这是它和其他方法的主要区别。有好的题目库时效果好，没有时就退化成普通的多步骤生成。

（采用 CC BY-NC-SA 4.0 许可协议进行授权）

本文标题:12. MapCoder：用类比和检索辅助代码生成

本文链接:https://www.sshipanoo.com/blog/ai/code-agent-harness/12-MapCoder/

本文最后一次更新为天前，文章中的某些内容可能已过时！