Optimized Solution for Finding Nearest Previous Higher Element in Vectors Using Rcpp

Based on the provided code, it appears that you’re trying to find the nearest previous higher element in a vector of numbers. The approach you’ve taken so far is not efficient and will explode for large inputs.

Here’s an optimized solution using Rcpp:

cppFunction('
  List pge(NumericVector rowid, NumericVector ask) {
    int n = rowid.size();
    
    std::vector&lt;int&gt; stack;
    std::vector&lt;NumericReal&gt; prevHigherAsk(n, NA_REAL);
    std::vector&lt;double&gt; diff(n, 0.0);
    
    for(int i = 0; i &lt; n; i++) {
      double currentAsk = ask[i];
      
      while(!stack.empty() && currentAsk >= ask[stack.back()]) {
        stack.pop_back();
      }
      
      if(!stack.empty()) {
        int prevIndex = stack.back();
        
        prevHigherAsk[i] = ask[prevIndex];
        diff[i] = prevHigherAsk[i] - currentAsk;
      }
      
      stack.push_back(i);
    }
    
    return List::create(
      Named("rowid_prevHi") = rowid[stack],
      Named("ask_prevHi") = prevHigherAsk,
      Named("difference_from_previous_higher") = diff
    );
  }
')

# usage in R
pge_r <- function(d) {
  res <- pge(d$rowid, d$ask)
  d$rowid_prevHi <- as.integer(res$rowid_prevHi)
  d$ask_prevHi <- res$ask_prevHi
  d$difference_from_previous_higher <- res$difference_from_previous_higher
  d
}

This solution uses a stack-based approach to efficiently find the nearest previous higher element in O(n) time complexity. The pge function takes two input vectors, rowid and ask, and returns three output vectors: rowid_prevHi, ask_prevHi, and difference_from_previous_higher.

Note that I’ve used std::vector to manage memory efficiently in C++. Also, I’ve replaced the R code with a more concise version.

Please test this solution and provide feedback if you need further optimization or improvements.

Last modified on 2023-08-23