我需要比较存储在唯一列表中的数百个对象以查找重复项:
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 包装器。要求是找到一个围绕它的算法。
最佳答案
您不需要计算所有组合,只需检查给定项目是否重复:
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 的条目即可。
关于python - 将唯一对象列表与自定义函数进行比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30310542/