Python的collections.Counter.total()方法的时间复杂度是多少？

底层实现逻辑 #

collections.Counter 是继承自原生字典的计数类，total() 为 Python 3.10 版本新增的实例方法，官方 CPython 实现中没有维护额外的全局累计计数缓存，方法核心逻辑等价于对 Counter 存储的所有计数值求和，对应伪代码如下：

def total(self):
    return sum(self.values())

每次调用该方法时，都会实时遍历所有键对应的计数值计算总和。

时间复杂度 #

• 时间复杂度为 O(k)，其中 k 是 Counter 中存储的不同元素的数量，和被统计元素的总个数无关
• 示例说明：若 Counter 仅统计了1个元素的100万次出现记录，此时k=1，调用total()耗时为常数级；若 Counter 存储了2000个不同元素的计数结果，调用total()就需要遍历2000个计数值求和。

注意事项 #

如果业务逻辑中需要多次获取计数总和，建议自行缓存total()的返回值，避免重复遍历带来的性能损耗。

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