kimi-for-coding 在「实现LRU缓存」的评测结果

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

基本信息

  • 模型名称：kimi-for-coding
  • 用例名称：实现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）简化链表边界处理。 **示例：**

评测结果

综合得分

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

基础难度评测结果

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

模型生成产物

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

```python class DLinkedNode: """双向链表节点，存储键、值及前驱、后继指针。""" def __init__(self, key: int = 0, value: int = 0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: """ LRU 缓存：双向链表 + 哈希表实现。 数据结构选择原因： - 哈希表（dict）：提供 O(1) 平均时间复杂度的 key 查找，用于快速定位缓存项 是否存在并获取对应的节点指针。 - 双向链表：维护缓存项的「使用时间顺序」。头部为最近使用，尾部为最久未使用。 双向链表允许在已知节点指针的情况下，以 O(1) 时间完成「删除该节点」和 「在头部插入节点」，这与 LRU 需要频繁执行的「移动至头部」和「淘汰尾部」 操作完美契合。 - 哑节点（dummy head / tail）：消除链表为空或仅有一个节点时的特殊边界判断， 使所有指针操作统一化，降低出错概率。 """ def __init__(self, capacity: int): if capacity DLinkedNode # 初始化哑头、哑尾，相互连接形成空链表 self.dummy_head = DLinkedNode() self.dummy_tail = DLinkedNode() self.dummy_head.next = self.dummy_tail self.dummy_tail.prev = self.dummy_head def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] # 命中缓存：将节点移动到链表头部，标记为最近使用 self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: if key in self.cache: # 更新已有节点的值，并提升为最近使用 node = self.cache[key] node.value = value self._move_to_head(node) else: # 插入新节点到链表头部 new_node = DLinkedNode(key, value) self.cache[key] = new_node self._add_to_head(new_node) self.size += 1 # 若超出容量，淘汰链表尾部（最久未使用）节点 if self.size > self.capacity: tail = self._remove_tail() del self.cache[tail.key] self.size -= 1 def _remove_node(self, node: DLinkedNode) -> None: """将节点从当前位置摘除：前驱的后继指向后继，后继的前驱指向前驱""" prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _add_to_head(self, node: DLinkedNode) -> None: """将节点插入到哑头节点之后（链表真实头部）""" node.prev = self.dummy_head node.next = self.dummy_head.next self.dummy_head.next.prev = node self.dummy_head.next = node def _move_to_head(self, node: DLinkedNode) -> None: """将已有节点移动到头部：先摘除原位置，再插入头部""" self._remove_node(node) self._add_to_head(node) def _remove_tail(self) -> DLinkedNode: """摘除并返回哑尾节点之前的一个节点（最久未使用项）""" tail = self.dummy_tail.prev self._remove_node(tail) return tail # ==================== 测试用例 ==================== def run_tests(): print("=== Test...

AI 评审点评

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

【CLAUDE】该实现质量极高，完整满足题目所有要求：正确使用双向链表 + 哈希表 + 哑节点实现 O(1) 的 get/put 操作；LRU 语义（命中提升、淘汰最久未用）实现准确；代码风格规范，注释详尽，测试用例覆盖全面。是一份接近满分的标准答案级实现。 【GEMINI】这是一个非常优秀的 LRU 缓存实现。开发者不仅准确完成了所有功能要求，还通过合理的辅助方法（如 _add_to_head, _remove_node）保证了代码的可读性和可维护性。数据结构的解释非常到位，展示了对算法复杂度的深刻理解。虽然元数据中提到了并发处理，但由于用户具体要求中未提及，开发者专注于实现高性能的单线程版本，这符合当前任务的上下文。 【KIMI】该实现是一份高质量的 LRU Cache 代码，完全满足题目所有核心要求。双向链表 + 哈希表的经典组合实现正确，O(1) 时间复杂度达标，哑节点设计简化了边界处理。代码文档完善、注释清晰、测试覆盖充分。唯一可改进之处是题目提及的「并发处理」未在实现中体现，但这不影响核心功能的完整性和正确性。

进阶难度评测结果

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

模型生成产物

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

下面给出一个工程化、可运行的实现：泛型类型注解、`monotonic` 时钟、惰性 TTL、显式异常与完整的边界处理，末尾附带 8 个断言式测试用例。 ```python from __future__ import annotations import time from typing import Dict, Generic, Optional, TypeVar K = TypeVar("K") V = TypeVar("V") class _Node(Generic[K, V]): """双向链表节点。 选择「哈希表 + 双向链表」的原因： - 哈希表(dict) 负责 O(1) 地把 key 定位到链表节点； - 双向链表维护“最近使用”的顺序（头=MRU，尾=LRU），并且由于 哈希表中持有的是节点引用，可在 O(1) 内完成任意位置删除与头插； - 单向链表无法 O(1) 删除中间节点（拿不到前驱），所以必须双向； - 使用哑元 head/tail 可消除空链表与首尾边界的特判。 """ __slots__ = ("key", "value", "expire_at", "prev", "next") def __init__( self, key: K, value: V, expire_at: Optional[float], prev: Optional["_Node[K, V]"] = None, next: Optional["_Node[K, V]"] = None, ) -> None: self.key = key self.value = value # 基于 time.monotonic() 的绝对过期时刻；None 表示永不过期。 self.expire_at = expire_at self.prev = prev self.next = next class LRUCache(Generic[K, V]): """带可选 TTL 的 LRU（最近最少使用）缓存。 - get / put 均摊 O(1)。 - TTL 采用惰性删除：仅在被访问时检查；过期项视为不存在并被移除。 - 时钟使用 time.monotonic()，避免系统时钟回拨导致误判。 """ def __init__(self, capacity: int, default_ttl: Optional[float] = None) -> None: """初始化缓存。 :param capacity: 最大容量，必须为正整数。 :param default_ttl: 默认过期时间（秒）；None 表示不过期。 :raises ValueError: capacity V: """读取 key 对应的值，并将其提升为最近使用(MRU)。 :param key: 缓存键。 :return: 缓存值。 :raises KeyError: key 不存在或已过期（过期项会被惰性删除）。 """ node = self._cache.get(key) if node is None: raise KeyError(key) if self._is_expired(node): self._unlink(node) del self._cache[key] raise KeyError(key) self._move_to_head(node) return node.value def put(self, key: K, value: V, ttl: Optional[float] = None) -> None: """写入/更新 key，并将其置为最近使用(MRU)。 若容量已满，则淘汰最久未使用(LRU)项。 :param key: 缓存键。 :param value: 缓存值。 :param ttl: 本次写入的过期时间（秒）；None 表示沿用 default_ttl。 :raises ValueError: 最终生效的 ttl self._capacity: lru = self._pop_tail() if lru is not None: del self._cache[lru.key] def delete(self, key: K) -> bool: """显式删除 key。 :param key: 缓存键。 :return: 删除成功返回 True；key 不存在或已过期返回 False。 """ node = self._cache.get(key) if node is None: return False self._unlink(node) del self._cache[key] return...

