提高该算法的时间复杂度

Question

我有 N 对字符串列表（N 从集合 1 到 N 从集合 2）需要通过 Jaccard 相似度与最接近的字符串列表配对。这意味着我需要计算 N^2 距离，并为集合 1 中的每个元素取集合 2 的最大相似度。运行它的简单代码是import numpy as npdef 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