1

我有两个列表l1并l2包含可能具有不同长度的整数，我想在这两个向量之间的每个可能配对之间执行计算。

具体来说，我正在检查每对之间的汉明距离，如果距离足够小，我想“计算”它。

天真地，这可以实现

def hamming_distance(n1: int, n2: int) -> float:
    return bin(n1 ^ n2).count('1')/32.0

matches = 0

for n1 in l1:
    for n2 in l2:
        sim = 1 - hamming_distance(n1, n2)

        if sim >= threshold:
            matches += 1

但这不是很快。

我没有成功尝试利用scipy.spatial.distance.cdist，我认为我将首先计算所有对之间的汉明距离，因为scipy.spatial.cdist 文档指出它将

计算两个输入集合中每对之间的距离。

然后计算满足谓词的元素个数，即汉明距离1 - d >= threshold在哪里d，即

from scipy.spatial.distance import cdist

l1 = l1.reshape(-1, 2)  # After np.array
l2 = l2.reshape(-1, 2)
r = cdist(l1, l2, 'hamming')
matches = np.count_nonzero(1 - r >= threshold)

但是各个解决方案找到的匹配数不同。我注意到可以cdist使用函数进行调用，cdist(XA, XB, f)但是我没有成功编写我的实现hamming_distance以使其正确广播。

我已经查看了这个问题/答案，但它假定两个列表的长度相同，这不是这里的情况。

4

2 回答 2

1

您可以与和np.bitwise_xor.outer一起使用：np.binary_reprnp.char.count

import numpy as np

a = np.random.randint(0, 10, size=5)
b = np.random.randint(0, 10, size=5)

binary_repr = np.vectorize(np.binary_repr)
distance = np.char.count(binary_repr(np.bitwise_xor.outer(a, b)), '1') / 32

然后得到匹配：

matches = np.sum(distance >= threshold)
于 2019-09-25T08:09:28.207 回答
1

以下是使用的三种方法

  1. scipy.spatial.KDTree
  2. scipy.spatial.distance.cdist
  3. 查找表

在一对长度为 100 和 200 的 32 位 int 向量上，它们都给出相同的结果；他们的快速比较如下：

count_sim_kd 16.408800622448325 ms
count_sim_cd 12.41896384395659 ms
count_sim_lu 0.8755046688020229 ms

因此，在这个问题大小上，查找以巨大的优势获胜。

代码：

import numpy as np
from scipy.spatial import cKDTree as KDTree
from scipy.spatial.distance import cdist

l1 = np.random.randint(0,2**32,100)
l2 = np.random.randint(0,2**32,200)
threshold = 10/32

def hamming_distance(n1: int, n2: int) -> float:
    return bin(n1 ^ n2).count('1')/32.0

matches = 0

for n1 in l1:
    for n2 in l2:
        sim = 1 - hamming_distance(n1, n2)

        if sim >= threshold:
            matches += 1

def count_sim_kd(a,b,th):
    A,B = (KDTree(np.unpackbits(x[:,None].view(np.uint8),axis=1))
           for x in (a,b))
    return A.sparse_distance_matrix(B,max_distance=32-int(32*th),p=1).nnz

def count_sim_cd(a,b,th):
    A,B = (np.unpackbits(x[:,None].view(np.uint8),axis=1) for x in (a,b))
    return np.count_nonzero(cdist(A,B,"minkowski",p=1)<=32-int(32*th))


lu = sum(np.unravel_index(np.arange(256),8*(2,)))
def count_sim_lu(a,b,th):
    return np.count_nonzero(lu[(a[:,None,None]^b[None,:,None])
                               .view(np.uint8)].sum(2)<=32-int(32*th))

from timeit import timeit
for f in (count_sim_kd,count_sim_cd,count_sim_lu):
    assert f(l1,l2,threshold)==matches
    print(f.__name__,timeit(lambda:f(l1,l2,threshold),number=100)*10,'ms')
于 2019-09-25T12:09:29.643 回答