python - 是否有一些通用的数据结构来比较对象列表并在其中找到最相等的？

Question

我将使用 Python 来展示一个代码(因为这个解决方案是为 Python 编写的代码)但是这个问题是独立于语言的。

假设我有 2 个对象列表。我不能使用对象 ID 作为这些对象的主键。

一个对象可能看起来像(真实的对象要复杂得多并且具有嵌套结构):

class A():
    def __init__(self, prop1, prop2, prop3):
        self.prop1 = prop1
        self.prop2 = prop2
        self.prop3 = prop3

列表看起来像:

list1 = [A(1, 2, 3), A(4, 5, 6), A(7, 8, 9)]
list2 = [A(1, 10, 11), A(4, 5, 6), A(1, 4, 9), A(10, 11, 12)]

在比较对象时，我使用相等属性的数量作为分数。

例如:

A(1, 2, 3) == A(1, 10, 11) gives 1, because only 1 == 1
A(4, 5, 6) == A(4, 5, 6) gives 3, because 4 == 4, 5 == 5, 6 == 6
A(7, 8, 9) == A(10, 11, 12) gives 0, because there are no equal items

在将 list1 中的所有对象与 list2 中的每个对象进行比较后，我得到了一个我称之为相似矩阵的东西，它看起来像这样:

[
    [1, 0, 1, 0],
    [0, 3, 0, 0],
    [0, 0, 1, 0],
]

之后我从列表中取出最大元素，即3，删除该数字所属的行和列(行=1，列=1)，按位置从中删除那些对象>list1、list2 并重复，直到相似度矩阵中没有任何项目大于阈值(在当前示例中为零)。

第一步后的相似度矩阵:

[
    [1, 1, 0],
    [0, 1, 0],
]

第一步后的列表:

list1 = [A(1, 2, 3), A(7, 8, 9)]
list2 = [A(1, 10, 11), A(1, 4, 9), A(10, 11, 12)]

通过这些操作，我将通过从列表中按位置弹出它们以及我标记为不相等的列表中剩余的所有对象来获得最相等的对象。

我想知道我是否重新发明了一个轮子，并且有一些数据结构可以帮助解决这个问题？您是否看到任何明显的改进可以加快当前解决方案的速度？

Answer 1

目前我能想到的两种方式是:

• 使用字典和集合，或者

• 具有 sim_level 方法的对象。

字典和集合

list1 = [
    {'x': 1, 'y': 2, 'z': 3},
    {'x': 7, 'y': 8, 'z': 9}
]

list2 = [
    {'x': 1, 'y': 10, 'z': 11},
    {'x': 1, 'y': 4, 'z': 9},
    {'x': 10, 'y': 11, 'z': 12},
]

def sim_level(a, b):
    # this creates set of pairs e.g. ('prop1', 2)
    sa = set(a.items())  
    sb = set(b.items())

    # here you intersect them and count number of intersecting elements
    return len(sa.intersection(sb)) 

然后就是遍历这些列表的乘积并计算权重，然后从两个列表中删除具有最大相似度的对象。

对象

这将包括拥有与您已经使用的对象相似的对象，但有额外的方法 sim_level 将与同一类的另一个实例进行比较。

class A():

    def __init__(self, prop1, prop2, prop3):
        self.prop1 = prop1
        self.prop2 = prop2
        self.prop3 = prop3

    def sim_level(self, other):
        s = 0
        if self.prop1 == other.prop1: s += 1
        if self.prop2 == other.prop2: s += 1
        if self.prop3 == other.prop3: s += 1
        return s

然后你继续，就好像你会使用字典建议一样。