首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >改进该算法的时间复杂度

改进该算法的时间复杂度
EN

Stack Overflow用户
提问于 2020-04-26 16:11:20
回答 1查看 121关注 0票数 2

我有N对字符串列表(从集合1到N,从集合2),它们需要通过Jaccard相似度与最近的字符串列表配对。这意味着我需要计算N^2距离,并为集合1中的每个元素取最大相似性w.r.t。第二组。

运行它的简单代码是

代码语言:javascript
复制
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)的时间复杂度,但我想知道是否会有一些优化/启发式,以便平均情况会更好。

类似地,有什么关于代码本身的东西我可以优化吗?

编辑:我修改了这个问题,使它更加精确。

EN

Stack Overflow用户

回答已采纳

发布于 2020-04-26 16:18:44

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

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

票数 2
EN
查看全部 1 条回答
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61443990

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档