kimi-for-coding 在「实现布隆过滤器」的评测结果

基本信息

• 模型名称：kimi-for-coding
• 用例名称：实现布隆过滤器
• 测试类型：文本生成
• 评测维度：代码生成

系统提示词（System Prompt）

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

你是一名资深算法工程师，擅长数据结构与概率型数据结构的设计与实现。 回答要求： 1. 使用 Python 实现，代码结构清晰，包含必要的注释。 2. 在实现前简要说明所选哈希函数的原理及其优缺点（2-4 句话即可）。 3. 位数组操作必须使用 bytearray 或 bitarray 等显式位级结构，不得用普通 Python list of bool 代替。 4. 代码需包含简单的测试用例，验证 add() 和 contains() 的基本行为（包括正例和误判说明）。 5. 保持实现简洁，聚焦于核心逻辑，不需要引入复杂的工程化设计。

用户提示词（User Prompt）

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

请用 Python 实现一个基础的布隆过滤器（Bloom Filter）。 **背景说明：** 布隆过滤器是一种空间高效的概率型数据结构，用于判断一个元素「可能存在」或「一定不存在」于集合中。 它的核心原理是：通过多个哈希函数将元素映射到一个位数组的多个位置，查询时若所有对应位均为 1， 则判定元素「可能存在」（存在误判）；若任意一位为 0，则元素「一定不存在」。 **实现要求：** 1. 实现 `BloomFilter` 类，构造函数签名为 `__init__(self, size: int = 1000)`， 其中 `size` 为位数组的大小（默认 1000）。 2. 实现 `add(item: str) -> None` 方法，将元素添加到过滤器中。 3. 实现 `contains(item: str) -> bool` 方法，检查元素是否可能存在于过滤器中。 4. 使用**至少 2 个相互独立**的哈希函数（不得仅用 Python 内置 `hash()` 的单次调用）。 5. 位数组必须使用 `bytearray` 实现（每个字节存储 8 位），不得使用 `list` 直接存储布尔值。 **哈希函数说明：** 在代码注释或文字说明中，简要描述你所选用的哈希方案（例如：基于 hashlib 的多种算法、 双重哈希技巧 `h(i) = h1 + i*h2`，或其他方案），并说明其优缺点。 **测试验证：** 在代码末尾编写测试，验证以下场景： - 已添加的元素调用 `contains()` 必须返回 `True`（零假阴性）。 - 未添加的元素调用 `contains()` 大概率返回 `False`（允许少量误判，需说明）。

任务要求

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

1. 位数组使用 bytearray 实现，通过位运算（移位、与、或）正确读写单个比特位，不得用 list of bool 替代。
2. 至少使用 2 个独立的哈希函数，且哈希函数之间具有实质性差异（不同种子、不同算法或双重哈希），不得仅对同一哈希结果做简单加减偏移。
3. add() 方法能将元素正确映射到位数组的多个位置并置 1；contains() 方法检查所有对应位均为 1 时才返回 True，任意一位为 0 时返回 False。
4. 已添加的元素调用 contains() 必须始终返回 True（无假阴性），测试用例需覆盖此断言。
5. 代码包含对哈希函数选择的简要说明，指出其优点（如分布均匀性）和局限性（如计算开销或冲突概率）。

评测结果

综合得分

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

基础难度评测结果

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

模型生成产物

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

