Python中高效对比大型非对称二维列表的方法

• IndexError 原因：原代码循环次数取的是list1的长度，但list2比list1短，当循环索引超过list2的最大索引时，访问list2[i]就会触发索引越界。
• 运行极慢原因：如果改成逐个比对两个列表的ID，时间复杂度是O(n*m)（n为list1长度，m为list2长度），面对4GB+的超大数据集，这种暴力匹配完全无法高效完成。

核心是把list2转换成字典（哈希表），利用字典O(1)的查找效率，把整体时间复杂度降到O(n)。

1. 把list2转成字典（省内存+快查找） #

不用先把list2存成二维列表，解析的时候直接构建ID到sequence的映射：

# 解析list2时直接生成字典，无需先存列表
list2_dict = {}
for record in file_parse_list2:
    id, seq = record
    list2_dict[id] = seq

如果已经有现成的list2二维列表，也可以快速转成字典：

list2_dict = {item[0]: item[1] for item in list2}

2. 快速生成对比结果 #

遍历list1的每个元素，用字典直接查找匹配的sequence，找不到就填-1：

list1_2_comparison = []
for item in list1:
    current_id = item[0]
    # get方法：找到对应sequence就返回，找不到返回默认值-1
    list1_2_comparison.append(list2_dict.get(current_id, -1))

额外优化：内存友好的处理方式 #

如果4GB+的文件解析成列表后内存吃紧，可以边解析list1边生成结果，不用把整个list1存进内存：

list1_2_comparison = []
# 直接遍历解析器，不提前存list1
for record in file_parse_list1:
    current_id, _ = record
    list1_2_comparison.append(list2_dict.get(current_id, -1))

• 字典查找是**O(1)**平均时间复杂度，整体流程时间复杂度为O(n+m)，比原暴力匹配快几个数量级，超大数据集也能快速处理。
• 彻底避免索引越界问题，因为不再依赖两个列表的索引位置对应，完全基于ID匹配。

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