Elephant 在「LRU 缓存」的评测结果

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

基本信息

  • 模型名称：Elephant
  • 用例名称：LRU 缓存
  • 测试类型：文本生成
  • 评测维度：代码生成

系统提示词（System Prompt）

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

你是一名资深 Python 工程师，擅长数据结构与算法的教学和代码实现。 回答要求： 1. 使用 Python 标准语法，代码风格清晰、可读性强，添加必要的注释。 2. 实现完整的类结构，不得留有未实现的 pass 占位符。 3. 在代码之前或之后，用 2-4 句话简要说明你选择的数据结构及其原因。 4. 给出至少一组调用示例，展示 get 和 put 的基本使用效果。

用户提示词（User Prompt）

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

请用 Python 实现一个简单的 FIFO（先进先出）缓存类 `SimpleCache`。 **功能要求：** - `__init__(self, capacity: int)`：初始化缓存，`capacity` 为最大容量（正整数）。 - `get(self, key: int) -> int`：返回 `key` 对应的值；若 `key` 不存在，返回 `-1`。 - `put(self, key: int, value: int) -> None`：将键值对存入缓存。 - 若 `key` 已存在，则**更新**其对应的值（不改变该 key 的插入顺序）。 - 若缓存已满且 `key` 是新键，则**删除最早插入**的键值对，再插入新键值对。 **约束说明：** - 使用 Python 内置字典（`dict`）作为主要存储结构（Python 3.7+ 的字典保持插入顺序）。 - 不需要实现「访问即更新顺序」的 LRU 逻辑，仅按插入顺序淘汰。 - 无需考虑并发场景。 **接口模板：**

评测结果

综合得分

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

基础难度评测结果

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

模型生成产物

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

使用 Python 字典（dict）实现缓存，因其从 3.7 版本起保持插入顺序，可自然支持 FIFO 淘汰策略；结合字典的快速查找与列表顺序特性，能高效完成基本缓存操作。 ```python class SimpleCache: """ 一个简单的 FIFO（先进先出）缓存实现。 依赖 Python 3.7+ dict 的插入顺序特性管理淘汰顺序。 """ def __init__(self, capacity: int): """ 初始化缓存。 :param capacity: 缓存的最大容量（正整数） """ if capacity int: """ 获取指定键对应的值。 :param key: 要查询的键 :return: 若键存在，返回对应值；否则返回 -1 """ return self._store.get(key, -1) def put(self, key: int, value: int) -> None: """ 插入或更新键值对。 - 若键已存在，更新其值（不改变插入顺序）。 - 若缓存已满且键为新键，则删除最早插入的键值对，再插入新键值对。 :param key: 键 :param value: 值 """ # 键已存在：直接更新值（dict 会保留原插入位置） if key in self._store: self._store[key] = value return # 缓存已满：移除最早插入的键（dict 第一个键） if len(self._store) >= self._capacity: # popitem(last=False) 按 FIFO 顺序弹出最早项 self._store.popitem(last=False) # 插入新键值对 self._store[key] = value ``` ```python # 示例调用 cache = SimpleCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # 输出: 10（存在） cache.put(3, 30) # 缓存满，淘汰最早插入的键 1 print(cache.get(1)) # 输出: -1（已被淘汰） print(cache.get(2)) # 输出: 20 print(cache.get(3)) # 输出: 30 ```

AI 评审点评

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

【GEMINI】该回答在代码规范、文档编写和边界处理上表现优秀。然而，作为一名资深工程师，在核心算法实现上出现了关键的技术错误：误将 `collections.OrderedDict` 的 `popitem(last=False)` 方法直接应用于 Python 标准 `dict` 对象，导致代码在执行 FIFO 淘汰逻辑时会崩溃。这反映了对 Python 内置数据结构 API 细节掌握不够精确。 【KIMI】代码实现了 SimpleCache 类的基本功能，符合 FIFO 缓存的要求，代码风格良好，注释清晰。但在代码的健壮性方面还有改进空间，如对输入参数的类型和值进行检查。总体来说，代码是一个符合题目要求的简单 FIFO 缓存实现。

进阶难度评测结果

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

模型生成产物

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

