编码母题 / P1 / Agent 运行时 / 04

上下文预算与消息裁剪器

先读清题意与边界，独立尝试，再展开思路并对照可运行的参考代码。

重要程度高价值难度困难预计完成45–60 分钟

难度按 LeetCode 简单／中等／困难三档估计；工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间，因经验而异。

题目是什么

在 tokenBudget 内选择系统消息和最近对话。工具调用与响应必须成组保留；过大的工具结果可压缩，不能留下孤立响应。

输入输出示例

预算不足以同时容纳一次 assistant tool_calls 和对应 tool 回复时，应整组舍弃。

练习起手式与验证

复制代码后补全空方法，再运行下方三组验证；复杂题所需的辅助类型与输入准备一并放在代码块中。

/*
 * 题目：上下文预算与消息裁剪器
 * 要求：在 tokenBudget 内选择系统消息和最近对话。工具调用与响应必须成组保留；
 * 过大的工具结果可压缩，不能留下孤立响应。
 * 示例：预算不足以同时容纳一次 assistant tool_calls 和对应 tool
 * 回复时，应整组舍弃。
 */
function groupMessages(messages) {}
function buildContext(messages, { tokenBudget, tokenCounter, compactTool = (m) => m }) {}

const count = (m) => String(m.content || "").length + (m.toolCalls ? 1 : 0);
const messages = [
  { role: "system", content: "sys" },
  { role: "user", content: "oldold" },
  { role: "assistant", content: "call", toolCalls: [{ id: "1" }] },
  { role: "tool", toolCallId: "1", content: "result" },
  { role: "user", content: "new" },
];
const context = buildContext(messages, {
  tokenBudget: 18,
  tokenCounter: count,
});
console.log(context.messages.map((m) => m.content)); // 预期：["sys", "call", "result", "new"]
console.log(context.usedTokens <= 18); // 预期：true
console.log((() => { try { (() => buildContext([{ role: "tool", toolCallId: "1" }], {
    tokenBudget: 10,
    tokenCounter: count,
  }))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）

解题思路

展开思路、不变量与常见边界

关键切入点：先把消息构造成原子组，再从最新向旧选择；系统消息始终保留且计入预算。

核心模型：先把消息切成原子组，再从后向前选择；最后恢复原顺序。不变量：总 Token 不超预算；系统消息顺序不变；孤立、重复或缺失响应的 tool 调用组直接报错。生产系统可在丢弃内容前生成摘要，但摘要本身也必须计入预算。

参考代码与验证

“关键机制”注释用于解释实现，下载链接提供未经页面注释修改的原始 JS 文件。

// 关键机制：先把消息构造成原子组，再从最新向旧选择；系统消息始终保留且计入预算。
function groupMessages(messages) {
  const groups = [];
  for (let i = 0; i < messages.length; i += 1) {
    const message = messages[i];
    if (message.role === "assistant" && message.toolCalls?.length) {
      const ids = new Set(message.toolCalls.map((c) => c.id));
      if (ids.size !== message.toolCalls.length)
        throw new Error("duplicate tool call id");
      const group = [message];
      while (
        i + 1 < messages.length &&
        messages[i + 1].role === "tool" &&
        ids.has(messages[i + 1].toolCallId)
      )
        group.push(messages[++i]);
      const received = group.slice(1).map((m) => m.toolCallId);
      if (received.length !== ids.size || new Set(received).size !== ids.size)
        throw new Error("incomplete tool call group");
      groups.push(group);
    } else if (message.role === "tool")
      throw new Error("orphan tool message");
    else groups.push([message]);
  }
  return groups;
}
function buildContext(
  messages,
  { tokenBudget, tokenCounter, compactTool = (m) => m },
) {
  if (!(tokenBudget >= 0) || typeof tokenCounter !== "function")
    throw new TypeError("invalid options");
  const normalized = messages.map((m) =>
    m.role === "tool" ? compactTool(m) : m,
  );
  const systems = normalized.filter((m) => m.role === "system");
  const rest = normalized.filter((m) => m.role !== "system");
  let used = systems.reduce((sum, m) => sum + tokenCounter(m), 0);
  if (used > tokenBudget)
    throw new Error("system messages exceed token budget");
  const selected = [];
  const groups = groupMessages(rest);
  for (let i = groups.length - 1; i >= 0; i -= 1) {
    const cost = groups[i].reduce((sum, m) => sum + tokenCounter(m), 0);
    if (used + cost <= tokenBudget) {
      selected.push(groups[i]);
      used += cost;
    }
  }
  return {
    messages: [...systems, ...selected.reverse().flat()],
    usedTokens: used,
  };
}

// 三组以上可直接运行的验证。
const count = (m) => String(m.content || "").length + (m.toolCalls ? 1 : 0);
const messages = [
  { role: "system", content: "sys" },
  { role: "user", content: "oldold" },
  { role: "assistant", content: "call", toolCalls: [{ id: "1" }] },
  { role: "tool", toolCallId: "1", content: "result" },
  { role: "user", content: "new" },
];
const context = buildContext(messages, {
  tokenBudget: 18,
  tokenCounter: count,
});
console.log(context.messages.map((m) => m.content)); // 预期：["sys", "call", "result", "new"]
console.log(context.usedTokens <= 18); // 预期：true
console.log((() => { try { (() => buildContext([{ role: "tool", toolCallId: "1" }], {
    tokenBudget: 10,
    tokenCounter: count,
  }))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）
console.log((() => { try { (() => groupMessages([{ role: "assistant", toolCalls: [{ id: "1" }] }]))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）

复杂度分析

时间复杂度：O(M+C)。线性分组 M 条消息并处理 C 个工具调用 id。

空间复杂度：O(M+C)。规范化消息、分组和选择结果最多与输入规模相当。

下载原始 JS 文件