AI 评审点评

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

【KIMI】该实现是一份工程化程度很高的LRU缓存代码，严格遵循了题目要求的核心数据结构约束（双向链表+哈希表），正确实现了O(1)的get/put操作和TTL惰性删除策略。代码结构清晰、类型注解完整、边界处理周到、测试覆盖充分。主要改进空间在于：消除类型忽略注释以提升类型安全、采用更标准的测试框架、以及若需满足更高并发要求可考虑加锁机制。整体而言，这是一份可作为生产代码参考的优质实现。

困难难度评测结果

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

模型生成产物

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

你的消息在 **「1. 基础接口」** 处被截断了，完整规格没有发出来。为了不空等，我先按生产级 LRU 缓存的**通用标准规格**实现一版完整方案；若与你的真实规格（TTL、加载器、权重、淘汰监听器等）有出入，把后半段补给我，我按你的接口签名对齐重构。 --- ## 0. 假设的规格（若不符请纠正） | 维度 | 选型 | 理由 | |---|---|---| | 并发模型 | **分段（striping）+ 每段独立锁** | 避免全局锁成为高并发瓶颈；接近 `ConcurrentLinkedHashMap`/旧 Guava 思路 | | 全局 LRU | **近似全局 LRU**（每段精确 LRU） | 精确全局 LRU 必须全局序列化，吞吐不可接受；这是性能/精度的显式权衡 | | 存储 | 每段 `LinkedHashMap(accessOrder=true)` | 天然按访问排序，淘汰 eldest 即 LRU | | 计数器 | `LongAdder` | 高并发下比 `AtomicLong` 竞争更小（分散 Cell） | | 过期 | 写入后 TTL（`expireAfterWrite`），**惰性清理** + 显式 `cleanUp()` | 不内置调度线程，避免资源泄漏；把调度权交给应用 | | 防击穿 | `get(key, loader)` **单飞（single-flight）** | 防止缓存击穿/惊群 | | 空值 | **拒绝 null key/value**（严格模式） | 避免歧义与 NPE 放大 | --- ## 1. 代码（分层，避免上帝类） ### `Cache.java` —— 基础接口 ```java package com.acme.cache; import java.util.Objects; import java.util.Optional; import java.util.function.Function; /** * 线程安全缓存的最小契约。所有实现必须满足： * * 并发 {@code put/get/remove} 不产生部分可见（撕裂）状态； * {@code null} 键/值一律被拒，避免 {@code null} 同时表示"缺失"与"值"的歧义。 * * * 边界约定：所有公开方法对 {@code null} 参数抛 {@link NullPointerException}； * 无返回值语义的方法（{@code put/remove/clear}）幂等。 */ public interface Cache { /** * 读取。命中刷新最近使用；缺失或已过期返回 {@link Optional#empty()}。 * * @param key 非空 * @return 命中的值；缺失/过期为空 * @throws NullPointerException key 为 null * @implSpec 过期按"惰性"处理：读到即删，计入 miss 而非 hit。 */ Optional get(K key); /** * 写入或覆盖；若总容量超限则按 LRU 淘汰。幂等。 * * @throws NullPointerException key 或 value 为 null */ void put(K key, V value); /** * 删除。不存在为 no-op（幂等）。 * * @throws NullPointerException key 为 null */ void remove(K key); /** 清空。幂等。 */ void clear(); /** * 近似当前条目数（快速路径，可能短暂落后）。 * 实现可在不加全局锁的情况下返回，用于监控；不要用于强一致决策。 */ int approximateSize(); /** 是否存在且未过期。等价于 {@code get(key).isPresent()} 但不刷新统计语义由实现决定。 */ default boolean containsKey(K key) { return get(Objects.requireNonNull(key, "key")).isPresent(); } /** 计算并缓存（不存在时）。默认实现不做单飞；高性能实现应覆盖以做防击穿。 */ default V getOrCompute(K key, Function loader) { Objects.requireNonNull(key, "key"); Objects.requireNonNull(loader, "loader"); Optional hit = get(key);...

AI 评审点评

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

【KIMI】该实现展现了扎实的并发编程功底，分段LRU+单飞防击穿的组合是生产级缓存的标准范式。文档和注释质量尤为突出，充分解释了设计权衡。主要扣分点在于：部分正确性细节（如size/count双计数风险、nanoTime溢出、单飞表全局热点）未严格处理，以及缺少权重、监听器、批量操作等高级特性使得'生产级'宣称略有折扣。作为'截断后按通用规格实现'的回应，其主动性和完整性值得肯定，但若严格对照'可用于生产环境'的要求，在极端场景下的健壮性仍需加强。

相关链接

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

加载中...
100%