Python循环加速求助：优化问题向量生成代码运行过慢

嘿，我看你这段代码在生成满足条件的向量排列并去除循环等价项时，耗时特别久——主要问题出在生成唯一排列的方式和线性遍历检查重复这两个环节上。下面我给你拆解问题，再一步步给出优化方案：

核心问题分析 #

1. 生成唯一排列效率低：用set(it.permutations(vector))的方式，会先生成所有可能的排列（包括大量重复的，因为vector里有重复元素），再通过集合去重，做了很多无用功；
2. 成员检查速度慢：用列表already_reviewed做p not in检查是线性时间复杂度O(n)，当列表元素越来越多，这一步会越来越卡。

优化方案1：直接生成唯一排列，避免无效计算 #

对于包含重复元素的序列，我们可以利用collections.Counter来直接生成唯一排列，跳过那些重复的排列生成过程，节省大量时间：

from collections import Counter

def unique_permutations(seq):
    counts = Counter(seq)
    if not counts:
        yield ()
    else:
        # 取一个元素，递归生成剩余元素的唯一排列
        elem = next(iter(counts))
        remaining = counts.copy()
        remaining[elem] -= 1
        if remaining[elem] == 0:
            del remaining[elem]
        for perm in unique_permutations(tuple(remaining.elements())):
            # 将当前元素插入到排列的各个位置
            for i in range(len(perm) + 1):
                yield perm[:i] + (elem,) + perm[i:]

这个函数直接生成无重复的排列，不需要先生成全排列再去重，时间复杂度从O(n!)降到了O(n!/(k₁!k₂!...kₘ!))（k是每个元素的重复次数），对于有重复元素的vector，效率提升非常明显。

优化方案2：用集合替代列表做快速重复检查 #

把already_reviewed从列表改成集合，集合的成员检查是哈希表查找，时间复杂度是O(1)，比列表的线性查找快得多：

替换原来的循环部分：

already_seen = set()
# 要遍历集合的拷贝，因为我们要修改原集合，避免遍历出错
for p in list(unique_perms):
    if p not in already_seen:
        # 生成当前排列的所有循环变体
        circular_perms = tuple(p[i:] + p[:i] for i in range(len(p)))
        already_seen.update(circular_perms)
        # 移除除当前排列外的其他循环变体
        unique_perms.difference_update(circular_perms[1:])

完整优化后的代码 #

把这些优化整合起来，代码变成这样：

import numpy as np
import itertools as it
import time
from collections import Counter

def unique_permutations(seq):
    counts = Counter(seq)
    if not counts:
        yield ()
    else:
        elem = next(iter(counts))
        remaining = counts.copy()
        remaining[elem] -= 1
        if remaining[elem] == 0:
            del remaining[elem]
        for perm in unique_permutations(tuple(remaining.elements())):
            for i in range(len(perm) + 1):
                yield perm[:i] + (elem,) + perm[i:]

v = [35,36,37,38,39,40,41,42,43,44,45,46]
start_total = time.time()

# 生成初始组合并筛选和为360的向量
m = np.array(list(it.combinations_with_replacement(v, 9)))
g = m[np.sum(m, axis=1) == 360]
print('g shape', g.shape)

f = []
for i, vector in enumerate(g[:10]):  # 后续可以去掉[:10]处理所有向量
    print(f"Processing vector {i}")
    start = time.time()
    # 生成唯一排列并转成集合
    unique_perms = set(unique_permutations(vector))
    end = time.time()
    print(f'Length of unique permutations: {len(unique_perms)}')
    print(f'Time to generate unique permutations: {end - start:.4f}s')
    
    start = time.time()
    already_seen = set()
    for p in list(unique_perms):
        if p not in already_seen:
            circular_perms = tuple(p[i:] + p[:i] for i in range(len(p)))
            already_seen.update(circular_perms)
            unique_perms.difference_update(circular_perms[1:])
    end = time.time()
    print(f'Time to remove circular duplicates: {end - start:.4f}s')
    
    f.append(list(unique_perms))

print(f'Total runtime: {time.time() - start_total:.4f}s')

额外小提示 #

如果g的数量很大，你还可以考虑用多进程/多线程来并行处理每个vector，进一步提升整体速度——不过先把上面的单线程优化做好，已经能解决大部分性能问题了。

内容的提问来源于stack exchange，提问作者Erik Nyström