python - 将唯一对象列表与自定义函数进行比较

Question

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

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

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

object_01.compare(object_02)
>>> True

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

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 包装器。要求是找到一个围绕它的算法。

Answer 1

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

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)

这会将列表中的每个元素放入一个字典(类似)中。如果您只想要重复项，那么只需获取所有长度大于 1 的条目即可。