将唯一对象列表与自定义函数进行比较
Comparing list of unique objects with custom function
我需要比较存储在唯一列表中的数百个对象以查找重复项：
object_list = {Object_01, Object_02, Object_03, Object_04, Object_05, ...}
我写了一个自定义函数，returns True，如果对象相等，False，如果不相等：
object_01.compare(object_02)
>>> True
比较方法运行良好，但每次执行需要花费大量时间。我目前正在使用 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'}
...
我想知道：是否有更快的方法遍历所有组合以及如何break/prevent已分配给重复项列表的对象的迭代？
期望输出：
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'}
...
注意：比较方法是一个c-wrapper。要求是找到一个围绕它的算法。
如果要查找按属性分组的复制品，请按名称对对象进行分组
class Foo:
def __init__(self,i,j):
self.i = i
self.j = j
object_list = {Foo(1,2),Foo(3,4),Foo(1,2),Foo(3,4),Foo(5,6)}
from collections import defaultdict
d = defaultdict(list)
for obj in object_list:
d[(obj.i,obj.j)].append(obj)
print(d)
defaultdict(<type 'list'>, {(1, 2): [<__main__.Foo instance at 0x7fa44ee7d098>, <__main__.Foo instance at 0x7fa44ee7d128>],
(5, 6): [<__main__.Foo instance at 0x7fa44ee7d1b8>],
(3, 4): [<__main__.Foo instance at 0x7fa44ee7d0e0>, <__main__.Foo instance at 0x7fa44ee7d170>]})
如果不是名称，则使用元组存储用于检查比较的所有属性。
或者按重要的属性对列表进行排序，然后使用 groupby 进行分组：
class Foo:
def __init__(self,i,j):
self.i = i
self.j = j
object_list = {Foo(1,2),Foo(3,4),Foo(1,2),Foo(3,4),Foo(5,6)}
from itertools import groupby
from operator import attrgetter
groups = [list(v) for k,v in groupby(sorted(object_list, key=attrgetter("i","j")),key=attrgetter("i","j"))]
print(groups)
[[<__main__.Foo instance at 0x7f794a944d40>, <__main__.Foo instance at 0x7f794a944dd0>], [<__main__.Foo instance at 0x7f794a944d88>, <__main__.Foo instance at 0x7f794a944e18>], [<__main__.Foo instance at 0x7f794a944e60>]]
您还可以实现 lt、eq 和 hash 以使您的对象可排序和可哈希：
class Foo(object):
def __init__(self,i,j):
self.i = i
self.j = j
def __lt__(self, other):
return (self.i, self.j) < (other.i, other.j)
def __hash__(self):
return hash((self.i,self.j))
def __eq__(self, other):
return (self.i, self.j) == (other.i, other.j)
print(set(object_list))
object_list.sort()
print(map(lambda x: (getattr(x,"i"),getattr(x,"j")),object_list))
set([<__main__.Foo object at 0x7fdff2fc08d0>, <__main__.Foo object at 0x7fdff2fc09d0>, <__main__.Foo object at 0x7fdff2fc0810>])
[(1, 2), (1, 2), (3, 4), (3, 4), (5, 6)]
显然，属性需要是可散列的，如果你有列表，你可以更改为元组等。
您不需要计算所有组合，您只需要检查给定的项目是否重复：
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] returns 列表中索引 i 之前的所有项目。如果项目 x[i] 出现在该列表中，您就知道它是重复项。如果没有，列表中之后可能有一个重复的，但是当你到达那里时你会担心。
这里使用 any 也很重要：如果找到任何 true 项目，它将立即停止，而不检查 iterable 的其余部分。
您还可以通过从您正在检查的列表中删除已知重复项来提高检查次数：
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 的条目即可。
我需要比较存储在唯一列表中的数百个对象以查找重复项：
object_list = {Object_01, Object_02, Object_03, Object_04, Object_05, ...}
我写了一个自定义函数，returns True，如果对象相等，False，如果不相等：
object_01.compare(object_02)
>>> True
比较方法运行良好，但每次执行需要花费大量时间。我目前正在使用 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'}
...
我想知道：是否有更快的方法遍历所有组合以及如何break/prevent已分配给重复项列表的对象的迭代？
期望输出：
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'}
...
注意：比较方法是一个c-wrapper。要求是找到一个围绕它的算法。
如果要查找按属性分组的复制品，请按名称对对象进行分组
class Foo:
def __init__(self,i,j):
self.i = i
self.j = j
object_list = {Foo(1,2),Foo(3,4),Foo(1,2),Foo(3,4),Foo(5,6)}
from collections import defaultdict
d = defaultdict(list)
for obj in object_list:
d[(obj.i,obj.j)].append(obj)
print(d)
defaultdict(<type 'list'>, {(1, 2): [<__main__.Foo instance at 0x7fa44ee7d098>, <__main__.Foo instance at 0x7fa44ee7d128>],
(5, 6): [<__main__.Foo instance at 0x7fa44ee7d1b8>],
(3, 4): [<__main__.Foo instance at 0x7fa44ee7d0e0>, <__main__.Foo instance at 0x7fa44ee7d170>]})
如果不是名称，则使用元组存储用于检查比较的所有属性。
或者按重要的属性对列表进行排序，然后使用 groupby 进行分组：
class Foo:
def __init__(self,i,j):
self.i = i
self.j = j
object_list = {Foo(1,2),Foo(3,4),Foo(1,2),Foo(3,4),Foo(5,6)}
from itertools import groupby
from operator import attrgetter
groups = [list(v) for k,v in groupby(sorted(object_list, key=attrgetter("i","j")),key=attrgetter("i","j"))]
print(groups)
[[<__main__.Foo instance at 0x7f794a944d40>, <__main__.Foo instance at 0x7f794a944dd0>], [<__main__.Foo instance at 0x7f794a944d88>, <__main__.Foo instance at 0x7f794a944e18>], [<__main__.Foo instance at 0x7f794a944e60>]]
您还可以实现 lt、eq 和 hash 以使您的对象可排序和可哈希：
class Foo(object):
def __init__(self,i,j):
self.i = i
self.j = j
def __lt__(self, other):
return (self.i, self.j) < (other.i, other.j)
def __hash__(self):
return hash((self.i,self.j))
def __eq__(self, other):
return (self.i, self.j) == (other.i, other.j)
print(set(object_list))
object_list.sort()
print(map(lambda x: (getattr(x,"i"),getattr(x,"j")),object_list))
set([<__main__.Foo object at 0x7fdff2fc08d0>, <__main__.Foo object at 0x7fdff2fc09d0>, <__main__.Foo object at 0x7fdff2fc0810>])
[(1, 2), (1, 2), (3, 4), (3, 4), (5, 6)]
显然，属性需要是可散列的，如果你有列表，你可以更改为元组等。
您不需要计算所有组合，您只需要检查给定的项目是否重复：
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] returns 列表中索引 i 之前的所有项目。如果项目 x[i] 出现在该列表中，您就知道它是重复项。如果没有，列表中之后可能有一个重复的，但是当你到达那里时你会担心。
这里使用 any 也很重要：如果找到任何 true 项目，它将立即停止，而不检查 iterable 的其余部分。
您还可以通过从您正在检查的列表中删除已知重复项来提高检查次数：
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 的条目即可。