如何优化Python脚本循环性能 解决执行超时超5秒问题

性能问题根源 #

你当前代码的时间复杂度为O(n²)，当N达到1e5量级时完全无法在5秒限制内跑完，耗时集中在两处：

• if not any(tablica[r] == x for x in unikaty):：每次判断元素是否存在需要遍历整个unikaty列表，最坏单次判断耗时O(n)，整体去重步骤耗时O(n²)
• tablica.count(i)：每次统计频率需要遍历整个tablica列表，单次调用耗时O(n)，多次调用后整体统计步骤耗时也为O(n²)

优化方案 #

核心思路是用哈希表（Python字典）做频率统计，把整体时间复杂度降到O(n)：

1. 因为列表是不可哈希类型，无法作为字典的key，所以构造元素时直接把嵌套列表转为嵌套元组
2. 无需单独做去重操作，遍历一次所有元素即可同步完成频率统计
3. 统计完频率后只需遍历频率字典，就能快速得到最大频率和对应元素数量

优化后代码 #

def solve(N, A):
    freq = {}
    for r in range(N):
        # 转为可哈希的嵌套元组
        item = ((A[0][r], A[0][r+1]), (A[1][r], A[1][r+1]))
        # 一次遍历统计频率
        freq[item] = freq.get(item, 0) + 1
    
    # 找最大频率
    max_freq = max(freq.values())
    # 统计有多少个元素频率等于最大频率
    return sum(1 for v in freq.values() if v == max_freq)
                             
T = int(input())
if not (1 <= T <= 10):
    quit()

for _ in range(T):
    N = int(input())
    if not (1 <= N <= 10**5):
        quit()
    A = [list(map(int, input().split())) for i in range(2)]
    print(solve(N, A))

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