字符串字符频率统计：两种方法的性能差异及原因探究

问题描述 #

有两段用于统计字符串中出现频率最高字符的代码：code1通过遍历字符串时检查字典中是否存在字符来统计频率，code2则先将字符串转换为集合再遍历统计。根据测试结果，code1耗时2.6955，code2耗时3.4223，code1性能更优。请问：

1. code1是否因性能优势更值得选用？
2. 为何将字符串转为集合的方式比在字典中检查元素存在性更耗时？

代码实现 #

code1：遍历字符串时检查字典存在性

string = "This is an example string"
char_list = {}
for char in string:
    if char in char_list:
        char_list[char] += 1
    else:
        char_list[char] = 1

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]

code2：先转集合再统计

string = "This is an example string"
char_list = {}
for char in set(string):
    char_list[char] = string.count(char)

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]

性能测试代码与结果 #

import timeit

code1 = '''
string = "This is an example string"
char_list = {}
for char in string:
    if char in char_list:
        char_list[char] += 1
    else:
        char_list[char] = 1

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]
'''

code2 = '''
string = "This is an example string"
char_list = {}
for char in set(string):
    char_list[char] = string.count(char)

max_frequency = max(char_list.values())
chars_with_max_frequency = [key for key, value in char_list.items() if value == max_frequency]
'''

print("Method #1: Checking string for unique chars: %.4f" % timeit.timeit(code1, number=1000000))
print("Method #2: Converting string to set: %.4f" % timeit.timeit(code2, number=1000000))

测试结果：

方法1：检查字符串唯一字符耗时：2.6955
方法2：转换字符串为集合耗时：3.4223

解答 #

1. code1更值得选用
   code1的核心优势是遍历效率：它只需要遍历字符串一次，就能完成所有字符的频率统计，后续的最大值查找和筛选都是基于已统计好的字典，开销极低。而code2的逻辑存在明显的效率浪费：

• 第一步转集合需要遍历一次字符串；
• 第二步对每个唯一字符调用string.count(char)，每次调用都会从头遍历整个字符串来计数，相当于总遍历次数是1 + 唯一字符数。当字符串长度增加时，这种重复遍历的开销会呈线性增长，性能差距会被进一步放大。从测试结果也能看出，即使是短字符串，code1的耗时也比code2少20%以上。

2. 转集合方式更耗时的核心原因
   表面上看是转集合的开销，但本质是code2的整体逻辑带来的多重遍历：

• 转集合本身是O(n)操作，需要遍历字符串、计算每个字符的哈希值、处理哈希冲突并存储唯一元素，这确实有一定开销，但不是主要原因；
• 真正的性能杀手是string.count(char)：每次调用都会完整遍历字符串，对每个字符进行匹配，这是O(n)的操作，而code2要对每个唯一字符执行一次这个操作，总时间复杂度是O(n * k)（k是唯一字符数）；
• 反观code1中的if char in char_list，字典的键查找是基于哈希表的O(1)操作，几乎没有额外开销，整个统计过程只需要一次O(n)遍历，时间复杂度是O(n)，自然比code2高效得多。

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