我有一个大的项目集(~200万),其中我需要将每个项目与此集中的每个其他项目进行比较
每个项本身是一组串接到单个字符串的字符串。因此,将使用difflib将字符串a
与所有其他字符串b
进行比较
从长远来看,我希望切换到不同于difflib的库,但即使是100倍的加速也不够快。这些项不存储在数据库中,而是直接存储在内存中。我使用两个for循环,这显然不是一个令人满意的解决方案
代码如下所示:
for a in data:
for b in data:
# calculate similarity of a and b
是否有更好的方法分别比较所有项目
Tags:
假设
a
和b
的长度相同,我们可以迭代它们的长度:编辑:
我看错了,所以我原来的答案是无效的
您可以为每个项目创建两个bucket,一个用于相似的项目,另一个用于不同的项目,从而改进运行时
通过在任何比较之前执行此操作,您可以添加两个检查,即
a
类似于b
类似的项还是类似于b
不同的项假设
a
和b
的长度足够长,并且它们在数据库中是足够相似的项(如果所有项都不同,那么这种方法就没有意义),那么这应该会提高性能简单PUESDO示例:
请注意,这仍然是O(n^2),但我们有可能大幅提高实际性能
相关问题 更多 >
编程相关推荐