Rcpp Power Set 实现：尝试在 SET_VECTOR_ELT 中设置索引 8/8

Question

考虑将一组元素作为输入向量和 returns 列表中幂集的函数：

> pwr_set(letters[1:3])

[[1]]
character(0)

[[2]]
[1] "a"

[[3]]
[1] "b"

[[4]]
[1] "a" "b"

[[5]]
[1] "c"

[[6]]
[1] "a" "c"

[[7]]
[1] "b" "c"

[[8]]
[1] "a" "b" "c"

R定义：

pwr_set <- function(els){
  n_els <- length(els)
  out <- vector(mode="list",length = 2 ^ n_els)
  out[[1]] <- character()     # first element in power set is the empty set

  listIdx <- 1L       # start a listIdx

  for(i in 1L:n_els){
    for(j in 1L:listIdx){
      listIdx <- listIdx + 1L
      out[[listIdx]] <- c(out[[j]], els[i])
    }
  }
  out
}

我想出了以下翻译来在 Rcpp 中实现：

#include <Rcpp.h>
#include <Math.h>
using namespace Rcpp;


// [[Rcpp::export]]
List pwr_set_cpp(CharacterVector els) {

  int n_els = els.size();         // size of set
  int pwrset_card = pow(2,n_els); // number of subsets to make power set is 2^n_elements
  List out(pwrset_card);          // list for output
  int listidx = 0;                // to count through list indeces
  out[0] = CharacterVector::create(); // first element of list represents empty set
  CharacterVector tmp;            // to hold new extended vector

  for (int i=0; i < n_els; ++i) {
    for (int j=0; j <= listidx; ++j) {

      listidx++;
      tmp = out[j];
      tmp.push_back(els[i]);
      out[listidx] = tmp;

    }
  }
  return out;
}

但是！

> pwr_set_cpp(letters[1:3])

给我错误：attempt to set index 8/8 in SET_VECTOR_ELT

谷歌搜索和查看源代码 here 让我认为我正在尝试索引超出 SET_VECTOR_ELT 缓存的内容？这一定意味着我误解了如何在 Rcpp 或类似的东西中逐步执行 input/output 循环。

任何帮助我理解这里的指导都会很棒。提前致谢。

更新：修复。

根据@Romain Francois 和@nicola 的 answer/comments ，关键的误解是你在 R 中单步执行循环的方式有点聪明！（或者至少我现在比以前更欣赏它）。要在 c++ 中实现相同的功能，我必须将 listidx 分解为一个 counter 变量（这是 j 的条件检查）和一个临时变量 cnt2 它基本上记录了 j 在当前计数器状态 之上采取的步数。 counter 然后在通过每个出口后更新为 cnt2 的当前值。

#include <Rcpp.h> #include <Math.h> using namespace Rcpp; // [[Rcpp::export]] List pwr_set_cpp(CharacterVector els) { int n_els = els.size(); int pwrset_card = pow(2,n_els); List out(pwrset_card); out[0] = StringVector::create(); CharacterVector tmp; int counter = 0; for (int i=0; i < n_els; ++i) { int cnt2 = counter; // capture counter state for (int j =0; j <= counter; ++j) { cnt2++; // capture counter + j steps tmp = as<StringVector>(out[j]); tmp.push_back(as<std::string>(els[i])); out[cnt2] = tmp; } counter = cnt2; // update counter state } return out; }

快速计时

只是为了好玩一个小基准。虽然我确信有更有效的方法来做到这一点（使用相同的算法结构），因为我正在做很多 STRSXP elements/vectors 的复制。

x <- letters[1:18] pwr_set_bitecompile <- compiler::cmpfun(pwr_set) # R 3.2.0 ! microbenchmark::microbenchmark( pwr_set(x), pwr_set_bitecompile(x), pwr_set_cpp(x)) Unit: milliseconds expr min lq mean median uq max neval pwr_set(x) 748.6553 820.0667 841.2828 834.1229 856.2436 1023.1324 100 pwr_set_bitecompile(x) 365.9969 480.9474 498.2100 503.5115 518.8562 596.8205 100 pwr_set_cpp(x) 155.9447 283.8771 295.8411 300.4865 314.0826 342.0261 100

Answer 1

问题是您正试图将某些内容分配给 out[8]，而这超出了列表中的元素数量。

查看此添加的行：

  Rprintf( "out.size() = %d, listidx = %d\n", out.size(), listidx );
  out[listidx] = tmp;

您将获得：

> pwr_set_cpp(letters[1:3])
out.size() = 8, listidx = 1
out.size() = 8, listidx = 2
out.size() = 8, listidx = 3
out.size() = 8, listidx = 4
out.size() = 8, listidx = 5
out.size() = 8, listidx = 6
out.size() = 8, listidx = 7
out.size() = 8, listidx = 8
Error in pwr_set_cpp(letters[1:3]) :
  tentative de modification de l'index 8/8 dans SET_VECTOR_ELT
Calls: sourceCpp ... withVisible -> eval -> eval -> pwr_set_cpp -> <Anonymous>
Exécution arrêtée

另请参阅@nicola 的评论。您对 listidx 和 j 做错了什么。如果溢出没有阻止它，你就会陷入无限循环。

可能令人困惑的是 R 代码：

for(j in 1L:listIdx){
  listIdx <- listIdx + 1L
  out[[listIdx]] <- c(out[[j]], els[i])
}

计算 1L:listIdx 一次，因此在循环内，您可以使用 listIdx 做其他事情。在 C++ 中不是这种情况。

Rcpp Power Set 实现：尝试在 SET_VECTOR_ELT 中设置索引 8/8

Rcpp Power Set implementation : attempt to set index 8/8 in SET_VECTOR_ELT

r

rcpp

我想出了以下翻译来在 Rcpp 中实现：

但是！

更新：修复。

快速计时