16嵌套循环速度C ++ / Rcpp

Question

我有一个计算量很大的程序，我需要运行16个嵌套的for循环才能完成对大小均为26的16个数字向量的所有可能排列的迭代检查。我的第一次尝试是使用R（我的首选语言） ，但很快就通过C++包重定向到了Rcpp。我可以在PC上本地运行代码（4核，Intel i7-6600U CPU @ 2.60GHz，16GB RAM），但是还可以访问Azure云计算，并且可以启动任何大小的群集。

我当前的代码如下：

#include <Rcpp.h>
#include <math.h>
#include <iostream>
using namespace Rcpp;

// [[Rcpp::export]]
NumericMatrix optimalIndex(NumericVector a, NumericVector b, NumericVector c, NumericVector d, NumericVector e, NumericVector f,
                           NumericVector g, NumericVector h, NumericVector i, NumericVector j, NumericVector k, NumericVector l,
                           NumericVector m, NumericVector n, NumericVector o, NumericVector p){
  NumericMatrix outp(1000000, 16);
  int index = 0;
  int minsum = 0;
  for(int c1 = 0; c1 < a.size(); c1++){
    for(int c2 = 0; c2 < b.size(); c2++){
      for(int c3 = 0; c3 < c.size(); c3++){
        for(int c4 = 0; c4 < d.size(); c4++){
          for(int c5 = 0; c5 < e.size(); c5++){
            for(int c6 = 0; c6 < f.size(); c6++){
              for(int c7 = 0; c7 < g.size(); c7++){
                for(int c8 = 0; c8 < h.size(); c8++){
                  for(int c9 = 0; c9 < i.size(); c9++){
                    for(int c10 = 0; c10 < j.size(); c10++){
                      for(int c11 = 0; c11 < k.size(); c11++){
                        for(int c12 = 0; c12 < l.size(); c12++){
                          for(int c13 = 0; c13 < m.size(); c13++){
                            for(int c14 = 0; c14 < n.size(); c14++){
                              for(int c15 = 0; c15 < o.size(); c15++){
                                for(int c16 = 0; c16 < p.size(); c16++){
                                  minsum = a(c1) + b(c2) + c(c3) + d(c4) + e(c5) + f(c6)
                                            + g(c7) + h(c8) + i(c9) + j(c10) + k(c11) + l(c12)
                                            + m(c13) + n(c14) + o(c15) + p(c16);
                                  if(minsum == 0){
                                    outp(index, 0) = c1;
                                    outp(index, 1) = c2;
                                    outp(index, 2) = c3;
                                    outp(index, 3) = c4;
                                    outp(index, 4) = c5;
                                    outp(index, 5) = c6;
                                    outp(index, 6) = c7;
                                    outp(index, 7) = c8;
                                    outp(index, 8) = c9;
                                    outp(index, 9) = c10;
                                    outp(index, 10) = c11;
                                    outp(index, 11) = c12;
                                    outp(index, 12) = c13;
                                    outp(index, 13) = c14;
                                    outp(index, 14) = c15;
                                    outp(index, 15) = c16;
                                    outp(index, 16) = c17;
                                    outp(index, 17) = c18;
                                    outp(index, 18) = c19;
                                    outp(index, 19) = c20;
                                    outp(index, 20) = c21;
                                    outp(index, 21) = c22;
                                    outp(index, 22) = c23;
                                    outp(index, 23) = c24;
                                    outp(index, 24) = c25;
                                    outp(index, 25) = c26;
                                    outp(index, 26) = c27;
                                    outp(index, 27) = c28;
                                    outp(index, 28) = c29;
                                    outp(index, 29) = c30;
                                    outp(index, 30) = c31;
                                    index++;
                                  }
                                }
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  return(outp);
}

此函数的输出维outp在这一点上是未知的，因此我任意选择了100万行。我想返回行总和匹配指定条件的每一列的索引，即。 = 0。

显然，这需要像YEARS那样运行。我不确定并行化是否是此循环的选项，或者我可以使用其他什么方法来提高速度。就像我说的那样，如果可以，我可以在具有更多核心和/或更多内存的Azure中运行。

是否有更好/更快的方法？

Answer 1

我认为不可能在合理的时间内运行此程序，因为26 ^ 16等于43,608,742,899,428,874,059,776。我认为使用状态为dp [SUM] [letterIndex]的动态编程可以更快地解决此问题。您可以预先计算多少个字母组合，其总和等于SUM并使用letterIndex字母。该解决方案的复杂度为O（26 * MAX），其中MAX是向量中的最大值。