Python字典创建性能对比：字典推导式vs Counter

1. 为什么字典推导式执行速度更慢？ #

你的字典推导式写法{x:s1.count(x) for x in s1}存在核心效率问题：

• 每次循环都会调用s1.count(x)，这个方法会完整遍历整个字符串来统计当前字符x的出现次数。
• 你是遍历s1中的每一个字符（共60000个），相当于执行了60000次全字符串扫描，时间复杂度为O(n²)。
• 而循环迭代和collections.Counter()都是只遍历字符串一次，每遇到一个字符就直接更新对应计数，时间复杂度为O(n)，两者的效率差距由此产生。

2. 是否有和另外两种方法速度相当的字典推导式写法？ #

严格来说，字典推导式的语法特性决定了它无法实现单次遍历的O(n)效率（推导式无法在生成键值对的过程中维护计数状态），但可以通过先对键去重来大幅优化速度：

d1 = {x: s1.count(x) for x in set(s1)}

• set(s1)会去除s1中的重复字符，只保留唯一的键（这里是6个），这样只需要执行6次s1.count(x)，时间复杂度变为O(n + k*n)（k为不同字符的数量），耗时会和循环、Counter相当。
• 但这种写法的效率依赖于不同字符的数量k：如果字符串中不同字符很少，速度会很快；如果k接近字符串长度（比如随机乱码），效率还是会下降。

如果想要真正达到单次遍历的O(n)效率，字典推导式无法做到，循环迭代或collections.Counter()仍然是最优选择。

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