提高该算法的时间复杂度

Question

我有 N 对字符串列表（第 1 组中的 N 到第 2 组中的 N）需要通过 Jaccard 相似度与最接近的列表配对。这意味着我需要计算 N^2 距离并为集合 1 中的每个元素取最大相似度 w.r.t。设置 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) 的时间复杂度，但我想知道是否可能有一些 optimization/heuristic 这样平均情况会更好。

同样，代码本身有什么我可以优化的吗？

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

Answer 1

您应该能够使用 scipy.spatial.distance.cdist，它计算给定指标的整个矩阵。时间复杂度是不可避免的，但是scipy让它变得很快。

https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html

提高该算法的时间复杂度

Improve time complexity of this algorithm

python

time-complexity

cosine-similarity