doubao-seed-2-1-pro 在「实现LRU缓存」的评测结果

这是该 AI 模型在此测试用例上的详细评测结果。

基本信息

  • 模型名称：doubao-seed-2-1-pro
  • 用例名称：实现LRU缓存
  • 测试类型：文本生成
  • 评测维度：代码生成

系统提示词（System Prompt）

这是给 AI 模型的背景设定和角色指令：

你是一名资深软件工程师，专注于数据结构与算法设计，熟悉 Python 语言规范。 回答要求： 1. 使用 Python 实现，代码需符合 PEP 8 规范，变量与方法命名清晰易读。 2. 必须使用「双向链表 + 哈希表」组合实现，并在代码注释或说明中解释选择该数据结构的原因。 3. 实现完成后，给出至少 3 个测试用例（含预期输出），覆盖正常操作与缓存淘汰场景。 4. 对核心逻辑（节点移动、淘汰操作）添加简短注释，帮助读者理解指针操作。

用户提示词（User Prompt）

这是用户给 AI 模型的具体任务要求：

请使用 Python 实现一个 LRU（最近最少使用）缓存类 `LRUCache`，具体要求如下： **功能要求：** - `__init__(self, capacity: int)`：初始化缓存，`capacity` 为正整数，表示缓存最大容量。 - `get(self, key: int) -> int`： - 若 `key` 存在于缓存中，返回对应的值，并将该项标记为「最近使用」。 - 若 `key` 不存在，返回 `-1`。 - `put(self, key: int, value: int) -> None`： - 若 `key` 已存在，更新其值，并将该项标记为「最近使用」。 - 若 `key` 不存在，插入新项。若插入后超出容量，则删除「最久未使用」的项。 **实现约束：** - `get` 和 `put` 操作的时间复杂度均须为 **O(1)**。 - 必须使用「双向链表 + 哈希表」实现，不得直接使用 `collections.OrderedDict` 等封装好 LRU 语义的标准库。 - 推荐使用哑节点（dummy head / tail）简化链表边界处理。 **示例：**

评测结果

综合得分

该模型在此用例的得分为：97.1 分（满分 100 分），已通过

基础难度评测结果

  • 得分：97.1 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

### LRU 缓存实现（双向链表 + 哈希表） #### 选型思路 1. **哈希表（字典）**：提供 O(1) 时间复杂度的键到节点的查找能力，解决链表无法快速定位节点的问题。 2. **双向链表**：维护节点的使用顺序（靠近哑头为最近使用，靠近哑尾为最久未使用）： - 支持 O(1) 时间的节点删除：通过节点自带的`prev/next`指针直接定位前后节点，无需遍历（单链表删除需 O(n) 找前驱）。 - 支持 O(1) 时间的头部插入（标记最近使用）、尾部删除（淘汰最久未用节点）。 3. **哑头/哑尾节点**：统一链表插入、删除逻辑，无需处理空链表、首尾节点操作的边界条件，减少空指针错误。 4. 节点存储`key`的必要性：淘汰尾部节点时，需要通过节点的`key`同步删除哈希表中的映射，否则会出现哈希表脏数据。 --- ### 完整代码 ```python from __future__ import annotations from typing import Optional class LRUCache: """ LRU（最近最少使用）缓存，get/put 操作时间复杂度均为 O(1) 实现方式：双向链表 + 哈希表 """ class Node: """双向链表节点，存储键值对与前后指针""" def __init__(self, key: int, value: int): self.key = key self.value = value self.prev: Optional[Node] = None self.next: Optional[Node] = None def __init__(self, capacity: int): if not isinstance(capacity, int) or capacity dummy_tail self.dummy_head = self.Node(0, 0) self.dummy_tail = self.Node(0, 0) self.dummy_head.next = self.dummy_tail self.dummy_tail.prev = self.dummy_head def _add_to_head(self, node: Node) -> None: """将节点插入到哑头节点之后（标记为最近使用）""" # 1. 先绑定新节点的前后指针，避免原链表指针丢失 node.prev = self.dummy_head node.next = self.dummy_head.next # 2. 更新原首节点的前驱指针 self.dummy_head.next.prev = node # 3. 更新哑头的后继指针，完成插入 self.dummy_head.next = node def _remove_node(self, node: Node) -> None: """从链表中移除指定节点（仅修改前后节点指针，O(1) 时间）""" prev_node = node.prev next_node = node.next # 让前后节点直接相连，跳过当前节点 prev_node.next = next_node next_node.prev = prev_node def _move_to_head(self, node: Node) -> None: """将已存在节点移动到链表头部（标记为最近使用）""" # 先从原位置摘除，再插入到头部 self._remove_node(node) self._add_to_head(node) def _pop_tail(self) -> Node: """移除并返回哑尾节点的前驱节点（即最久未使用的节点）""" lru_node = self.dummy_tail.prev self._remove_node(lru_node) return lru_node def get(self, key: int) -> int: """获取键对应的值，不存在返回 -1；访问后将节点标记为最近使用""" if key not in self.cache: return -1 target_node = self.cache[key] self._move_to_head(target_node) return target_node.value def put(self, key: int, value: int) -> None: """插入/更新键值对，超出容量时淘汰最久未使用的节点""" if key not in self.cache: # 新键：创建节点，加入哈希表和链表头部...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【CLAUDE】该实现质量极高，完整满足题目所有要求：正确使用双向链表 + 哈希表实现 O(1) 的 get/put，哑节点设计简化边界处理，节点存储 key 保证淘汰时数据一致性。选型思路说明详尽，核心逻辑注释到位，测试用例覆盖全面（4 个场景，超过要求的 3 个），代码规范性和可读性均属上乘。是一份接近满分的标准答案级实现。 【GEMINI】这是一份非常优秀的 LRU 缓存实现。不仅功能完全符合要求，而且在代码工程化（类型提示、哑节点使用）、文档说明（选型理由、核心逻辑注释）以及测试完备性（覆盖了基础、更新、边界、重复插入等多种场景）方面都表现出色。 【KIMI】该实现是一份高质量的LRU缓存实现，严格遵循题目要求使用双向链表+哈希表组合，时间复杂度满足O(1)要求，代码结构清晰、注释详尽、测试覆盖全面。主要优点包括：哑节点设计简化边界处理、Node存储key保证淘汰时哈希表同步清理、指针操作顺序安全（先绑定新节点再更新现有节点）。 minor 不足：size字段冗余、测试用例4的淘汰逻辑描述略有混淆，但不影响功能正确性。未实现线程安全（题目提及并发处理但未作为硬性要求），在basic难度下可接受。

