Python中如何基于list生成元素与出现次数的tuple列表并优化代码

原代码存在的问题 #

• 每次循环都需要两次生成临时列表[v1 for (v1,count) in tuple_count_list]，额外占用内存
• 成员判断in和index查找操作的时间复杂度都是O(k)（k是当前已统计的不同元素数量），整体时间复杂度达到O(n²)，列表长度较大时性能会非常差

优化方案 #

方案1：使用标准库collections.Counter（最推荐） #

Python内置的Counter工具专门用来做可迭代对象的频率统计，Python3.7及以上版本会默认保留元素第一次出现的插入顺序，完全符合预期输出要求。

from collections import Counter

def get_tuple_count_list(_list):
    return list(Counter(_list).items())

print(get_tuple_count_list(["a","b","b","d","e","a","a","a","c","b"]))
# 输出：[('a', 4), ('b', 3), ('d', 1), ('e', 1), ('c', 1)]

该方案时间复杂度为O(n)，代码简洁易维护。

方案2：手动用字典暂存计数（不依赖内置统计库的场景） #

如果不想引入collections依赖，可以用普通字典做中间存储，利用字典O(1)的查找特性提升效率：

def get_tuple_count_list(_list):
    count_dict = {}
    for v in _list:
        count_dict[v] = count_dict.get(v, 0) + 1
    return list(count_dict.items())

print(get_tuple_count_list(["a","b","b","d","e","a","a","a","c","b"]))

该方案同样是O(n)的时间复杂度，性能和Counter方案基本一致，兼容性更好；如果需要兼容Python3.7以下版本，替换普通字典为collections.OrderedDict即可保持顺序。

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