grok-4.7 在「实现跳表数据结构」的评测结果

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

基本信息

  • 模型名称：grok-4.7
  • 用例名称：实现跳表数据结构
  • 测试类型：文本生成
  • 评测维度：代码生成

系统提示词（System Prompt）

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

你是一名资深算法工程师，擅长数据结构设计与实现，尤其熟悉跳表、平衡树等概率性数据结构。 回答要求： 1. 在给出代码前，先用 2-4 句话简述跳表的核心设计思路（多层索引结构、查找路径、层级建立方式）。 2. 使用 Python 实现，代码结构清晰，包含必要的注释说明关键步骤。 3. 实现完成后，提供至少 5 个测试用例验证插入与查找的正确性，并打印输出结果。 4. 分析插入和查找操作的时间复杂度（平均情况）。

用户提示词（User Prompt）

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

请实现一个基础的跳表（Skip List）数据结构，满足以下要求： **功能要求：** 1. 支持插入整数元素（允许重复值插入时忽略或覆盖均可，需说明策略）。 2. 支持查找操作，返回目标值是否存在（True/False）。 3. 跳表最大层数固定为 4 层（MAX_LEVEL = 4），层级索引手动或按固定规则建立（无需随机化，例如每隔 2 个节点在上层建立索引）。 4. 查找时必须从最高层开始，逐层向下，体现跳表的多层索引加速原理。 **接口要求：**

任务要求

AI 模型需要满足以下要求：

  1. 【算法正确性】跳表核心逻辑（随机层级生成、多层索引维护、查找/插入/删除的前驱节点更新）实现正确，通过 10 万条数据的增删查验证，结果与 TreeMap 对照一致。
  2. 【并发安全性】使用细粒度锁（分段锁或节点级读写锁）而非全局锁，8 线程并发压力测试下无死锁、数据竞争或数据丢失，读操作可并发执行。
  3. 【工程化完备性】泛型设计正确（支持自定义 Comparator）、NodePool 对象池实现有效（删除节点可被复用）、SkipListStats 统计数据准确（avgSearchPathLength 误差 ≤ 5%）。
  4. 【批量操作与序列化】putAll 具备原子性语义（全部成功或全部回滚），serialize/deserialize 往返一致性通过验证，序列化格式包含魔数和版本号字段。
  5. 【代码质量】包含完整的 Javadoc/Doxygen 注释、关键步骤行内注释，代码结构清晰（职责分离），可直接编译运行，无第三方依赖。
  6. 【复杂度分析】在答案末尾提供各操作的期望/最坏时间复杂度分析，并说明细粒度锁对并发吞吐量的影响。

评测结果

综合得分

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

基础难度评测结果

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

模型生成产物

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