**哈希方案说明：** 采用「双重哈希技巧」`h_i = (h1 + i·h2) % size`，其中 `h1`、`h2` 分别由 `hashlib.md5` 与 `hashlib.sha1` 对元素编码后取整得到，从而派生出 `k` 个相互近似独立的哈希位置。优点是只需 2 次真实哈希计算即可得到 k 个位置，开销低且经证明接近 k 个独立哈希的效果；缺点是哈希质量依赖 MD5/SHA1（抗碰撞性对布隆过滤器足够，但非密码学场景），且在位数组很小时双重哈希可能出现相关性模式。 ```python import hashlib import math import random import string class BloomFilter: """ 基础布隆过滤器。 哈希方案：双重哈希 h_i(item) = (h1 + i * h2) % size h1 来自 MD5(item)，h2 来自 SHA1(item)，二者相互独立， 通过线性组合派生出 hash_count 个哈希位置。 位存储：bytearray，每个字节存 8 位，按 (pos >> 3) 定位字节、(pos & 7) 定位位。 """ def __init__(self, size: int = 1000): if size None: self._bits[pos >> 3] |= (1 bool: return (self._bits[pos >> 3] & (1 None: for pos in self._positions(item): self._set_bit(pos) def contains(self, item: str) -> bool: return all(self._get_bit(pos) for pos in self._positions(item)) def theoretical_fp_rate(self, n: int) -> float: """在已插入 n 个元素时的理论误判率：p ≈ (1 - e^(-k·n/m))^k。""" m, k = self.size, self.hash_count return (1 - math.exp(-k * n / m)) ** k # ----------------------------- 测试 ----------------------------- if __name__ == "__main__": bf = BloomFilter(size=1000) # 1) 正例：已添加元素必须全部命中（零假阴性） added = ["apple", "banana", "cherry", "date", "elderberry"] for w in added: bf.add(w) assert all(bf.contains(w) for w in added), "假阴性！布隆过滤器不允许已添加元素被判为不存在" print("[OK] 已添加元素全部返回 True（零假阴性）") # 2) 反例：未添加元素大概率为 False（允许少量误判） random.seed(42) not_added = set() while len(not_added) < 1000: not_added.add("".join(random.choices(string.ascii_lowercase, k=10))) not_added -= set(added) # 确保不与正例重叠 false_positives = sum(1 for w in not_added if bf.contains(w)) fp_rate = false_positives / len(not_added) print(f"[INFO] 测试 {len(not_added)} 个未添加元素，误判 {false_positives} 次，" f"实测误判率 {fp_rate:.4f}") print(f"[INFO] 理论误判率(n={len(added)}) ≈ {bf.theoretical_fp_rate(len(added)):.6f}") # 3) 直观演示误判随元素增多而上升（仅说明，不做断言） bf2 = BloomFilter(size=1000) for i in range(200): # 故意塞入较多元素使位数组趋于饱和 bf2.add(f"item-{i}") demo_fp = sum(1 for i in range(1000) if bf2.contains(f"unknown-{i}")) print(f"[DEMO] 塞入 200 个元素后，1000...

AI 评审点评

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

【KIMI】该实现是一个高质量的布隆过滤器，核心逻辑正确：bytearray 位操作规范、双重哈希方案合理、add/contains 功能无误。主要差距在于：(1) hash_count 硬编码为 7，缺乏灵活性；(2) 测试覆盖不如参考实现全面（缺少边界情况和参数校验测试）。代码结构清晰，注释充分，理论误判率计算是加分项。

进阶难度评测结果

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

模型生成产物

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

下面给出完整实现。先简要说明三个核心公式的来源，再给出代码与示例。 ## 一、核心公式的推导（写在代码注释里也会用到） 把 `n` 个元素插入到 `m` 位、使用 `k` 个哈希函数的布隆过滤器中，某位仍为 0 的概率约为 `e^(-kn/m)`，因此误判率 `p ≈ (1 - e^(-kn/m))^k` - **最优 k**：对 `k` 求导令其为 0，得 `k* = (m/n)·ln2`。此时 `(1 - e^(-kn/m)) = 1/2`。 - **最优 m**：代入 `k*`，`p = (1/2)^k`，两边取 `ln` 得 `ln p = -(m/n)(ln2)²`，整理即 `m = -n·ln p / (ln2)²`。 - **元素数估计**：由 `X/m ≈ 1 - e^(-kn/m)`（X 为置 1 位数）反解 `n = -(m/k)·ln(1 - X/m)`。 ## 二、实现代码（零外部依赖，内置哈希；注释中给出 MurmurHash3 选型建议） ```python import math import hashlib from numbers import Real from typing import Iterable class BloomFilter: """ 可配置布隆过滤器：给定预期元素数量 n 与期望误判率 p， 依据概率论公式自动推导最优位数组大小 m 与哈希函数个数 k。 数学关系（推导见模块说明）： m = -n * ln(p) / (ln 2) ** 2 # 最优位数组大小 k = (m / n) * ln 2 # 最优哈希函数个数 p_current = (1 - exp(-k*n_ins/m)) ** k # 当前误判率估计 n_est = -(m / k) * ln(1 - X/m) # 由置位数 X 估计元素个数 注意：contains() 返回 True 仅表示“可能存在”（可能误判）， 返回 False 表示“一定不存在”（永无误漏）。本实现非线程安全。 """ __slots__ = ( "_n", "_p", "_m", "_k", "_bits", "_n_inserted", "_bit_count", ) # ------------------------------------------------------------------ # # 构造与参数推导 # ------------------------------------------------------------------ # def __init__(self, n: int, p: float) -> None: """ 初始化布隆过滤器并自动推导最优 m、k。 :param n: 预期插入的元素数量，必须为正整数（n >= 1）。 :param p: 期望误判率，必须满足 0 = 1，收到 n={n}。") if isinstance(p, bool) or not isinstance(p, Real): raise ValueError(f"p 必须为 (0, 1) 内的实数，收到类型 {type(p).__name__}。") if not (0.0 =1，避免步长为 0 的退化 m, k = self._m, self._k for i in range(k): yield (h1 + i * h2) % m @staticmethod def _to_bytes(item) -> bytes: """ 将元素确定性序列化为字节，并用类型前缀避免 '1'(str) 与 1(int) 相撞。 支持字符串与数字；其它类型回退到 repr（不保证跨进程稳定）。 :param item: 待序列化元素。 :return: 带类型标签的字节串。 """ if isinstance(item, bool): return b"bool:" + (b"1" if item else b"0") if isinstance(item, str): return b"str:" + item.encode("utf-8") if isinstance(item, int): # 注意放在 bool 判断之后 return b"int:" + str(item).encode("ascii") if isinstance(item, float): return b"float:" + repr(item).encode("ascii") return ("obj:" + repr(item)).encode("utf-8") #...

