我喜欢开发一个查询系统,它可以根据从数据中提取的二进制签名找到与给定项目最相似的项目。因为我有运行时限制,所以我探索了最有效的方法。我尝试使用 scipy distance 但它太慢了。你知道任何其他有用的库或技巧来更快地制作它吗?
对于存在和示例场景,
我有一个二进制值长度为 68 的查询向量,我有一个矩阵大小为 3000Kx68 的数据集。我喜欢使用汉明距离在此矩阵中找到与给定查询最相似的项目。
谢谢你的评论
请您参考如下方法:
好问题,我喜欢 Alex 和 Piotr 的回答。我的第一次幼稚尝试也导致解决方案时间约为 800 毫秒(在我的系统上)。我的第二次尝试使用 numpy 的 (un)packbits,导致速度提高了 4 倍。
import numpy as np
LENGTH = 68
K = 1024
DATASIZE = 3000 * K
DATA = np.random.randint(0, 2, (DATASIZE, LENGTH)).astype(np.bool)
def RandomVect():
return np.random.randint(0, 2, (LENGTH)).astype(np.bool)
def HammingDist(vec1, vec2):
return np.sum(np.logical_xor(vec1, vec2))
def SmallestHamming(vec):
XorData = np.logical_xor(DATA, vec[np.newaxis, :])
Lengths = np.sum(XorData, axis=1)
return DATA[np.argmin(Lengths)] # returns first smallest
def main():
v1 = RandomVect()
v2 = SmallestHamming(v1)
print(HammingDist(v1, v2))
# oke, lets try make it faster... (using numpy.(un)packbits)
DATA2 = np.packbits(DATA, axis=1)
NBYTES = DATA2.shape[-1]
BYTE2ONES = np.zeros((256), dtype=np.uint8)
for i in range(0,256):
BYTE2ONES[i] = np.sum(np.unpackbits(np.uint8(i)))
def RandomVect2():
return np.packbits(RandomVect())
def HammingDist2(vec1, vec2):
v1 = np.unpackbits(vec1)
v2 = np.unpackbits(vec2)
return np.sum(np.logical_xor(v1, v2))
def SmallestHamming2(vec):
XorData = DATA2 ^ vec[np.newaxis, :]
Lengths = np.sum(BYTE2ONES[XorData], axis=1)
return DATA2[np.argmin(Lengths)] # returns first smallest
def main2():
v1 = RandomVect2()
v2 = SmallestHamming2(v1)
print(HammingDist2(v1, v2))