进阶难度评测结果

  • 得分：92.9 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

```python from __future__ import annotations import time from typing import Any, Dict, Optional class _DListNode: """双向链表节点类，存储缓存项、过期时间及前后指针，为内部私有实现。""" def __init__( self, key: Any, value: Any, expire_at: float, prev: Optional[_DListNode] = None, next: Optional[_DListNode] = None, ) -> None: self.key = key self.value = value self.expire_at = expire_at self.prev = prev self.next = next class LRUCache: """ 带TTL惰性删除的LRU（最近最少使用）缓存实现，get/put操作时间复杂度均为O(1)。 数据结构选择说明： 1. 哈希表（Python dict）：提供O(1)时间复杂度的键到链表节点的快速查找，解决链表遍历查找效率低的问题。 2. 双向链表：支持O(1)时间复杂度的节点删除、头部插入、尾部弹出操作，完美适配LRU顺序维护需求： - 链表头部（哑节点后）为最近使用（MRU）节点 - 链表尾部（哑节点前）为最久未使用（LRU）节点，缓存满时优先淘汰 3. 哑节点（Dummy Head/Tail）：避免空链表、首尾节点操作的边界判断，简化代码逻辑，降低出错概率。 4. 节点冗余存储key：淘汰尾部节点时可直接获取对应键，实现哈希表映射的O(1)删除。 TTL策略说明： 采用惰性删除机制，仅当访问key时（get/put命中已存在key）检查是否过期，过期项立即移除； 不启动后台扫描线程，无额外性能开销，未访问的过期项会在缓存淘汰时被自然清理。 """ def __init__(self, capacity: int) -> None: """ 初始化LRU缓存实例。 Args: capacity: 缓存最大容量，必须为正整数。 Raises: ValueError: 当capacity不是正整数（含布尔值、0、负数、非整数类型）时抛出。 """ # 容量参数合法性校验 if ( not isinstance(capacity, int) or isinstance(capacity, bool) or capacity None: """将节点添加到链表头部（MRU位置），内部辅助方法。""" # 先设置新节点的前后指针，避免丢失原有链表引用 node.prev = self.head node.next = self.head.next # 调整原有节点指针完成插入 self.head.next.prev = node self.head.next = node def _remove_node(self, node: _DListNode) -> None: """从链表中移除指定节点（已知节点引用，O(1)时间），内部辅助方法。""" # 直接修改前后节点指针跳过当前节点 node.prev.next = node.next node.next.prev = node.prev # 断开节点引用，帮助垃圾回收 node.prev = None node.next = None def _move_to_head(self, node: _DListNode) -> None: """将指定节点移动到链表头部（标记为最近使用），内部辅助方法。""" self._remove_node(node) self._add_to_head(node) def _pop_tail(self) -> _DListNode: """移除并返回链表尾部节点（LRU位置），内部辅助方法。""" lru_node = self.tail.prev self._remove_node(lru_node) return lru_node def get(self, key: Any, default: Any = None) -> Any: """ 获取缓存中指定key对应的value。 访问规则： 1. 若key不存在或已过期，返回default默认值，过期项会被惰性删除。 2. 若key存在且未过期，返回对应value，并将该节点标记为最近使用。 Args: key: 要查询的缓存键，必须可哈希。 default: key不存在/过期时返回的默认值，默认为None。 Returns: 缓存的value值，或默认值。 Raises:...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【KIMI】该实现是一个高质量的LRU缓存，核心算法正确，数据结构选择恰当，代码规范且文档完善。主要不足在于完全未实现题目要求的并发处理（线程安全），这是一个明显的功能缺失。此外，测试用例中对时间敏感操作的边界处理可更稳健（如使用更长的sleep间隔或mock时间）。总体而言，作为教学或单线程场景下的实现非常优秀，但作为生产级代码需补充锁机制。

相关链接

您可以通过以下链接查看更多相关内容：

加载中...
100%