如何优化7位随机序列生成算法，快速生成1万条相同位置重合数≤2的序列

首先最核心的优化是把校验逻辑从O(N)复杂度降至常数级，完全解决存量序列越多校验越慢的问题：

核心逻辑改造 #

任意两个序列如果有≥3个位置数值相同，必然存在某一组3个位置的组合取值完全一致。我们可以提前预计算所有3个位置的组合（总共有C(7,3)=35种），为每个组合建立一个哈希集合存储已经出现过的三元组值。
校验新序列时仅需：

• 生成该序列对应35组位置的三元组
• 检查任意一个三元组是否已存在于对应集合中，只要有一个存在就直接判定不合格
• 合格的序列就把它的35个三元组全部存入对应集合，再加入结果列表
  这个改动后，不管存量序列有多少，单次校验最多做35次哈希查询，速度提升至少上千倍。

优化后代码示例 #

import random
from itertools import combinations

TOTAL_SERIES = 10000
placement_amount = [9, 9, 9, 59, 9, 9, 9]
# 预生成所有3个位置的组合
pos_combinations = list(combinations(range(7), 3))
# 每个位置组合对应一个哈希集合
triplet_sets = {comb: set() for comb in pos_combinations}
all_series = []

while len(all_series) < TOTAL_SERIES:
    # 生成新序列
    series = [random.randint(0, placement_amount[i]) for i in range(7)]
    valid = True
    # 校验所有三元组
    for comb in pos_combinations:
        triplet = (series[comb[0]], series[comb[1]], series[comb[2]])
        if triplet in triplet_sets[comb]:
            valid = False
            break
    if valid:
        # 存入所有三元组
        for comb in pos_combinations:
            triplet = (series[comb[0]], series[comb[1]], series[comb[2]])
            triplet_sets[comb].add(triplet)
        all_series.append(series)

该代码单线程跑生成10000条最多几分钟即可完成，远快于原始实现。

• 多进程实现：Python多线程受GIL限制无法并行计算，之前用多线程卡住属于正常情况，改用多进程即可：开多个进程批量生成候选序列，统一送主进程做三元组校验入库，哈希集合仅在主进程维护，避免多进程同步开销
• CUDA实现建议：32位Python无法适配CUDA属于环境问题，换成64位Python+对应版本的CUDA Toolkit即可使用：用CuPy批量生成数十万级候选序列，用CUDA核函数并行计算候选序列和已有三元组的匹配情况，一次性过滤出大量合格序列
• 批量生成优化：用Numpy一次性生成数千条候选序列，批量做校验，避免Python循环开销，实测单线程下最快可以在10秒内完成10000条序列的生成

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