计算两个不同列表元素间高复杂度函数的最快实现方案

核心优化逻辑 #

你的原始代码最大的性能损耗来自大量重复计算：样例中list1元素范围是1_{100，list2元素范围是1}10，两者相加的可能取值最多只有110种，原始100万次循环中绝大多数都是重复计算相同值的阶乘，属于完全可避免的性能浪费。
该优化逻辑完全适配你实际使用的dynamo交集检查场景：先计算所有唯一输入组合的结果存为映射表，后续全量组合直接查表取值即可，不需要重复执行高复杂度函数。

优化后代码 #

%%time
import random
import itertools
import math
random.seed(10)

list1 = [random.randint(1, 100) for i in range(10000)]
list2 = [random.randint(1, 10) for i in range(100)]

# 预计算所有可能的和对应的阶乘，最多仅需110次计算
max_possible_sum = max(list1) + max(list2)
factorial_lookup = {sum_val: math.factorial(sum_val) for sum_val in range(2, max_possible_sum + 1)}

# 查表生成结果，无重复计算
result = [factorial_lookup[x + y] for x, y in itertools.product(list1, list2)]

Wall time: 15 ms

优化后性能提升约70倍，如果你实际场景中唯一组合量级仍然很大，可以额外引入多进程并行计算所有唯一组合的结果，进一步利用多核CPU性能。

实际场景适配方法 #

对于你用到的交集检查dynamo函数，只需对预计算逻辑做少量修改：

• 先提取list1的唯一元素集合unique_list1、list2的唯一元素集合unique_list2
• 遍历所有itertools.product(unique_list1, unique_list2)的唯一组合，计算交集结果，以(元素1, 元素2)为key存入查找表
• 全量组合遍历时直接查表获取结果即可

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