为何Python中基于Counter的字谜解法远慢于排序解法？

我实现了两种在语言词库中查找给定单词字谜的算法。原本以为基于Counter的版本会更快——毕竟Counter是哈希表实现（O(1)访问），而排序的时间复杂度通常是O(n log n)。但实际测试里排序版本的速度大概是Counter版本的60倍，这是为什么？

排序版本代码 #

import urllib.request
import time

LANGUAGE_REFERENCE_URL = "https://inventwithpython.com/dictionary.txt"


def find_anagrams_sorting(input_str):
    input_str = input_str.upper()
    sorted_input_str = "".join(sorted(input_str))
    results = []
    for idx, word in enumerate(sorted_words_list):
        if word == sorted_input_str:
            results.append(words_list[idx])
    return results


with urllib.request.urlopen(LANGUAGE_REFERENCE_URL) as response:
    words_list = response.read().decode('utf-8').split("\n")

words_list = list(map(lambda x: x.upper(), words_list))  # Needed if source has mixed case
sorted_words_list = list(map(lambda x: "".join(sorted(x)), words_list))

# Time execution for sorting version
start = time.perf_counter()
print(find_anagrams_sorting("rats"))
print(find_anagrams_sorting("RatS"))
print(find_anagrams_sorting("Goldfish"))
print(find_anagrams_sorting("SteaL"))
end = time.perf_counter()
print(f"Checked all anagrams in language reference using sorting. Seconds taken: {end - start:.7f}")

Counter版本代码 #

import urllib.request
import time
from collections import Counter

LANGUAGE_REFERENCE_URL = "https://inventwithpython.com/dictionary.txt"


def find_anagrams_hash_table(input_str):
    input_str = input_str.upper()
    input_str_counter = Counter(input_str)
    results = []
    for idx, word in enumerate(word_counters):
        if Counter(word) == input_str_counter:
            results.append(words_list[idx])
    return results


with urllib.request.urlopen(LANGUAGE_REFERENCE_URL) as response:
    words_list = response.read().decode('utf-8').split("\n")

words_list = list(map(lambda x: x.upper(), words_list))  # Needed if source has mixed case
word_counters = list(map(lambda x: Counter(x), words_list))

# Time execution for hash table version
start = time.perf_counter()
print(find_anagrams_hash_table("rats"))
print(find_anagrams_hash_table("RatS"))
print(find_anagrams_hash_table("Goldfish"))
print(find_anagrams_hash_table("SteaL"))
end = time.perf_counter()
print(f"Checked all anagrams in language reference using hash table. Seconds taken: {end - start:.7f}")

原因分析 #

1. 你的Counter代码存在致命冗余
   你预计算了word_counters列表，但在查找函数里完全没用到——反而每次循环都重新调用Counter(word)生成新的Counter对象。这相当于重复做了几十上百万次哈希表初始化，直接把性能拖垮了。就算修正成用word_counters[idx]，性能也赶不上排序版本。

2. 字符串操作的底层优化碾压哈希表

   • 排序版本的核心是字符串比对：CPython对字符串的相等性检查做了极致优化，直接比对内存中的字节序列，速度快到离谱。预计算的排序字符串存储成本也极低，就是普通的字符串对象。
   • Counter版本的核心是哈希表比对：两个Counter相等需要遍历所有键值对，检查每个字符的计数是否一致。哈希表本身的创建、存储、遍历都有不小的常数开销，对于短单词来说，这些开销的占比远高于排序的O(n log n)耗时。

3. 理论复杂度不等于实际性能
   排序的O(n log n)是理论时间复杂度，但对于英文单词这种短字符串（大多在10个字符以内），排序的实际耗时微乎其微。而Counter的哈希表操作虽然理论上是O(n)，但每个步骤的常数因子太大，实际运行起来反而慢得多。

修正后的Counter版本（仍不如排序快，但能提速） #

把查找函数里的Counter(word)换成预计算的word_counters[idx]：

def find_anagrams_hash_table(input_str):
    input_str = input_str.upper()
    input_str_counter = Counter(input_str)
    results = []
    for idx, word_counter in enumerate(word_counters):
        if word_counter == input_str_counter:
            results.append(words_list[idx])
    return results

就算修正后，排序版本依然会更快，因为字符串比对的效率还是远高于哈希表比对。

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