速度总和等于0到n的k个数字的所有组合，速度优化 [英] all combinations of k numbers between 0 and n whose sum equals n, speed optimization

问题描述

我有这个R函数来生成一个矩阵，该矩阵包含0和n之和等于n的k个数字的所有组合.这是我的程序的瓶颈之一，因为即使是很小的数，它也会变得非常慢(因为它正在计算功率集)

I have this R function to generate a matrix of all combinations of k numbers between 0 and n whose sum equals n. This is one of the bottlenecks of my program as it becomes extremely slow even with small numbers (because it is computing the power set)

这是代码

sum.comb <-
function(n,k) {

 ls1 <- list()                           # generate empty list
 for(i in 1:k) {                        # how could this be done with apply?
    ls1[[i]] <- 0:n                      # fill with 0:n
 }
 allc <- as.matrix(expand.grid(ls1))     # generate all combinations, already using the built in function
 colnames(allc) <- NULL
 index <- (rowSums(allc) == n)       # make index with only the ones that sum to n
 allc[index, ,drop=F]                   # matrix with only the ones that sum to n
 }

推荐答案

除非您回答关于n和k的典型值的问题(请这样做)，否则很难说它是否有用.是使用递归的版本，似乎比josilber使用基准测试更快:

It is hard to tell if it will be useful unless you answer my question regarding your typical values for n and k (please do.) Here is a version using recursion that seems to be faster than josilber's using his benchmark test:

sum.comb3 <- function(n, k) {

   stopifnot(k > 0L)

   REC <- function(n, k) {
      if (k == 1L) list(n) else
      unlist(lapply(0:n, function(i)Map(c, i, REC(n - i, k - 1L))),
             recursive = FALSE)
   }

   matrix(unlist(REC(n, k)), ncol = k, byrow = TRUE)
}

microbenchmark(sum.comb(3, 10), sum.comb2(3, 10), sum.comb3(3, 10))
# Unit: milliseconds
#              expr      min       lq   median       uq      max neval
#  sum.comb2(3, 10) 39.55612 40.60798 41.91954 44.26756 70.44944   100
#  sum.comb3(3, 10) 25.86008 27.74415 28.37080 29.65567 34.18620   100

这篇关于速度总和等于0到n的k个数字的所有组合，速度优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！