提高该算法的时间复杂度

Question

我有 N 对字符串列表（N 从集合 1 到 N 从集合 2）需要通过 Jaccard 相似度与最接近的字符串列表配对。这意味着我需要计算 N^2 距离，并为集合 1 中的每个元素取集合 2 的最大相似度。

运行它的简单代码是

import numpy as np

def jaccard_similarity(a, b):

    intersection = set(a).intersection(set(b))

    union = set(a).union(set(b))

    return len(intersection)/len(union)

set_1 = [['Pisa','Tower','River','Tuscany'],['London','City','UK','England'],['Berlin','Germany','Munich']]

set_2 = [['Pisa','Arno','River','Tuscany','Florence','London','Tower'],['Germany','German','UBanh'],['London','City','UK','England','Europe']]

pairs = []

for vect_1 in set_1:

    dist = []

    for vect_2 in set_2:

        dist.append(jaccard_similarity(vect_1,vect_2))

    pairs.append(np.argmax(dist))

print(pairs)

我知道这有 O(N^2) 时间复杂度，但我想知道是否可能有一些优化/启发式，以便平均情况会更好。

同样，我可以优化代码本身吗？

编辑：我修改了问题以使其更精确。

Answer 1

您应该能够使用 scipy.spatial.distance.cdist，它计算给定度量的整个矩阵。时间复杂度是不可避免的，但 scipy 让它很快。https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html