比较具有自定义功能的唯一对象列表 - python

我需要比较存储在唯一列表中的数百个对象以查找重复项:

object_list = {Object_01, Object_02, Object_03, Object_04, Object_05, ...}

我编写了一个自定义函数，如果对象相等，则返回True，否则返回False:

object_01.compare(object_02)
>>> True

比较方法效果很好，但是每次执行花费大量时间。我目前正在使用itertools.combinations(x, 2)遍历所有组合。我认为使用dict来存储已比较的对象并动态创建新集是一个好主意，例如:

dct = {'Compared': {}}
dct['Compared'] = set()

import itertools
for a, b in itertools.combinations(x, 2):

    if b.name not in dct['Compared']:

        if compare(a,b) == True:

            #print (a,b)
            key = a.name
            value = b.name

            if key not in dct:
                dct[key] = set()
                dct[key].add(value)
            else:
                dct[key].add(value)

            dct[key].add(key)

    dct['Compared'].add(b)

电流输出:

Compared: {'Object_02', 'Object_01', 'Object_03', 'Object_04', 'Object_05'}
Object_01: {'Object_02', 'Object_03', 'Object_01'}
Object_04: {'Object_05', 'Object_04'}
Object_05: {'Object_04'}
...

我想知道:是否有一种更快的方法来遍历所有组合，以及如何中断/阻止已分配给重复项列表的对象的迭代？

所需输出:

Compared: {'Object_02', 'Object_01', 'Object_03', 'Object_04', 'Object_05'}
Object_01: {'Object_02', 'Object_03', 'Object_01'}
Object_04: {'Object_05', 'Object_04'}
...

注意:compare方法是一个c-wrapper。要求是找到一种算法。

python大神给出的解决方案

您不需要计算所有组合，只需要检查给定项目是否重复:

for i, a in enumerate(x):
    if any(a.compare(b) for b in x[:i]):
        # a is a duplicate of an already seen item, so do something

从技术上讲，这仍然是O(n ^ 2)，但是您至少已经削减了所需检查的一半，并且应该更快一些。

简而言之，x[:i]返回索引i之前列表中的所有项目。如果项目x[i]出现在该列表中，则说明它是重复项。如果不是，列表中的后面可能会有重复项，但是到达那里时您会担心。

在这里使用any也很重要:如果找到任何真实的项目，它将立即停止，而无需检查其余的可迭代对象。

您还可以通过从要检查的列表中删除已知重复项来提高检查数量:

x_copy = x[:]
removed = 0
for i, a in enumerate(x):
    if any(a.compare(b) for b in x_copy[:i-removed]):
        del x_copy[i-removed]
        removed += 1
        # a is a duplicate of an already seen item, so do something

请注意，我们使用一个副本，以避免更改要迭代的序列，并且在使用索引时，我们需要考虑已删除的项目数。

接下来，我们只需要弄清楚如何构建字典。

这可能要复杂一些。第一步是准确找出哪个元素是重复项。这可以通过实现any只是for循环的包装器来完成:

def any(iterable):
    for item in iterable:
        if item: return True
    return False    

然后，我们可以进行较小的更改，并传入一个函数:

def first(iterable, fn):
    for item in iterable:
        if fn(item): return item     
    return None

现在，我们如下更改重复查找程序:

d = collections.defaultdict(list)

x_copy = x[:]
removed = 0
for i, a in enumerate(x):
    b = first(x_copy[:i-removed], a.compare):
    if b is not None:
        # b is the first occurring duplicate of a
        del x_copy[i-removed]
        removed += 1

        d[b.name].append(a)

     else:
         # we've not seen a yet, but might see it later
         d[a.name].append(a)

这会将列表中的每个元素放入dict(-like)。如果您只想要重复项，那么这只是获得长度大于1的所有条目的一种情况。