У меня есть N пар списков строк (N от набора 1 до N из набора 2), которые должны быть соединены с ближайшим из-за сходства с Жакаром. Это означает, что мне нужно вычислить 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)
I Я знаю, что это имеет O (N ^ 2) временную сложность, но мне было интересно, может ли быть некоторая оптимизация / heuristi c, чтобы средний случай был лучше.
Аналогично, есть ли что-то, касающееся самого кода, которое я мог бы оптимизировать?
РЕДАКТИРОВАТЬ: я изменил вопрос, чтобы сделать его более точным.