60个短字符串全排列计算性能优化及高效处理方案咨询

60! ≈ 8.32×10^{81，这个数值比可观测宇宙的总原子数（约1×10}80）还要高一个数量级，哪怕你动用人类当前所有算力，每秒能生成10^{20个排列，跑完所有排列也需要约2.6×10}54年，远超过宇宙的年龄，没有任何超算、并行计算方案能够解决这个问题。

需求侧优化（必做） #

你当前的需求大概率是对业务目标的理解偏差，真实业务场景不可能需要用到全部60!个排列结果，先对齐业务目标再调整技术方案：

• 如果你的业务目标是求两组60个字符串的一一配对最优解，直接用匈牙利算法，时间复杂度O(n³)，60个元素的计算耗时不到1毫秒，完全不需要遍历全排列。
• 如果你的业务需要多个符合要求的配对结果，不需要全部枚举，直接用启发式算法：分支定界、遗传算法、模拟退火都可以在秒级得到Top K个满足要求的结果。
• 如果后续需要用配对结果做数据库搜索，提前给两组字符串建哈希索引，搜索耗时可以降到微秒级，不需要做全量预生成。

小规模排列的性能优化（仅适用于测试阶段20个元素以内的场景） #

如果是测试阶段需要处理小规模排列，可以按以下方式优化性能：

• 把当前单线程的Heap排列算法改成并行实现：按排列的第一个元素的取值拆分成n个独立的子任务，每个子任务处理第一个元素固定后的剩余n-1个元素的全排列，直接分配到多个CPU核心运行，就能跑满你CPU的100%算力，比当前单线程快6倍左右。
• 把所有短字符串提前映射为整数ID，所有排列操作直接对整数数组执行，需要输出配对结果时再映射回原字符串，能减少90%以上的字符串操作开销。
• 避免高频内存分配：复用排列数组的内存空间，不要每次生成新排列都创建新数组，减少VB.Net的GC回收耗时，性能可以再提升1~2个数量级。
• 不需要输出的排列不要做持久化存储，生成后直接喂给后续处理流程，减少IO开销。

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