为何字典统计频率的速度慢于排序列表生成频率数组？

我最近在做一道编程题时遇到了个反直觉的情况：明明理论上用字典统计元素频率是O(n)时间复杂度，而先排序再统计是O(nlogn)，但实际跑起来排序的方法反而更快，还帮我解决了超时问题！先给大家看看我写的两种实现：

字典统计频率的实现（超时版本） #

t= int(input())
for _ in range(t):
    n, k = map(int, input().split())
    arr = map(int, input().split())
    frequence_table = {}
    for num in arr:
        try:
            frequence_table[num] += 1
        except:
            frequence_table[num] = 1
    freq = list(frequence_table.values())
    freqs = sorted(freq, reverse=True)
    while k>0:
        if k>=freqs[-1]:
            k -= freqs.pop()
        else:
            break
    print(max(len(freqs), 1))

排序后统计频率的实现（AC版本） #

t= int(input())
for _ in range(t):
    n, k = map(int, input().split())
    arr = map(int, input().split())
    arr = sorted(arr)
    freq = [1]
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            freq[-1] += 1
        else:
            freq.append(1)
    freqs = sorted(freq, reverse=True)
    while k>0:
        if k>=freqs[-1]:
            k -= freqs.pop()
        else:
            break
    print(max(len(freqs), 1))

为什么会出现这种“理论与实际不符”的情况？ #

我后来琢磨了下，主要有这几个原因：

• 异常处理的开销：字典版本里用了try-except来处理新元素的初始化，而Python里异常捕获的代价其实很高——每次遇到新元素都会触发一次异常，这比直接用frequence_table.get(num, 0) + 1要慢不少，累积起来就拖慢了整体速度。
• 缓存局部性优势：排序后的数组是连续相同元素聚集在一起的，统计频率时是顺序遍历数组，访问的内存地址是连续的，缓存命中率极高；而字典的哈希表访问是随机的，经常会出现缓存未命中，这在底层硬件层面会带来额外的时间开销。
• Timsort的高效性：Python内置的sorted()用的是Timsort算法，它对有重复元素的序列优化得非常好，实际运行时的性能可能比我们估算的O(nlogn)要接近O(n)，尤其是当重复元素很多的时候，排序的耗时并没有想象中那么大。
• 额外的遍历与转换：字典版本里，我们先遍历map对象生成字典，再把字典的值取出来转成列表，最后还要排序；而排序版本里，排序和统计频率的过程更紧凑，减少了中间步骤的额外开销。

总的来说，理论时间复杂度是基于平均情况的抽象估算，而实际代码的性能还要考虑语言特性、硬件缓存、算法实现细节等很多因素，这也算是个很有意思的实践教训了！

备注：内容来源于stack exchange，提问作者User