跳表在最底层用一条有序链表保存全部元素，并在其上按固定间隔抽出节点，建成少量“快速通道”。查找始终从最高层开始，在当前层向右走到最后一个仍小于目标的节点，再下降一层，直到第 0 层确认是否命中。本实现不做随机抛硬币：按排序后的位置建索引，能被 \(2^k\) 整除的位置提升到第 \(k\) 层，最高只到第 3 层（共 4 层）。重复值采用忽略策略：已存在则不再插入，跳表按集合语义工作。 ```python """固定 4 层、按位置建立索引的跳表。重复插入直接忽略。""" MAX_LEVEL = 4 # 层号为 0..3 class Node: def __init__(self, value, level): self.value = value self.level = level # 该节点出现的最高层 # forward[i] 指向同一层的后继；只为实际参与的层分配指针 self.forward = [None] * (level + 1) class SkipList: def __init__(self, max_level=MAX_LEVEL): if max_level != MAX_LEVEL: raise ValueError("本题要求最大层数固定为 4") self.max_level = max_level # 头结点不存业务值，但拥有全部层的指针，作为每层链表的起点 self.header = Node(None, max_level - 1) @staticmethod def _level_of_position(pos): """位置从 1 计。pos 能被 2^k 整除则至少出现在第 k 层，且不超过 3。""" level = 0 while level ".join(parts) if parts else "(empty)" print(f"Level {lv}: {body}") def run_tests(): print("策略：重复值忽略，不覆盖、不新增节点。") # 用例 1：空表查找 sl = SkipList() print("用例1 空表查找 1:", sl.search(1)) # 用例 2：单元素插入与查找 sl = SkipList() print("用例2 插入 5:", sl.insert(5)) print("用例2 查找 5:", sl.search(5)) print("用例2 查找 3:", sl.search(3)) # 用例 3：无序插入 + 重复忽略 sl = SkipList() inserted = [sl.insert(x) for x in (1, 3, 2, 3, 2)] print("用例3 各次插入是否成功:", inserted) print("用例3 底层序列:", sl.values()) print("用例3 查找 2:", sl.search(2), "查找 4:", sl.search(4)) # 用例 4：满 8 个节点，四层索引都出现，并打印查找路径 sl = SkipList() for v in range(10, 90, 10): sl.insert(v) print("用例4 索引结构:") sl.display() print("用例4 查找 70 的路径:") print("用例4 查找 70:", sl.search(70, trace=True)) print("用例4 查找 25:", sl.search(25)) print("用例4 查找 80:", sl.search(80)) print("用例4 查找 10:", sl.search(10)) print("用例4 查找 90:", sl.search(90)) # 用例 5：降序插入后仍能有序查找 sl = SkipList() for v in (9, 7, 5, 3, 1): sl.insert(v) print("用例5 底层序列:", sl.values()) print( "用例5 查找 1/6/9:", sl.search(1), sl.search(6), sl.search(9), ) # 用例 6：负数、零，以及重复 -5 sl = SkipList() flags = [sl.insert(v) for v in (-5, 0, 5, -5)] print("用例6 插入是否成功:", flags) print("用例6 底层序列:", sl.values()) print( "用例6 查找 0/-1/-5:", sl.search(0), sl.search(-1), sl.search(-5), ) if...

AI 评审点评

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

【CLAUDE】整体质量较好：固定 4 层、按位置每 2^k 个节点提升一级的索引方案实现正确，查找严格自顶向下逐层下降，插入后重建索引虽笨重但能维持不变量，6 组测试覆盖了空表、单元素、重复值、满 8 节点四层结构与降序插入等场景，输出经推演与代码行为一致。最出彩的是复杂度分析——作者没有套用随机跳表的 O(log n)，而是正确指出固定 4 层下平均查找与插入退化为 O(n)，仅常数优于单链表，并说明只有层数随 n 增长到 Θ(log n) 时才恢复对数复杂度。主要短板有三：任务描述中列入的删除操作完全缺失；_rebuild_index 全量重建使每次插入都是 O(n) 且判重与定位存在重复遍历，工程上可以更优；对「按位置建立索引导致插入时后续节点索引归属整体迁移」这一副作用缺少说明。此外，本评测包中用户消息的接口要求部分被截断，无法核对接口命名、返回值约定等是否符合规定，评分未对这部分作额外加减。 【GEMINI】生成质量优秀，严格遵循了所有系统约束与用户指令。在实现固定层级跳表的基础上，查找路径打印清晰直观，测试用例充分全面，复杂度分析客观深入。 【KIMI】该实现能够完成基本功能，查找逻辑正确，测试覆盖充分，代码可读性较好。但插入操作采用全局重建索引的方式严重偏离了跳表的核心设计思想——跳表的优雅之处在于通过前驱指针数组实现O(log n)的局部插入，而非本题中的O(n)全量重建。虽然题目允许手动建立索引，但实现方式过于粗暴，未能体现跳表作为概率性数据结构的工程价值。复杂度分析客观准确，但实现层面未能将理论认知转化为代码实践。综合评价：功能达标，原理理解有待深化。

进阶难度评测结果

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

模型生成产物

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

跳表用多层有序链表加哨兵头节点实现，查找、插入、删除都从当前最高层向右跳、再逐层下降，期望时间为 O(log n)。层级按 P=0.5 抛硬币生成：每升一层概率减半，节点期望指针数约为 2，在空间与查找步数之间比较均衡；层数上限 16，可覆盖远超 2^16 规模的实际数据。删除时自底向上拆掉各层前向指针，若头节点在最高层的后继变为空，则把有效层数下调，避免在空层上浪费比较。 ```python import random from typing import List, Optional class SkipListNode: """跳表节点：val 为键，forward[i] 为第 i 层的后继。""" def __init__(self, val: int, level: int): self.val = val # level 为该节点最高层下标，指针数组长度为 level + 1 self.forward: List[Optional["SkipListNode"]] = [None] * (level + 1) class SkipList: """不重复整数跳表。MAX_LEVEL=16，晋升概率 P=0.5。""" MAX_LEVEL = 16 P = 0.5 def __init__(self) -> None: # 哨兵头节点不存业务键，各层 forward 初始为空，简化边界 self.header = SkipListNode(0, self.MAX_LEVEL - 1) self.level = 0 # 当前有效最高层（0 起） def _random_level(self) -> int: """抛硬币决定新节点层数：连续 random() List[SkipListNode]: """ 返回 update[i]：第 i 层上严格小于 val 的最右节点。 从当前最高层向下降，只在已有层上行走。 """ update: List[Optional[SkipListNode]] = [None] * self.MAX_LEVEL curr = self.header for i in range(self.level, -1, -1): while curr.forward[i] is not None and curr.forward[i].val bool: """从最高有效层下降查找，期望 O(log n)。""" curr = self.header for i in range(self.level, -1, -1): while curr.forward[i] is not None and curr.forward[i].val None: """插入 val；已存在则忽略。新节点层数由抛硬币决定，并改写各层前驱指针。""" update = self._predecessors(val) nxt = update[0].forward[0] if nxt is not None and nxt.val == val: return lvl = self._random_level() # 新节点高于当前有效层时，高出的层前驱就是头节点，并抬高有效层 if lvl > self.level: for i in range(self.level + 1, lvl + 1): update[i] = self.header self.level = lvl node = SkipListNode(val, lvl) for i in range(lvl + 1): node.forward[i] = update[i].forward[i] update[i].forward[i] = node def delete(self, val: int) -> bool: """删除 val。成功后若最高层已空则收缩有效层数。""" update = self._predecessors(val) target = update[0].forward[0] if target is None or target.val != val: return False # 只拆目标实际出现的那些层；更高层前驱不再指向它即可停止 for i in range(self.level + 1): if update[i].forward[i] is not target: break update[i].forward[i] = target.forward[i] while self.level > 0 and self.header.forward[self.level] is None:...

AI 评审点评

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

【CLAUDE】整体实现质量高，算法正确性强，工程规范良好。代码可直接运行并通过所有8个测试用例，覆盖了题目要求的全部场景。设计思路简洁准确，代码注释到位。 【GEMINI】该模型生成的内容完全满足并超越了 prompt 的各项要求。先期设计思路清晰概括了概率选择与收缩逻辑，代码实现规范严谨、算法正确无误，测试用例设计详实，属于高质量的专家级代码输出。 【KIMI】该实现展示了跳表的基本架构和思路，search、insert、range_query功能大体正确，但delete操作存在关键的层指针更新缺陷：使用break提前终止循环导致高层前驱指针可能未更新，这会引发后续的悬空指针和层收缩问题。类型注解的不一致也反映了工程严谨性的不足。作为medium难度的实现，基本思路合格但细节处理有待加强，需要在层更新逻辑和类型安全方面进行修正。

相关链接

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

加载中...
100%