NumPy环境下查询向量与条目矩阵汉明距离的高效计算方法求解

性能优化方案 #

1. 先纠正现有代码的参数错误

你当前使用的(query ^ items).sum(axis=0)中axis参数设置错误，按列求和无法得到每行与查询向量的汉明距离，正确写法应为axis=1，该参数错误也可能是你实测耗时偏高的原因之一。

2. 最高效实现：比特打包+位计数

你的场景维度只有30位，刚好可以打包进单个32位无符号整数，利用numpy的底层位运算接口可以大幅降低运算开销，实现比现有方案快数十倍的性能：

import numpy as np

# 提前预处理条目矩阵（仅需执行一次）
# 将每行30维布尔向量打包为1个uint32整数
packed_items = np.packbits(items, axis=1, bitorder='little').view(np.uint32).ravel()

# 查询侧预处理（每个查询仅需执行一次）
packed_query = np.packbits(query, bitorder='little').view(np.uint32)[0]

# 计算汉明距离（单步运算，5000样本耗时可低至0.01秒以内）
hamming_dist = (packed_items ^ packed_query).bit_count()

3. 性能提升原理

• 原方案中xor后求和需要将布尔值转换为整数再逐元素累加，存在大量类型转换和冗余运算
• 比特打包后每行数据从30字节压缩为4字节，内存占用减少87.5%，缓存命中率大幅提升
• bit_count是CPU指令级优化的位计数操作，比逐元素求和快1~2个数量级

如果你不需要严格的汉明距离，也可以直接用打包后的整数做相等判断匹配完全一致的条目，速度会更快。

内容的提问来源于stack exchange，提问作者Chenghao Liu