如何优化Python代码以处理100+带引用的计算输入？

我需要解决一个计算问题，输入规则如下：

• 第一行是数字n，代表计算次数
• 后续n行是计算项，每行包含三个元素：运算方法、第一个参数、第二个参数
• 参数支持用$+计算索引的形式，引用其他计算项的结果（索引从0开始）

我编写的Python代码仅能处理小规模输入，现在需要优化以适配100+的大规模输入场景。

原代码 #

table = []
results = []

def eval(list_num ,list):
    if '$' not in list[1] and '$' not in list[2]:
        calc(list_num, list)
    else:
        if '$' in list[1]:
            if results[int(list[1][1])] != ' ':
                list[1] = results[int(list[1][1])]
        if '$' in list[2]:
            if results[int(list[2][1])] != ' ':
                list[2] = results[int(list[2][1])]

def calc(cell, variab):
    if variab[0] == 'VALUE':
        results[cell] = variab[1]
    elif variab[0] == 'ADD':
        results[cell] = str(int(variab[1]) + int(variab[2]))
    elif variab[0] == 'SUB':
        results[cell] = str(int(variab[1]) - int(variab[2]))
    elif variab[0] == 'MULT':
        results[cell] = str(int(variab[1]) * int(variab[2]))


n = int(input())
for i in range(n):
    operation, arg_1, arg_2 = input().split()
    table.append([operation, arg_1, arg_2])
    results.append(' ')
while ' ' in results:
    for i in range(n):
        eval(i, table[i])

for i in range(n):
    print(results[i])

原代码问题分析 #

原代码通过循环遍历所有计算项直到全部完成，时间复杂度为O(k*n)（k为循环次数）。当输入规模达到100+且存在长依赖链时，循环次数会接近n，整体复杂度退化为O(n²)，效率急剧下降。此外，代码直接修改原输入参数列表，可能导致重复处理时的逻辑混乱，且仅支持单数字索引（如$0），无法处理$10这类多位数索引。

优化后的代码 #

from functools import lru_cache

def main():
    n = int(input())
    operations = []
    for _ in range(n):
        op, arg1, arg2 = input().split()
        operations.append((op, arg1, arg2))
    
    @lru_cache(maxsize=None)
    def compute(index):
        op, arg1, arg2 = operations[index]
        
        # 解析参数，处理$引用
        def resolve_arg(arg):
            if arg.startswith('$'):
                ref_idx = int(arg[1:])
                return int(compute(ref_idx))
            return int(arg)
        
        if op == 'VALUE':
            return arg1
        elif op == 'ADD':
            return str(resolve_arg(arg1) + resolve_arg(arg2))
        elif op == 'SUB':
            return str(resolve_arg(arg1) - resolve_arg(arg2))
        elif op == 'MULT':
            return str(resolve_arg(arg1) * resolve_arg(arg2))
    
    # 批量计算并输出结果
    results = [compute(i) for i in range(n)]
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

优化说明 #

• 缓存机制：用lru_cache缓存每个计算项的结果，确保每个项仅计算一次，避免重复开销
• 递归解析依赖：遇到$引用时直接递归计算依赖项，保证依赖优先完成，无需循环遍历
• 索引兼容：支持多位数索引（如$100），修复原代码的索引解析缺陷
• 时间复杂度：整体复杂度降至O(n)，每个计算项仅被处理一次，适配100+甚至更大规模的输入

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