Python嵌套列表统计元素对出现次数的性能优化方案

原有代码性能问题分析 #

• 四层循环生成全量配对中间列表，数据量大时内存占用极高，遍历效率极低
• 后续使用list.count()方法统计每个配对的出现次数，每次统计都要完整遍历一次全量配对列表，整体时间复杂度达到O(n²)，数据量上升后耗时会指数级增长

优化思路 #

配对s_p的总出现次数 = 单个staff元素s的总出现次数 × 单个process元素p的总出现次数，不需要生成全量配对列表，只需要先分别统计两类元素的出现频率，再直接计算乘积即可，整体时间复杂度降低到O(a + b + c*d)，其中a是staff总元素数、b是process总元素数、c是去重后staff数、d是去重后process数，性能提升非常明显。

优化后代码 #

from collections import Counter

processes = [['Iota', 'Gamma', 'Kappa'], ['Delta', 'Zeta', 'Beta'], ['Alpha', 'Zeta'], ['Alpha', 'Epsilon', 'Delta', 'Beta']]
staffs = [['William', 'James', 'Noah', 'Oliver'], ['Benjamin', 'Oliver', 'William'],['Oliver', 'Benjamin']]

# 分别统计两类元素的出现频率
staff_counter = Counter(s for each_s in staffs for s in each_s)
process_counter = Counter(p for each_p in processes for p in each_p)

with open(r'c:\temp\outfile.txt', 'a', encoding='utf-8') as outfile:
    for s, s_cnt in staff_counter.items():
        for p, p_cnt in process_counter.items():
            outfile.write(f"{s}_{p}@{s_cnt * p_cnt}\n")

额外优化点 #

• 如果不需要追加写入可以把打开模式的a换成w，避免多次运行重复写入内容
• 新增了encoding='utf-8'参数，避免出现特殊字符时写入乱码

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