使用并行计算大幅提升递归算法效率

使用并行计算大幅提升递归算法效率2013-01-21 infoq 千峰前言：

无论什么样的并行计算方式，其终极目的都是为了有效利用多机多核的计算能力，并能灵活满足各种需求。相对于传统基于单机编写的运行程序，如果使用该方式改写为多机并行程序，能够充分利用多机多核cpu的资源，使得运行效率得到大幅度提升，那么这是一个好的靠谱的并行计算方式，反之，又难使用又难直接看出并行计算优势，还要耗费大量学习成本，那就不是一个好的方式。

由于并行计算在互联网应用的业务场景都比较复杂，如海量数据商品搜索、广告点击算法、用户行为挖掘，关联推荐模型等等，如果以真实场景举例，初学者很容易被业务本身的复杂度绕晕了头。因此，我们需要一个通俗易懂的例子来直接看到并行计算的优势。

数字排列组合是个经典的算法问题，它很通俗易懂，适合不懂业务的人学习，我们通过它来发现和运用并行计算的优势，可以得到一个很直观的体会，并留下深刻的印象。问题如下：

请写一个程序，输入M，然后打印出M个数字的所有排列组合（每个数字为1，2，3，4中的一个）。比如：M=3，输出：

1，1，11，1，2……4，4，4

共64个

注意：这里是使用计算机遍历出所有排列组合，而不是求总数，如果只求总数，可以直接利用数学公式进行计算了。

一、单机解决方案：

通常，我们在一台电脑上写这样的排列组合算法，一般用递归或者迭代来做，我们先分别看看这两种方案。

1）单机递归

可以将n（1<=n<=4）看做深度，输入的m看做广度，得到以下递归函数，完整代码见附件CombTest.java：

http://www.infoq.com/resource/articles/parallel-computing-improve-recursive-algorithm- efficiency/zh/resources/demo.rar

public void comb（String str）{for（int i=1;i<n+1;i++）{if（str.length（）==m-1）{System.out.println（str+i）;total++;} else {comb（str+i）;}}}

但是当m数字很大时，会超出单台机器的计算局限导致缓慢，太大数字的排列组合在一台计算机上几乎很难运行出，不光是排列组合问题，其他类似遍历求解的递归或回溯等算法也都存在这个问题，如何突破单机计算性能的问题一直困扰着我们。

2）单机迭代

我们观察到，求的m个数字的排列组合，实际上都可以在m-1的结果基础上得到。

比如m=1，得到排列为1,2,3,4，记录该结果为r（1）

m=2, 可以由（1,2,3,4）* r（1） = 11,12,13,14,21,22,…,43,44得到, 记录该结果为r（2）

由此，r（m） =（1,2,3,4）*r（m-1）

如果我们从1开始计算，每轮结果保存到一个中间变量中，反复迭代这个中间变量，直到算出m的结果为止，这样看上去也可行，仿佛还更简单。

但是如果我们估计一下这个中间变量的大小，估计会吓一跳，因为当m=14的时候，结果已经上亿了，一亿个数字，每个数字有14位长，并且为了得到m=15的结果，我们需要将 m=14的结果存储在内存变量中用于迭代计算，无论以什么格式存，几乎都会遭遇到单台机器的内存局限，如果排列组合数字继续增大下去，结果便会内存溢出了。