r - Rcpp Power Set implementation : attempt to set index 8/8 in SET_VECTOR_ELT -
consider function takes set of elements input vector , returns power set in list:
> 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 definition:
pwr_set <- function(els){ n_els <- length(els) out <- vector(mode="list",length = 2 ^ n_els) out[[1]] <- character() # first element in power set empty set listidx <- 1l # start listidx for(i in 1l:n_els){ for(j in 1l:listidx){ listidx <- listidx + 1l out[[listidx]] <- c(out[[j]], els[i]) } } out }
i have come following translation implement in 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 make power set 2^n_elements list out(pwrset_card); // list output int listidx = 0; // count through list indeces out[0] = charactervector::create(); // first element of list represents empty set charactervector tmp; // hold new extended vector (int i=0; < n_els; ++i) { (int j=0; j <= listidx; ++j) { listidx++; tmp = out[j]; tmp.push_back(els[i]); out[listidx] = tmp; } } return out; }
but!
> pwr_set_cpp(letters[1:3])
gives me error: attempt set index 8/8 in set_vector_elt
googling , looking @ source code here leads me think trying index beyond set_vector_elt
has cached? must mean mis-understand how step through input/output loops in rcpp
or of sort.
any guidance in helping me understand here wonderful. ahead of time.
update: fix.
as per answer/comments @romain francois , @nicola key misunderstanding way step through loops in r
sorta clever! (or @ least appreciate more before). implement same thing in c++
have break listidx
counter
variable (which condition check j
) , interim cnt2
records number of j
steps taken on top of current counter state. counter
gets updated after passing each exit current value of 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; (int i=0; < n_els; ++i) { int cnt2 = counter; // capture counter state (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; }
quick timings
just fun little benchmark. although i'm sure there more efficient ways (with same algorithm structure) i'm doing lot of copying of 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
the problem trying assign out[8]
, that's above number of elements in list.
see added line:
rprintf( "out.size() = %d, listidx = %d\n", out.size(), listidx ); out[listidx] = tmp;
you'll get:
> 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
see comment @nicola. you're doing wrong listidx
, j
. if overflow did not stop it, you'd endless loop.
what's confusing r code:
for(j in 1l:listidx){ listidx <- listidx + 1l out[[listidx]] <- c(out[[j]], els[i]) }
evaluates 1l:listidx
once, inside loop, can use listidx
else. that's not case in c++.
Comments
Post a Comment