通过从另一个列表(python)中执行查找来替换元组列表中的元素的有效方法

Question

我有一个元组列表，如下所示：

tuple_list = [(id-1,value-1),(id-2,value-2),....(id-n,value-n)]

同样，我有一个与上面列表中的ids相关的对象列表，即：

object_list = [<obj-3>,<obj-1>,....<obj-n>]

注意，object_list中的顺序是不同的。

我想要生成一个与上面的第一个列表完全一样的新列表，除了id之外，它应该有它自己的对象。

resulting_list = [(<obj-1>,value-1),(<obj-2>,value-2),...(<obj-n>,value-n)]

最有效的方法是什么？

目前，我正在两个循环中尝试：

resulting_list = []
for tpl in tuple_list:
    for obj in object_list:
        if tpl[0] == obj.id
        resulting_list.append((obj,tpl[1]))

Answer 1

构造一个dict，其中键是对象ids，值是对象。然后在列表理解范围内迭代tuple_list，并对来自dict的每个元组输出对象和原始列表中的值进行迭代：

class Obj:
    def __init__(self, id):
        self.id = id

    def __repr__(self):
        return 'Obj({})'.format(self.id)

tuple_list = [(0, 'Zero'), (1, 'One'), (2, 'Two'), (3, 'Three'), (4, 'Four')]
object_list = [Obj(i) for i in range(4, -1, -1)]

d = {o.id: o for o in object_list}
result = [(d[_id], val) for _id, val in tuple_list]

print(result)

输出：

[(Obj(0), 'Zero'), (Obj(1), 'One'), (Obj(2), 'Two'), (Obj(3), 'Three'), (Obj(4), 'Four')]

上面的时间复杂度是O(n)，其中嵌套循环的原始代码是O(n^2)。

Answer 2

如果列表的长度为n，那么当前的算法在外部循环上执行n迭代，在每个内循环上执行n迭代，从而得到总计的n*n。一旦找到匹配项，您就可以通过打破内环来改进这一点。这将给出n*n/2的平均值。

但是最好每个循环都是长度n，因为对于大型n，2n要比n*n小得多。在下面的代码中，第一个循环构造一个字典，其中对象id作为键，对象本身作为值。然后，第二个循环可以快速地从其id中找到对象。

obj_map = {obj.id: obj for obj in object_list}
resulting_list = [(obj_map[k], v) for k, v in tuple_list]

如果tuple_list中的某些ids在obj_map中没有匹配的对象，并且您不希望在这种情况下使用KeyError失败，则可以这样做

resulting_list = [(obj_map.get(k), v) for k, v in tuple_list]

它将为任何丢失的对象提供None。

或者，

resulting_list = [(obj_map.get(k, default_object), v) for k, v in tuple_list]

它将为缺少的对象提供default_object。

Answer 3

...
    i = object_list.index(tpl[0]) if tpl[0] in tuple_list else -1
    if i > -1:
      resulting_list.append((object_list[i],tpl[1]))