如何优化双列表匹配索引对应值相乘的执行性能？

问题背景 #

我创建了两个列表a和b，列表a长度为24480，列表b长度为20116。两个列表的每个元素都是长度为3的子列表，结构如下：

# 子列表结构示例
a_item = [str1a, str2a, float1a]
b_item = [str1b, str2b, float1b]

需求：当子列表的str1a == str1b且str2a == str2b时，将a中对应子列表的float1a更新为float1a * float1b。注意列表b存在重复元素，且a中并非所有元素都能找到匹配项。

当前使用嵌套循环实现，但效率较低，代码如下：

for i in range(0, len(a)):
    for n in range(0, len(b)):
        if a[i][0] == b[n][0] and a[i][1] == b[n][1]:
            a[i][2] *= b[n][2]

优化方案 #

嵌套循环的时间复杂度为O(M*N)，对于数万条数据来说效率极低。我们可以利用Python原生字典的O(1)查找特性，将时间复杂度降至O(M+N)，具体步骤如下：

1. 预处理列表b，合并相同键的乘积 #

由于b中存在重复的(str1b, str2b)组合，我们先将这些组合对应的float1b相乘，存入字典中，确保每个键只对应一个最终乘积值：

# 构建b的乘积字典
b_product_dict = {}
for s1, s2, val in b:
    key = (s1, s2)
    if key in b_product_dict:
        b_product_dict[key] *= val
    else:
        b_product_dict[key] = val

2. 遍历列表a完成更新 #

遍历a中的每个元素，用(str1a, str2a)作为键去字典中查找，找到匹配项则更新float1a：

# 更新a中的对应元素
for item in a:
    key = (item[0], item[1])
    if key in b_product_dict:
        item[2] *= b_product_dict[key]

方案优势 #

• 时间效率大幅提升：从原来的二次方复杂度降至线性复杂度，处理数万条数据时速度差距会非常明显
• 完全使用Python原生语法，无需导入任何外部模块
• 逻辑和原嵌套循环完全一致：合并乘积的操作等价于原循环中多次匹配相乘的效果（乘法结合律）

内容的提问来源于stack exchange，提问作者joetjen