当比较两大组数据时,复杂性是否可以从O(n^2)降低到O(n)?

2024-03-29 07:53:37 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个大的项目集(~200万),其中我需要将每个项目与此集中的每个其他项目进行比较

每个项本身是一组串接到单个字符串的字符串。因此,将使用difflib将字符串a与所有其他字符串b进行比较

从长远来看,我希望切换到不同于difflib的库,但即使是100倍的加速也不够快。这些项不存储在数据库中,而是直接存储在内存中。我使用两个for循环,这显然不是一个令人满意的解决方案

代码如下所示:

for a in data:
    for b in data:
        # calculate similarity of a and b

是否有更好的方法分别比较所有项目


Tags: andof项目方法内存字符串代码in
1条回答
网友
1楼 · 发布于 2024-03-29 07:53:37

假设ab的长度相同,我们可以迭代它们的长度:

#if length not equal then items not equal and we can save time.
if len(a) != len(b):
   return False 

for i in range(len(a)):
    if a[i] != b[i]:
        return False

return True

编辑:

我看错了,所以我原来的答案是无效的

您可以为每个项目创建两个bucket,一个用于相似的项目,另一个用于不同的项目,从而改进运行时

通过在任何比较之前执行此操作,您可以添加两个检查,即a类似于b类似的项还是类似于b不同的项

假设ab的长度足够长,并且它们在数据库中是足够相似的项(如果所有项都不同,那么这种方法就没有意义),那么这应该会提高性能

简单PUESDO示例:

similar_buckets = {}
different_buckets = {}

def func():
    for string in data:
        if string not in similar_buckets:
            similar_buckets[string] = set()
        if string not in different_buckets:
            different_buckets[string] = set()

        for string2 in data:
            # these occur in O(1)
            if string2 in similar_buckets[string]:
                continue #true
            elif string2 in different_buckets[string]:
                continue #false

            #expensive
            if string == string2:
                similar_buckets[string].add(string2)
                different_buckets[string2] = similar_buckets[string]
                continue
            else:
                different_buckets[string].add(string2)
                similar_buckets[string2] = different_buckets[string]
                continue

func()

请注意,这仍然是O(n^2),但我们有可能大幅提高实际性能

相关问题 更多 >