AI 评审点评

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

【KIMI】该实现是一份高质量的布隆过滤器代码，数学推导严谨、接口完整、实现稳健。核心亮点包括：详细的公式推导文档、严格的参数校验（特别是bool排除）、类型安全的序列化（避免字符串与数字碰撞）、以及生产环境友好的MurmurHash3迁移建议。位操作和哈希设计的协同正确，边界处理周全。整体达到专业工程水准，仅在k取整策略和重复元素计数上有轻微保守处理，但不影响核心正确性。

困难难度评测结果

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

模型生成产物

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

下面给出一个**单文件、仅依赖标准库**的完整实现 `advanced_bloom.py`（`mmh3` 为可选加速，序列化默认走 `hashlib` 以保证跨环境确定性）。代码内联注释已包含公式来源/推导、哈希取舍、锁粒度与边界处理；文末为测试示例与设计要点小结。 ```python """ advanced_bloom.py ================= 高级布隆过滤器系统（标准库实现，mmh3 可选）： 1) StandardBloomFilter 基础标准布隆过滤器（union/intersection/序列化） 2) CountingBloomFilter 计数布隆过滤器（4-bit 或 int 计数器，饱和/防下溢） 3) ScalableBloomFilter 可扩展布隆过滤器（自动扩容 + 误判率收紧） 4) ConcurrentBloomFilter 并发安全（全局锁/分段锁可选）+ 性能统计 哈希策略（双重哈希，double hashing） --------------------------------- g_i(x) = (h1(x) + i * h2(x)) % m, i = 0..k-1 理论依据：Kirsch & Mitzenmacher (2006/2008) 证明仅用 2 个独立哈希即可 模拟 k 个独立哈希，误判率与真正 k 哈希同阶，且哈希计算量从 O(k) 降到 O(1)。 - h1/h2 默认由 sha512(x) 的前/后 64-bit 截取得到：确定性、跨平台、免第三方依赖。 - 可选 mmh3：速度更快（~ns 级）、分布好，但跨进程/跨版本种子一致性需注意， 故序列化默认仍走 hashlib（可移植）；需要吞吐时通过 hash_func 注入 mmh3。 - h2 规约到 [1, m-1]：h2 = (h2 % (m-1)) + 1，避免 h2==0 导致序列退化为单点。 取舍：sha512 单次哈希即可产出 128-bit 够用熵；md5 更快但抗碰撞弱， 本场景只看分布均匀性不看密码学安全，hashlib 方案已足够且可移植。 最优参数（来源：Bloom 1970；Mitzenmacher & Upfal, *Probability and Computing*） ---------------------------------------------------------------------- 给定期望元素数 n 与目标误判率 p： m = ceil( -(n * ln p) / (ln 2)^2 ) # 位数组长度 k = round( (m/n) * ln 2 ) # 哈希个数（最优 k = ln2 * m/n） 推导：最小化 fpp ≈ (1 - e^{-kn/m})^k 对 k 求导得 k* = (m/n)ln2， 代回得 p 与 m/n 的关系，反解出上式。k 至少为 1。 """ from __future__ import annotations import hashlib import math import struct import threading import time from typing import Callable, List, Optional, Tuple # 可选加速：mmh3（不强制安装；默认走 hashlib 保证可移植/可复现） try: import mmh3 # type: ignore _HAS_MMH3 = True except Exception: # pragma: no cover _HAS_MMH3 = False HashFunc = Callable[[bytes, int, int], int] # (item_bytes, i, m) -> index _MAGIC = b"PYBF" _VER = 1 # --------------------------------------------------------------------------- # # 工具函数 # --------------------------------------------------------------------------- # def _to_bytes(item) -> bytes: """统一把 item 转成 bytes：str->utf-8；bytes 原样；其它用 repr（保守）。""" if isinstance(item, bytes): return item if isinstance(item, str): return...

AI 评审点评

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

【KIMI】该实现是一份高质量的高级布隆过滤器系统，在标准库约束下完成了所有核心要求。双重哈希、计数器饱和/下溢保护、可扩展误判率收紧、并发分段锁等关键机制均实现正确且附有充分的设计说明。主要改进空间在于：ScalableBloomFilter的扩容判定指标可更精确（基于实际位填充率而非元素计数）、分段锁可进一步区分读写优化读并发、以及序列化状态重建的完全一致性。整体达到生产代码水准，文档与注释尤为出色。

相关链接

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

• 查看所有模型在此用例的表现：「实现布隆过滤器」
• 查看该模型的所有评测结果：kimi-for-coding
• 浏览同维度的其他用例：「代码生成」
• 返回排行榜首页