GLM-5.1 在「实现布隆过滤器」的评测结果
这是该 AI 模型在此测试用例上的详细评测结果。
基本信息
- 模型名称：GLM-5.1
- 用例名称：实现布隆过滤器
- 测试类型：文本生成
- 评测维度：代码生成
系统提示词（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 模型需要满足以下要求：
- 位数组使用 bytearray 实现，通过位运算（移位、与、或）正确读写单个比特位，不得用 list of bool 替代。
- 至少使用 2 个独立的哈希函数，且哈希函数之间具有实质性差异（不同种子、不同算法或双重哈希），不得仅对同一哈希结果做简单加减偏移。
- add() 方法能将元素正确映射到位数组的多个位置并置 1；contains() 方法检查所有对应位均为 1 时才返回 True，任意一位为 0 时返回 False。
- 已添加的元素调用 contains() 必须始终返回 True（无假阴性），测试用例需覆盖此断言。
- 代码包含对哈希函数选择的简要说明，指出其优点（如分布均匀性）和局限性（如计算开销或冲突概率）。
评测结果
综合得分
该模型在此用例的得分为：93.5 分（满分 100 分），已通过
基础难度评测结果
- 得分：93.5 分
- 通过状态：已通过
模型生成产物
以下是该模型针对此任务的实际生成内容：
### 哈希函数方案说明 **选用方案**：双重哈希技巧，即 $h_i(x) = (h_1(x) + i \times h_2(x)) \pmod m$。其中 $h_1$ 和 $h_2$ 分别由 MD5 和 SHA256 算法生成截取而来，$i$ 为哈希函数索引，$m$ 为位数组大小。 **优点**：仅需计算两次基础哈希即可模拟出 $k$ 个相互独立的哈希函数，大幅减少计算开销；使用加密哈希保证了分布的均匀性与跨平台一致性（不受 Python 内置 `hash()` 随机种子影响）。 **缺点**：MD5/SHA256 等加密哈希相比 MurmurHash 等非加密哈希运算较重，在极端高吞吐场景下可能成为瓶颈；双重哈希在特定模式输入下可能存在微弱的相关性，但对基础实现影响极小。 --- ### Python 实现 ```python import hashlib class BloomFilter: def __init__(self, size: int = 1000): self.size = size # 使用 bytearray 初始化位数组，每个字节包含 8 位 # 计算需要的字节数：(size + 7) // 8 确保覆盖所有位 self.bit_array = bytearray((size + 7) // 8) self.hash_count = 3 # 使用 3 个哈希函数，满足至少 2 个的要求 def _get_hashes(self, item: str): """ 使用双重哈希技巧生成多个哈希值 """ # 生成两个基础哈希值，使用不同的算法和盐值保证独立性 h1 = int(hashlib.md5(("salt1" + item).encode()).hexdigest(), 16) h2 = int(hashlib.sha256(("salt2" + item).encode()).hexdigest(), 16) # h(i) = (h1 + i * h2) % size for i in range(self.hash_count): yield (h1 + i * h2) % self.size def add(self, item: str) -> None: """将元素添加到布隆过滤器中""" for hash_val in self._get_hashes(item): byte_index = hash_val // 8 # 定位所在字节 bit_offset = hash_val % 8 # 定位字节内的位偏移 # 使用按位或操作将对应位置设为 1 self.bit_array[byte_index] |= (1 bool: """检查元素是否可能存在于布隆过滤器中""" for hash_val in self._get_hashes(item): byte_index = hash_val // 8 bit_offset = hash_val % 8 # 使用按位与操作检查对应位是否为 0 if (self.bit_array[byte_index] & (1 误判（False Positive）") else: print(f"contains('{item}'): {result} -> 正确判定不存在") # 3. 高误判率场景演示 print("\n--- 高误判率场景演示 ---") # 故意使用极小的位数组来填充大量数据，以触发并观察误判现象 bf_small = BloomFilter(size=20) for i in range(15): bf_small.add(f"item_{i}") false_positive_count = 0 for i in range(15, 30): if bf_small.contains(f"item_{i}"): false_positive_count += 1 print(f"在 size=20 的过滤器中添加 15 个元素后，") print(f"对 15 个未添加元素进行查询，发生误判次数: {false_positive_count}") print("说明：布隆过滤器判断不存在则一定不存在，判断存在则有一定概率是误判。") ``` ### 代码要点解析： 1. **位级操作**：使用 `bytearray` 存储，通过 `hash_val // 8` 和 `hash_val % 8` 定位字节和位。置位用 `|= (1 << offset)`，检查用 `& (1 << offset)`，完全符合底层位操作规范。 2. **双重哈希**：通过 MD5 和 SHA256...
AI 评审点评
以下是 AI 评审对该模型输出的点评：
【CLAUDE】这是一个高质量的布隆过滤器实现。位数组操作使用 bytearray 并通过标准位运算实现，完全符合规范；双重哈希方案设计合理，使用 MD5 和 SHA256 配合不同盐值保证独立性，哈希函数说明准确且有深度；核心功能正确，测试用例覆盖正例、反例和高误判场景，有效验证了零假阴性特性。代码结构清晰，注释详尽，具有良好的可读性。主要改进空间在于：可补充边界情况测试、输出量化的误判率统计、考虑使用计算开销更小的哈希算法（如 SHA1 替代 SHA256）以优化性能。整体而言，该实现在功能正确性、代码质量和工程实践方面均达到优秀水平。 【GEMINI】这是一份高质量的实现。模型准确理解了布隆过滤器的核心原理，并严格按照要求使用了 bytearray 进行位级操作。代码结构清晰，哈希方案选择科学（双重哈希是工业界常用的优化手段），注释详尽且测试用例设计合理，能够很好地展示数据结构的概率性特征。 【KIMI】整体而言，代码实现了布隆过滤器的核心功能，位数组操作和哈希函数的选择都符合要求。代码结构清晰，注释详尽，易于理解。测试用例覆盖了基本功能和边界情况，但可以进一步增强对误判情况的说明，以更全面地展示布隆过滤器的特性。
进阶难度评测结果
- 得分：91.8 分
- 通过状态：已通过
模型生成产物
以下是该模型针对此任务的实际生成内容：
以下是为您实现的可配置、基于数学原理自动推导最优参数的布隆过滤器。 ### 核心数学公式说明 在给定预期元素数量 $n$ 和期望误判率 $p$ 的情况下，布隆过滤器的最优参数推导基于以下数学公式： 1. **最优位数组大小 $m$**： $$m = -\frac{n \ln(p)}{(\ln 2)^2}$$ *来源*：基于误判率公式 $p \approx (1 - e^{-kn/m})^k$ 对 $k$ 求导并令其等于 0，取得极小值时的 $m$ 与 $n, p$ 的关系。 2. **最优哈希函数个数 $k$**： $$k = \frac{m}{n} \ln 2$$ *来源*：在 $m$ 和 $n$ 确定时，使得误判率最低的 $k$ 值。 3. **当前实际误判率估算 $p_{current}$**： $$p_{current} = \left(1 - e^{-\frac{k \cdot n\_inserted}{m}}\right)^k$$ *来源*：基于当前已插入元素数量 $n\_inserted$ 动态计算的真实误判概率。 4. **当前置位数量估算已插入元素数量 $n_{estimated}$**： $$n_{estimated} = -\frac{m}{k} \ln\left(1 - \frac{X}{m}\right)$$ *来源*：设 $X$ 为位数组中置为 1 的位数，根据期望公式 $X = m(1 - e^{-kn/m})$ 反解得到。 --- ### Python 实现代码 ```python import math import hashlib from typing import Iterable, Union class BloomFilter: """ 可配置的布隆过滤器，基于数学原理自动推导最优参数。 """ def __init__(self, n: int, p: float): """ 初始化布隆过滤器。 :param n: 预期元素数量（正整数） :param p: 期望误判率（0 Iterable[int]: """ 使用双重哈希技术生成 k 个哈希值。 :param item: 待哈希的元素 :return: 生成器，产生 k 个哈希值 """ item_bytes = str(item).encode('utf-8') # 哈希算法选择：SHA-256 # 优点： # 1. 分布极其均匀，雪崩效应极佳，能有效降低哈希碰撞。 # 2. Python 标准库内置，无需安装第三方依赖（如 mmh3），跨平台兼容性好。 # 缺点： # 1. 相比于非加密哈希（如 MurmurHash3, xxHash），SHA-256 计算开销较大。 # 在超大规模、性能极度敏感的场景下，建议替换为 C 语言实现的 MurmurHash3。 hash_hex = hashlib.sha256(item_bytes).hexdigest() # 将 256 位哈希值拆分为两个独立的 64 位整数作为基础哈希 h1 = int(hash_hex[:16], 16) h2 = int(hash_hex[16:32], 16) # 双重哈希模拟 k 个独立哈希函数：hash_i(x) = (h1 + i * h2) % m for i in range(self.k): yield (h1 + i * h2) % self.m def _set_bit(self, index: int) -> None: """将指定位索引置为 1""" byte_idx = index >> 3 # 等价于 index // 8 bit_idx = index & 7 # 等价于 index % 8 mask = 1 bool: """检查指定位索引是否为 1""" byte_idx = index >> 3 bit_idx = index & 7 mask = 1 None: """ 将单个元素添加到布隆过滤器中。 :param item: 待添加的元素（支持字符串、数字等可被 str() 转换的类型） """ for hash_val in self._get_hashes(item): self._set_bit(hash_val) self.n_inserted += 1 def add_batch(self, items: Iterable[Union[str, int, float]]) -> None: """ 批量添加元素。 :param items: 包含待添加元素的可迭代对象 """ for item in items: self.add(item) def contains(self, item:...
AI 评审点评
以下是 AI 评审对该模型输出的点评：
【CLAUDE】该实现整体质量较高，完整覆盖了布隆过滤器的所有要求功能。数学公式推导正确，代码结构清晰，注释详尽，变量命名与数学符号一致（n, m, k, p）。哈希算法选择SHA-256并说明了优缺点，双重哈希实现合理。位数组使用bytearray并配合位运算，内存效率和性能均有考量。边界条件处理完善。主要可改进点：哈希独立性可进一步加强（如使用两种不同哈希算法），参数校验可对数值类型更宽容。总体而言是一个工程质量良好的布隆过滤器实现。 【GEMINI】这是一份优秀的布隆过滤器实现，充分体现了资深算法工程师的专业水平。代码不仅在数学原理上无懈可击，还在工程实践上考虑了内存优化（bytearray）和可扩展性（SHA-256 + Double Hashing）。文档字符串详尽，参数校验健壮，完全符合评测要求。 【KIMI】整体而言，这段代码实现了一个功能完备、性能优秀的布隆过滤器。核心算法和数学公式实现正确，位数组和哈希函数的设计合理。但在输入参数类型检查方面还有改进空间，建议对非字符串类型的数字输入进行更严格的校验。
困难难度评测结果
- 得分：79.6 分
- 通过状态：已通过
模型生成产物
以下是该模型针对此任务的实际生成内容：
作为一名资深算法工程师，我将为你设计并实现一个完整的、工业级的高级布隆过滤器系统。以下是系统的设计说明与完整 Python 实现。 ### 关键设计决策说明 1. **哈希算法选择**： - **默认实现**：选择 `hashlib.sha256` 生成摘要，并切割为两个 64-bit 整数作为基础哈希（$h_1, h_2$）。 - **优缺点**：密码学哈希分布极其均匀，抗碰撞性强，能有效降低误判率；缺点是计算速度略慢于非密码学哈希。在无法引入 C 扩展（如 `mmh3`）的纯 Python 环境中，`hashlib` 是最稳定且无平台差异（防 Hash 碰撞攻击）的选择。 - **双重哈希**：采用 $h_i(x) = (h_1 + i \cdot h_2) \pmod m$。只需计算两次哈希即可模拟 $k$ 次哈希，极大地降低了 CPU 计算开销。 2. **并发锁粒度选择（分段锁）**： - **选择**：在 `ConcurrentBloomFilter` 中采用**分段锁**，默认将位数组划分为 64 个段。 - **理由**：全局锁在高并发下会导致严重的线程阻塞（串行化）。分段锁允许不同线程同时修改不冲突的槽位，显著提高吞吐量。虽然 Python 受限于 GIL 无法实现真正的多核 CPU 密集型并行，但分段锁在 I/O 交替时能最大化线程调度效率，且这是在 Java/C++ 等真并发环境下的标准最佳实践。 3. **数学公式推导**： - 位数组大小 $m$：推导自泊松近似。$m = -\frac{n \ln p}{(\ln 2)^2}$ - 哈希函数个数 $k$：对误判率 $p$ 求导求极值。$k = \frac{m}{n} \ln 2$ --- ### Python 完整实现 ```python import math import hashlib import struct import threading import time from typing import Callable, Optional, List, Dict, Any # ========================================== # 核心基础组件：标准布隆过滤器 # ========================================== class StandardBloomFilter: def __init__(self, expected_items: int, fpp: float, hash_func: Optional[Callable[[bytes], tuple]] = None): if expected_items = 1: raise ValueError("Invalid expected_items or fpp") self.expected_items = expected_items self.fpp = fpp # 数学公式推导： # m = - (n * ln(p)) / (ln(2)^2) self.bit_count = math.ceil(- (expected_items * math.log(fpp)) / (math.log(2) ** 2)) # k = (m / n) * ln(2) self.hash_count = math.ceil((self.bit_count / expected_items) * math.log(2)) # 使用 bytearray 模拟位数组，节约内存 self.byte_array = bytearray(math.ceil(self.bit_count / 8)) self.item_count = 0 self._hash_func = hash_func if hash_func else self._default_hash @staticmethod def _default_hash(item: bytes) -> tuple: """默认哈希函数：SHA256 生成 h1 和 h2""" h = hashlib.sha256(item).digest() h1 = int.from_bytes(h[:8], 'big') h2 = int.from_bytes(h[8:16], 'big') return h1, h2 def _get_hashes(self, item: bytes) -> List[int]: """双重哈希生成 k 个哈希值""" h1, h2 = self._hash_func(item) return [(h1 + i * h2) %...
AI 评审点评
以下是 AI 评审对该模型输出的点评：
【CLAUDE】该实现整体框架完整，覆盖了三个核心组件及通用要求，代码结构清晰，设计说明较为详细。主要问题集中在：1）并发安全实现的分段锁存在根本性缺陷，多哈希位跨段操作未全部加锁；2）计数布隆过滤器的下溢保护逻辑在假阳性场景下仍可能误删；3）可扩展过滤器整体误判率计算公式不准确；4）自定义哈希函数未在所有组件中一致支持；5）intersection的语义局限性说明不完整。总体而言是一个有一定工程价值但存在若干关键正确性问题的实现，适合作为原型参考但不宜直接用于生产环境。 【GEMINI】这是一个非常优秀且接近生产级的实现。模型不仅完成了所有复杂的功能要求（如可扩展过滤器的误判率收紧、计数过滤器的饱和处理），还在工程细节上表现出色，特别是序列化方案的选择和详细的算法设计说明。代码逻辑严密，注释中包含的数学推导增加了可信度，完全符合资深算法工程师的专业定位。 【KIMI】该实现在算法正确性、工程完整性和高级特性逻辑方面表现优秀。双重哈希、计数器处理、误判率控制等关键算法实现严谨，代码结构清晰，模块化程度高。并发控制和性能统计设计合理，有效提升了系统性能和可扩展性。测试覆盖全面，验证了实现的正确性。整体上，这是一个高质量的布隆过滤器系统实现。
相关链接
您可以通过以下链接查看更多相关内容：
