字典序全排列生成算法提速[一次作业]

以下是刚刚完成的一个作业，后半部分图文互换太麻烦了，我都贴了图，会有一些不齐，凑合看吧，3个实验的代码比较长，欢迎来信索取文档和3份代码，我的email:mgigabyte[艾特]gmail.com

可能会有部分网友感觉很垃圾，很无聊，权且仅当是一个作业吧，我对这个作业的预算是3天，实际1天半完成，还是比较满意的。

字典序全排列生成算法提速

摘 要： 本文实验了字典序全排列生成算法，并给出了三种优化方法，采用t假设检验的方法证明3种优化方法都可接受，最终的优化方法比作为baseline的算法提速了29.7倍。

关键词：字典序全排列生成算法；t假设检验。

1 引言

在全排列生成方法是一种将n个不同的项按照一定的顺序，无重复、无遗漏地列举出全部的不同的排列方法，n个不同项将会生成n阶层个不同的排列方案，在这些方法中字典序方法最为自然容易理解，但字典序法不可避免地需要循环或者递归，而以邻位对换法等为代表的LOOPLESS的方法避免了循环和递归，但由于每次执行都需要依赖此前的结果，因此在分布式，多核环境下显得性能不高。字典序方法虽然依赖循环和递归但其很容易将任务分解在不同的计算单元在多核，甚至是分布式的环境下，可以获得很好的性能。本文从字典序的3重优化过程，来探讨字典序的性能提速。

2 相关工作

论文[1]提到了常见的通过邻位对换法来获得全排列生成算法，论文[2]讨论了并行计算排列生成算法，并且支持scalability，性能和计算机CPU核数量相关，论文[3]提出了一种新的计算第kth个排列方案的并行算法。

3 系统的优化方法

本文利用字典序的基本算法，生成一个最简单的算法作为性能比较的baseline。之后采用了递归底部消除，多线程，文件读写优化等方法，将性能提升29.7倍。

以[1,2,3,4]为例进行举例：

图1 递归过程

递归过程为一个从k叉树逐级递减，直到1叉树，深入优先的过程，栈的深度为O(n)，n为给出的n不同项的数目。

第一个优化的想法：在递归到某个k叉树的节点时，没有必要继续递归，而是可以直接求解，从而消除底部的递归，实验尝试了消除底部1层的递归，消除2层的递归和消除3层的递归，实验表明消除2层的递归的性能更加优良，性能提升3%，并以此为基础继续进行优化。

第二个优化的想法：整个计算都是顺序执行，系统的其他CPU核并没有使用上，使用并行计算的方法对计算资源进行饱和。和第一种优化思路相反，本文使用了在递归树的顶部进行展开出9个线程分别计算，实验表明采用这种方法，性能提升31%，如图2所示。

图2 多线程方法等价于在顶部展开

如图2所示，1打头的字典序算法由一个独立的线程完成，并写入一个独立的文件f1。因此4个元素的情况下，结果会生成4个文件，最后用cat命令将这4个文件进行合并输出。如果将结果输出文件看成一个织布，那么这里同时让4个织布工人同时织布，每个织布工人都从头开始织布，不考虑其他织布工人的情况，最后把各自的织布合并成为一个完成的布匹。

第三个优化方法是：从结果文件的角度考虑系统同时有10个线程在进行磁盘IO，最后还需要进行一次合并，如果采用mmap将文件映射到内存，直接在内存中写入，最后一次性sync进磁盘，可以大大提高效率。实验表明采用这种方法后，性能提升2183%。只所以能高效优化，可以认为4个织布工人在同一张大布上分别织布，织完后就是最后的结果，不同的工人织布的起始点不同，各自安排好织布的起始点分别织布。性能的提升主要和mmap这种文件读写加速有关。

使用最优的优化算法后，我们对9个不同的项做了实验，在最好的算法下，9阶层个输出项只需要平均0.042秒即可完成，相当于输出一个项只需0.12微秒。

4 实验和分析

首先我们使用了递归底部展开的优化方法，该优化方法与快速排序在递归到最后k个元素后采用简单的直接插入排序类似，以下是实验一的数据，我们采用t检验的假设检验的方法，这种方法可以有效地估计性能提升是否可以接受。用t检验来对3种展开的方法进行效果估计，并在最后给出了产生这些数据的分析。

实验结论，方法2比方法1和方法3都具有显著的性能提升，方法2的有效性可以接受。

4.1 实验一 递归展开