CODEWITHSUNDEEP
rrcpp
DanY
DanY

Reputation: 6073

Rcpp max of vector except one element

In Rcpp I want to find the maximum of a vector, but I want to omit one element.

I have working code, but I'm sure my approach is quite bad as it involves the full copy of the vector. Is there a much better way to accomplish what I want?

In R:

vec <- 1:10
ele <- 3
max(vec[-ele])

My (terrible) version in Rcpp:

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
double my_fun(NumericVector vec, int ele) {
    NumericVector vec_no_ele = clone(vec);
    vec_no_ele.erase(ele);
    return max(vec_no_ele);
}

Upvotes: 1

Views: 591

Answers (3)

thc
thc

Reputation: 9705

Under the hood, max is implemented as a humble for loop. You shouldn't shy away from for loops in c++ since there is much less overhead compared to R. In this case, a for loop does significantly better than using the built in:

// Coatless answer:
// [[Rcpp::export]]
double max_no_copy(NumericVector vec, int ele) {
  double temp = vec[ele-1];
  vec[ele-1] = vec[0];
  double result_max = max(vec);
  vec[ele-1] = temp;
  return result_max;
}

// humble for loop
// [[Rcpp::export]]
double max_except_for(NumericVector vec, int ele) {
  int vs = vec.size();
  double res = 0;
  for(int i=0; i<vs; i++) {
    if( i == ele-1 ) continue;
    if(vec[i] > res) res = vec[i];
  }
  return res;
}

R side:

x <- rnorm(1e8)
x[1000] <- 1e9
microbenchmark(max_except_for(x, 1000), max_no_copy(x, 1000), times=5)

Unit: milliseconds
                    expr       min        lq     mean    median       uq       max neval cld
 max_except_for(x, 1000)  87.58906  93.56962  92.5092  93.59754  93.6262  94.16361     5  a 
    max_no_copy(x, 1000) 284.46662 292.57627 296.3772 296.78390 300.5345 307.52455     5   b


identical(max_except_for(x, 1000), max_no_copy(x, 1000)) # TRUE

Upvotes: 1

DanY
DanY

Reputation: 6073

The answer from @coatless is great and builds on the other generous commenters above. However, it can be further generalized. @coatless uses the value in vec[0] as the placeholder for the value to be omitted, but this fails when the value to be omitted is element 0!

Here's a slightly generalized solution, where I use the adjacent element to ele as the placeholder, and I check that ele is in the index of vec and that vec.length() is greater than 1:

// calculate the max of a vector after omitting one element
double max_except(NumericVector vec, int ele) {
    if (vec.length() == 1) stop("vec too short");
    if (ele < 0 | ele > vec.length()-1) stop("ele out of range");
    double temp = vec[ele];
    int idx = (ele > 0) ? ele-1 : ele+1;
    vec[ele] = vec[idx];
    double res = max(vec);
    vec[ele] = temp;
    return res;
}

Upvotes: 1

coatless
coatless

Reputation: 20746

@Spacemen is suggesting the following approach in comments:

Save the value you want to omit in a temp variable. Set that element to zero or some small value or the same as another value in the vector. Compute the max. Reset the element from the temp variable.

This would be implemented like so:

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
double max_no_copy(NumericVector vec, int ele) {
  double temp = vec[ele];

  // Use a value already in vector
  vec[ele] = vec[0];

  // Find max value
  double result_max = max(vec);

  // Remove NA value
  vec[ele] = temp;

  return result_max;
}

Test:

vec <- 1:10
ele <- 2 # C++ indices start at 0 not 1. So, subtract.

max_no_copy(vec, ele)
# [1] 10

Benchmark to be added later...

Upvotes: 1

Related Questions