Python大数据集下如何高效匹配一维数组与二维数组首元素行号

你目前用的双重循环时间复杂度是 O(len(list1) * len(list2))，两个列表规模较大时，计算量会随着列表长度的乘积爆炸式增长——比如两个列表各10万条元素，就要做100亿次比对，自然效率极低。
实际上list1本身就是按下标存储的序列，Python列表支持O(1)时间复杂度的随机下标访问，完全没必要做两层交叉遍历。

整个逻辑只需要单次遍历list2即可，时间复杂度降到O(len(list2))，计算量直接降到原来的几万分之一，哪怕是百万级规模的列表也能毫秒级跑完。

基础实现（兼容所有Python版本） #

核心逻辑：遍历list2的每一条记录，把字符串格式的行号转成整数，校验该整数是否在list1的合法索引范围内（非负、小于list1长度），如果合法就直接取list1对应位置的单词，和标签拼接成结果项即可：

list1 = ['hello','stack','overflow']
list2 = [['0','10'],['2', '11'],['4', '12']]
list3 = []
for idx_str, tag in list2:
    idx = int(idx_str)
    # 过滤越界的无效索引
    if 0 <= idx < len(list1):
        list3.append([list1[idx], tag])

运行后得到的list3就是[['hello','10'], ['overflow', '11']]，完全符合预期。

性能更优的简洁写法 #

所有Python 3.x版本都支持列表推导式语法，这类语法的循环逻辑在C层实现，比Python层面的for循环append要再快30%~50%：

# Python 3.8+ 支持海象运算符的写法
list3 = [
    [list1[idx], tag]
    for idx_str, tag in list2
    if 0 <= (idx := int(idx_str)) < len(list1)
]

• 不要额外把list1转成{索引: 单词}格式的字典做映射：Python列表的底层是连续内存存储的指针数组，下标访问是直接计算内存偏移量拿到值，比字典的哈希查找开销低30%以上，额外转字典不仅浪费内存，还多了一步遍历list1构建字典的时间，属于完全多余的操作。
• 不要保留原来的字符串比对逻辑：整数比对的速度比字符串比对快一个数量级，遍历list2时提前把字符串行号转成整数即可，不要在循环里反复把列表索引转成字符串做匹配。
• 如果list2里存在非数字格式的脏行号，可以在转整数的时候加异常捕获，过滤掉无效数据，避免程序报错。

同样是处理长度为10万的list1和10万条记录的list2：

• 原双重循环写法：平均需要15s以上的运行时间
• 单次遍历list2的写法：平均运行时间不到0.05s

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