优化FIDE国际象棋奥赛配对递归函数：缓存反而变慢？

首先解释为什么加了@cached反而变慢：

• 缓存key无效：你的函数参数usedTeams和teams都是可变的列表类型，memoization库默认会把列表的内存地址作为缓存key的一部分——哪怕两个列表内容完全相同，只要内存地址不同就会被当成不同参数，导致缓存完全不命中。不仅没享受到缓存的好处，还额外增加了缓存的存储、序列化和查找开销。
• 全局变量副作用：你用了全局变量matches来收集结果，递归过程中这个变量会被持续修改，导致缓存返回的结果包含之前调用的旧数据，缓存的有效性完全丧失，同时也会让结果逻辑混乱。

下面分两种场景给出优化方案：

场景1：确实需要生成所有可能的配对组合（仅适用于n≤12的小场景） #

如果你的需求是生成所有符合对手选择顺序的配对组合，先修复代码的核心问题，再正确使用缓存：

修复后的代码 #

import itertools
from memoization import cached

@cached
def pairing(n, used_teams=(), teams=None, reverse=False):
    """
    返回所有符合对手选择逻辑的队伍配对组合
    参数：
        n: 剩余待配对的队伍数
        used_teams: 已完成的配对（元组类型，用于缓存）
        teams: 当前待配对的队伍列表（元组类型，用于缓存）
        reverse: 是否优先为低排名队伍配对
    返回：
        所有配对组合的列表
    """
    if teams is None:
        teams = tuple(range(n))
    
    if reverse:
        teams = tuple(reversed(teams))

    # 剩余2支队伍，直接配对
    if len(teams) == 2:
        return [list(used_teams) + [[teams[0], teams[1]]]]
    
    elif len(teams) > 2:
        team = teams[0]
        current_len = len(teams)
        # 修复原代码bug：用当前剩余队伍数代替初始n生成对手列表
        opp_teams = [teams[i] for i in itertools.chain(
            range(round(current_len/2), current_len), 
            range(round(current_len/2)-1, 0, -1)
        )]
        
        all_matches = []
        for opp in opp_teams:
            # 生成新的待配对队伍元组
            tmp_teams = tuple(t for t in teams if t not in (team, opp))
            # 用元组拼接代替深拷贝，减少开销
            new_used = used_teams + ((team, opp),)
            # 递归收集子问题结果
            sub_matches = pairing(len(tmp_teams), new_used, tmp_teams, reverse)
            all_matches.extend(sub_matches)
        return all_matches

# 测试
import time
start = time.process_time()
result = pairing(12)
print(f"耗时：{time.process_time() - start}秒")
print(f"生成配对数：{len(result)}")  # 应为10395，符合(11)!!的计算结果

关键优化点 #

1. 可变参数转不可变：把usedTeams和teams改成元组，让缓存能正确识别相同内容的参数，提升命中率。
2. 移除全局变量：改成递归返回子问题结果，避免副作用，确保缓存结果的正确性。
3. 修复对手选择逻辑：原代码错误地使用初始n生成对手列表，现在改为用当前剩余队伍数，确保递归过程中对手选择正确。
4. 替换深拷贝：用元组拼接代替deepcopy，大幅减少内存拷贝开销。

场景2：实现FIDE 9.3条款的单组配对（支持n≤100的大场景） #

如果你的目标是生成符合FIDE规则的一组有效配对（而非所有组合），那递归生成所有组合的思路完全不可行——n=100时所有配对组合数是(99)!!，这是一个天文数字，根本无法计算。

FIDE奥赛9.3条款核心是瑞士制团体赛的配对逻辑：同积分组内优先高排名对高排名、避免重复对阵、颜色平衡等。推荐用以下高效算法实现：

方案：Berger配对法（循环赛标准配对） #

适合偶数队伍的循环赛配对，能快速生成对称的配对方案，可在此基础上添加FIDE规则的约束（如避免重复对阵、颜色调整）：

def berger_pairing(n):
    """生成Berger循环赛配对表，n为偶数"""
    if n % 2 != 0:
        raise ValueError("n必须是偶数")
    teams = list(range(n))
    all_round_pairings = []
    
    for _ in range(n-1):
        round_pairs = []
        # 固定首队，与中间队伍配对
        round_pairs.append([teams[0], teams[n//2]])
        # 其余队伍对称配对
        for i in range(1, n//2):
            round_pairs.append([teams[i], teams[n - i]])
        all_round_pairings.append(round_pairs)
        # 轮换队伍（首队固定，其余队伍右移一位）
        teams.insert(1, teams.pop())
    
    return all_round_pairings

# 示例：生成12队的Berger配对
print(berger_pairing(12))

扩展FIDE规则约束 #

如果需要支持避免重复对阵、颜色平衡等规则，可以在Berger配对的基础上做贪心调整：

1. 将队伍按积分/排名排序
2. 从最高排名开始，依次为其分配未配对、未对阵过的最高排名对手
3. 记录每队的对阵历史和颜色使用情况，确保符合规则

通用性能优化建议 #

• 避免递归深度问题：n=100时递归深度为50，未超过Python默认递归限制，但迭代式算法始终比递归更高效，适合大n场景。
• 减少内存开销：避免生成不必要的中间列表，用生成器或迭代器代替列表推导（如果不需要保存所有结果）。
• 缓存策略调整：如果用缓存，可指定@cached(cache_type=CacheType.LRU)设置LRU缓存，避免内存溢出。

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