Wordle游戏smart_guess函数性能优化：将6秒运行时长压缩至1秒以内

我帮你梳理了代码里的性能瓶颈，核心问题集中在低效的字符串比较、重复计算和不够合理的采样逻辑上。下面是针对性的优化方案，既能把运行时间压到1秒以内，又能保留原函数选择最优猜测的核心逻辑：

1. 重写compare函数（最大性能提升点） #

原来的compare用了很多低效操作：比如多次调用target.count(letter)（每次都是O(n)遍历）、index_list.remove(idx)（O(n)时间复杂度），这些在大规模target列表里会累积成巨大的耗时。优化后的版本用collections.Counter一次性统计字符频率，并且用两次线性遍历完成判断，时间复杂度降到O(n)：

from collections import Counter

def compare(guess, target):
    '''优化后的比较函数：返回'X'（位置正确）、'O'（存在但位置错）、'-'（不存在）'''
    n = len(guess)
    result = ['-'] * n
    target_counts = Counter(target)
    
    # 第一步：标记所有位置正确的字符（X）
    for idx in range(n):
        if guess[idx] == target[idx]:
            result[idx] = 'X'
            target_counts[guess[idx]] -= 1
            if target_counts[guess[idx]] == 0:
                del target_counts[guess[idx]]
    
    # 第二步：标记存在但位置错误的字符（O）
    for idx in range(n):
        if result[idx] != 'X' and guess[idx] in target_counts:
            result[idx] = 'O'
            target_counts[guess[idx]] -= 1
            if target_counts[guess[idx]] == 0:
                del target_counts[guess[idx]]
    
    return ''.join(result)

2. 优化distributions函数 #

原来的统计逻辑用了手动判断key是否存在，换成collections.defaultdict可以减少冗余判断，提升统计效率：

from collections import defaultdict

def distributions(guess, targets):
    distr_dict = defaultdict(int)
    for target in targets:
        res = compare(guess, target)
        distr_dict[res] += 1
    return distr_dict

3. 改进sample_targets的采样逻辑 #

原来的targets[0:sample_size]取的是有序列表的前N个，采样不随机，而且重复添加随机元素可能导致重复样本。改用random.sample可以保证采样的随机性，同时避免重复：

def sample_targets(targets):
    len_word = len(targets[0])
    # 调整采样大小：根据单词长度设置更合理的数值，同时不超过targets的长度
    sample_size_map = {
        4: 100,
        5: 100,
        6: 60,
        7: 60,
        8: 70,
        9: 8,
        10:5
    }
    sample_size = min(sample_size_map.get(len_word, 50), len(targets))
    # 随机采样，保证无重复
    samples = set(random.sample(targets, sample_size))
    # 额外添加2个随机样本（可选，增加采样多样性）
    if len(samples) < len(targets):
        samples.add(random.choice(targets))
        samples.add(random.choice(targets))
    return samples

4. 微调smart_guess的终止逻辑 #

在遍历采样时，一旦找到能把最大分布值降到1的猜测（也就是直接锁定目标），可以立即返回，不用继续遍历剩下的样本：

def smart_guess(wordlist, targets):
    ''' Returns best guess after comparing the distributions of each sampled guess '''
    samples = sample_targets(targets)
    min_largest_value = len(wordlist)
    best_guess = ""
    
    for guess in samples:
        distr = distributions(guess, targets)
        biggest_value = max(distr.values())
        
        if biggest_value < min_largest_value:
            min_largest_value = biggest_value
            best_guess = guess
            
            # 提前终止：如果已经能把候选缩小到1个，直接返回
            if min_largest_value == 1:
                return best_guess
            # 原有的终止条件保留
            elif min_largest_value <= 2:
                return best_guess
    
    # 如果采样里没找到最优， fallback到随机选一个（可选，避免空返回）
    return best_guess if best_guess else random.choice(targets)

优化效果说明 #

• compare函数：把原来的多次O(n)操作降到单次O(n)，这是最大的性能提升点，直接减少了distributions函数的耗时。
• 采样逻辑：随机采样保证了选出来的guess更具代表性，同时避免了重复样本的无效计算。
• 数据结构优化：用Counter和defaultdict替代手动字典操作，利用Python内置的高效实现减少底层开销。

经过这些优化后，smart_guess的运行时间应该能轻松降到1秒以内，同时保留原有的“最小化最大候选数”的最优猜测逻辑，不会影响游戏的猜测效率。

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