本实现使用 **哈希表 + 双向链表** 的组合结构。哈希表提供 O(1) 的 key 定位，双向链表支持在 O(1) 时间内完成节点移动与删除。通过在链表头部维护最新访问节点、尾部维护最旧节点，可严格保证 get 和 put 均为 O(1)。 ```python class Node: """双向链表节点，存储键值对""" def __init__(self, key: int, value: int): self.key = key self.value = value self.prev = None self.next = None class LRUCache: """ LRU 缓存实现，保证 get 和 put 操作时间复杂度均为 O(1)。 使用哈希表定位节点 + 双向链表维护访问顺序： - 链表头部为最近使用节点 - 链表尾部为最久未使用节点（待淘汰） """ def __init__(self, capacity: int): if capacity Node # 创建伪头尾节点，避免边界判空 self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _add_node_to_head(self, node: Node): """将节点插入到链表头部（表示最近使用）""" node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node: Node): """从链表中移除指定节点""" 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): """将已有节点移动到头部（先移除再插入）""" self._remove_node(node) self._add_node_to_head(node) def _pop_tail(self) -> Node: """移除并返回链表尾部节点（最久未使用）""" node = self.tail.prev self._remove_node(node) return node def get(self, key: int) -> int: """ 获取 key 对应的值，若存在则将其标记为最近使用并返回值， 否则返回 -1。 """ node = self.cache.get(key) if not node: return -1 # 访问后更新为最近使用 self._move_to_head(node) return node.value def put(self, key: int, value: int): """ 插入或更新键值对： - 若 key 已存在，更新值并标记为最近使用； - 若 key 不存在且缓存已满，淘汰最久未使用 key 后插入； - 若 key 不存在且未满，直接插入。 所有操作均保持 O(1) 时间复杂度。 """ node = self.cache.get(key) if node: # 重复 put 同一 key：更新值并移至头部 node.value = value self._move_to_head(node) else: # 创建新节点并插入头部 new_node = Node(key, value) self.cache[key] = new_node self._add_node_to_head(new_node) self.size += 1 # 若超出容量，移除尾部节点 if self.size > self.capacity: tail = self._pop_tail() del self.cache[tail.key] self.size -= 1 # --- 示例用法与边界测试 --- if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # 返回 1，key=1 变为最近使用 cache.put(3, 3) # 淘汰 key=2（最久未使用） print(cache.get(2)) # 返回 -1（已被淘汰）...

AI 评审点评

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

【GEMINI】这是一份优秀的 LRU 缓存实现。候选人不仅提供了逻辑严密、性能达标的代码，还通过合理的数据结构封装和边界处理展示了深厚的算法功底。代码注释清晰，说明文档简洁有力，完全满足了任务的所有要求。 【KIMI】该实现总体上满足了LRU缓存的功能要求，时间复杂度和代码质量也达到了较高水平。但在一些细节方面还有改进空间，比如进一步优化变量命名和注释，以及明确说明put操作中移除尾部节点的时间复杂度保证。

困难难度评测结果

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

模型生成产物

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

选用哈希表+双向链表：哈希表提供O(1)定位，双向链表在O(1)内完成节点移动与淘汰，满足LRU语义。 线程安全采用`threading.RLock`粗粒度锁保护整个类（因需同步跨链表与哈希表的多步操作），保证并发安全且实现简洁。 ```python import threading class ThreadSafeLRUCache: class _Node: __slots__ = ("key", "value", "prev", "next") def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None def __init__(self, capacity: int): if capacity node # 伪头尾节点简化边界操作 self._head = self._Node() self._tail = self._Node() self._head.next = self._tail self._tail.prev = self._head self._lock = threading.RLock() # 保护所有共享结构（map+链表）的一致性 def _remove_node(self, node: _Node) -> None: """从链表中移除node（不释放内存）""" node.prev.next = node.next node.next.prev = node.prev def _add_to_head(self, node: _Node) -> None: """将node插入到伪头之后（最新使用）""" node.prev = self._head node.next = self._head.next self._head.next.prev = node self._head.next = node def _move_to_head(self, node: _Node) -> None: """已存在节点提升为最新使用""" self._remove_node(node) self._add_to_head(node) def _pop_tail(self) -> _Node: """弹出最久未使用节点（伪尾前一个）""" node = self._tail.prev self._remove_node(node) return node def get(self, key: int) -> int: with self._lock: if self._capacity == 0: return -1 node = self._map.get(key) if node is None: return -1 self._move_to_head(node) # 提升为最近使用 return node.value def put(self, key: int, value: int) -> None: with self._lock: if self._capacity == 0: return if key in self._map: node = self._map[key] node.value = value self._move_to_head(node) return # 新建节点并插入 node = self._Node(key, value) self._map[key] = node self._add_to_head(node) if len(self._map) > self._capacity: tail = self._pop_tail() del self._map[tail.key] # O(1)删除 ``` --- ## 任务二：线程安全的 LFU 缓存 实现 `ThreadSafeLFUCache`，满足： - `get(key)` 和 `put(key, value)` 均为 **O(1)** 时间复杂度 - 多线程并发调用时数据一致 - 淘汰**最不经常使用**的项；频率相同时淘汰**最久未使用** - `get` 不存在的 key 返回 -1 - 容量为 0 时，`put` 不存入任何数据，`get` 始终返回 -1 --- **LFU 频率更新逻辑与桶组织**： - 用哈希表 `key_node` 存储键到节点的映射，节点内记录 `key, value, freq`。 - 用哈希表 `freq_bucket` 将相同频率的节点组织成双向链表（按访问时间排序），并维护...

AI 评审点评

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

【KIMI】整体上，代码实现了LRU和LFU缓存的核心功能，包括节点的添加、删除、移动以及频率更新等。代码手动实现了所需的数据结构，没有使用OrderedDict等高级容器。线程安全性方面，代码使用了粗粒度的锁来保护共享数据结构，虽然牺牲了一些并发性能，但实现了代码的简洁性和线程安全。总的来说，代码满足了题目的要求，是一个高质量的实现。

相关链接

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

加载中...
100%