Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to remove an element in NumericVector for a recursion using R and Rcpp

i was trying to learn more about how to use Rcpp package for R. So i started testing basic sorting algorithms using Rcpp. I was starting at Hadley Wickham tutorial here.

I successfully implemented insertion sort recursively this way:

library(Rcpp)

vetor<-sample(100)
vetor
cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
        double aux;
        int i;

        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

But the function ask for 2 arguments, then i tried this way:

cppFunction("
    NumericVector insertionsortRC(NumericVector vetor) {
        int n = vetor.size();

        double aux;
        int i;

        if(n>1) {
            vetor.erase(n-1);
            insertionsortRC(vetor);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

I think erase was not a good idea here, it seem that i erase the element from memory and cant recover it later, after the recursion call. I thought also that the problem could be on vetor.erase(n-1); line, tried vetor.erase(n); and it compiled, but didn't work at all.

With vetor.erase(n); i got the following error in R:

insertionsortRC(vetor) * Error in `/usr/lib/R/bin/exec/R': malloc(): memory corruption: 0x098db548 *

with vetor.erase(n-1); it got a strange output:

insertionsortRC(vetor) [1] 3.607393e-313 3.300000e+01 3.100000e+01 8.600000e+01 2.500000e+01 7.000000e+01 [7] 4.000000e+01 8.800000e+01 8.100000e+01 1.300000e+01 8.500000e+01 8.700000e+01 [13] 3.900000e+01 6.000000e+01 6.400000e+01 1.000000e+01 8.200000e+01 8.900000e+01 [19] 1.400000e+01 6.600000e+01 3.600000e+01 1.500000e+01 9.600000e+01 2.600000e+01 [25] 4.000000e+00 5.400000e+01 2.900000e+01 8.300000e+01 5.500000e+01 6.800000e+01 [31] 9.100000e+01 6.000000e+00 1.000000e+02 5.100000e+01 7.000000e+00 5.300000e+01 [37] 9.900000e+01 6.500000e+01 2.300000e+01 9.400000e+01 5.700000e+01 9.000000e+01 [43] 3.200000e+01 4.700000e+01 1.600000e+01 5.000000e+01 2.800000e+01 3.000000e+00 [49] 9.800000e+01 1.100000e+01 1.800000e+01 7.600000e+01 6.300000e+01 7.700000e+01 [55] 7.400000e+01 4.900000e+01 8.000000e+00 9.700000e+01 1.200000e+01 2.700000e+01 [61] 3.500000e+01 7.900000e+01 8.000000e+01 2.000000e+01 6.700000e+01 9.300000e+01 [67] 5.000000e+00 5.600000e+01 9.000000e+00 3.700000e+01 2.400000e+01 9.200000e+01 [73] 6.900000e+01 3.800000e+01 4.400000e+01 1.700000e+01 4.600000e+01 4.300000e+01 [79] 3.400000e+01 1.900000e+01 2.000000e+00 9.500000e+01 7.200000e+01 1.000000e+00 [85] 6.100000e+01 4.100000e+01 6.200000e+01 2.200000e+01 4.200000e+01 2.100000e+01 [91] 8.400000e+01 4.800000e+01 7.800000e+01 7.300000e+01 3.000000e+01 5.900000e+01 [97] 5.800000e+01 5.200000e+01 7.500000e+01

Could someone tell me if: 01. Is it possible to implement this code, like this, using Rcpp and R, calling the function with only one argument, the vector of data? 02. How to do it correctly?

like image 270
Augusto Ribas Avatar asked Oct 19 '13 23:10

Augusto Ribas


3 Answers

Briefly:

  1. The good news is that you have your compilation working.

  2. The not-so-good news is the segfault. Likely a logic error in your code.

  3. In general, adding or removing to NumericVector etc is a bad idea. These are shallow types which directly connect to the R memory of the same object ("no copies"). This means extending or removing is costly. Consider using an STL std::vector<double>. All this is documented.

like image 72
Dirk Eddelbuettel Avatar answered Oct 21 '22 04:10

Dirk Eddelbuettel


A few things:

vetor.erase(n) is undefined behavior. The first index is 0, the last is n-1. erase does not do bounds check because everybody would have to pay the price. Instead it assumes, as it is common in the C++ world that the function is used correctly.

Learn about std::sort. it is likely to be more efficient than home backed sort implementation, especially insertion sort.

Rcpp vectors have a sort method. So a NumericVectorcan sort itself.

Learn about attributes, i.e. with the Rcpp-attributes vignette, this is simpler to use and this will give you a way to deal with default arguments.

like image 25
Romain Francois Avatar answered Oct 21 '22 05:10

Romain Francois


Try: vector.erase(vector.begin()+desiredElement)

That should take care of your problem.

The NumericVector type seems to be related to std::vector at least in the way it handles insertion and removal of data, which means that you have to use iterators (However, I am not an Rcpp guru).

Brian

like image 1
user1809770 Avatar answered Oct 21 '22 05:10

user1809770