C++ версия оператора% in% в R

Question

Есть ли какая-либо функция в C++, эквивалентная оператору %in% в R? Рассмотрим приведенную ниже команду в R:

which(y %in% x) 

Я пытался найти что-то эквивалент в C++ (в частности, в Armadillo), и я не мог ничего найти. Затем я написал свою собственную функцию, которая очень медленная по сравнению с приведенной выше командой R.

Вот что я писал:

#include <RcppArmadillo.h> 
// [[Rcpp::depends("RcppArmadillo")]] 

// [[Rcpp::export]] 
arma::uvec myInOperator(arma::vec myBigVec, arma::vec mySmallVec){ 
arma::uvec rslt = find(myBigVec == mySmallVec[0]); 
for (int i = 1; i < mySmallVec.size(); i++){ 
    arma::uvec rslt_tmp = find(myBigVec == mySmallVec[i]); 
    rslt = arma::unique(join_cols(rslt, rslt_tmp)); 
} 
return rslt; 
} 

Теперь после поиска в коде выше, мы имеем:

x <- 1:4 
y <- 1:10 
res <- benchmark(myInOperator(y, x), which(y %in% x), columns = c("test", 
     "replications", "elapsed", "relative", "user.self", "sys.self"), 
     order = "relative") 

И вот результаты:

    test replications elapsed relative user.self sys.self 
2 which(y %in% x)   100 0.001  1  0.001  0 
1 myInOperator(y, x)   100 0.002  2  0.001  0 

Может кто-нибудь подскажите мне либо найти код C++, соответствующий которому (y% в% x), либо сделать мой код более эффективным? Истекшее время для обеих функций уже очень мало. Я предполагаю, что я имею в виду, по эффективности, больше от перспективы программирования и от того, насколько эффективен способ, которым я думал о проблеме, и используемые мной команды.

Я ценю вашу помощь.

Answer 1

EDIT: Благодаря @MatthewLundberg и @Yakk, чтобы поймать мои глупые ошибки.

Если вам действительно нужно только ускорить поиск, вы должны проверить пакет Simon Urbanek's fastmatch. Тем не менее, Rcpp действительно имеет сахару функцию in, которую можно использовать здесь. in использует некоторые идеи из пакета fastmatch и включает их в Rcpp. Я также сравниваю решение @ hasley.

// [[Rcpp::plugins("cpp11")]] 
#include <Rcpp.h> 
using namespace Rcpp; 

// [[Rcpp::export]] 
std::vector<int> sugar_in(IntegerVector x, IntegerVector y) { 
    LogicalVector ind = in(x, y); 
    int n = ind.size(); 
    std::vector<int> output; 
    output.reserve(n); 
    for (int i=0; i < n; ++i) { 
    if (ind[i]) output.push_back(i+1); 
    } 
    return output; 
} 

// [[Rcpp::export]] 
std::vector<int> which_in(IntegerVector x, IntegerVector y) { 
    int nx = x.size(); 
    std::unordered_set<int> z(y.begin(), y.end()); 
    std::vector<int> output; 
    output.reserve(nx); 
    for (int i=0; i < nx; ++i) { 
    if (z.find(x[i]) != z.end()) { 
     output.push_back(i+1); 
    } 
    } 
    return output; 
} 


// [[Rcpp::export]] 
std::vector<int> which_in2(IntegerVector x, IntegerVector y) { 
    std::vector<int> y_sort(y.size()); 
    std::partial_sort_copy (y.begin(), y.end(), y_sort.begin(), y_sort.end()); 

    int nx = x.size(); 
    std::vector<int> out; 

    for (int i = 0; i < nx; ++i) { 
    std::vector<int>::iterator found = 
     lower_bound(y_sort.begin(), y_sort.end(), x[i]); 
    if (found != y_sort.end()) { 
     out.push_back(i + 1); 
    } 
    } 
    return out; 
} 

/*** R 
set.seed(123) 
library(microbenchmark) 
x <- sample(1:100) 
y <- sample(1:10000, 1000) 
identical(sugar_in(y, x), which(y %in% x)) 
identical(which_in(y, x), which(y %in% x)) 
identical(which_in2(y, x), which(y %in% x)) 
microbenchmark(
    sugar_in(y, x), 
    which_in(y, x), 
    which_in2(y, x), 
    which(y %in% x) 
) 
*/ 

Вызов sourceCpp на это дает мне, из теста,

Unit: microseconds 
      expr min  lq median  uq max neval 
    sugar_in(y, x) 7.590 10.0795 11.4825 14.3630 32.753 100 
    which_in(y, x) 40.757 42.4460 43.4400 46.8240 63.690 100 
which_in2(y, x) 14.325 15.2365 16.7005 17.2620 30.580 100 
which(y %in% x) 17.070 21.6145 23.7070 29.0105 78.009 100 

Answer 2

Для этого множества входов, мы можем зарабатывать себе немного больше производительности при использовании такого подхода, который технически имеет более высокую алгоритмическую сложность (O (ln n) vs O (1) для каждого поиска), но имеет более низкие константы: двоичный поиск.

// [[Rcpp::plugins("cpp11")]] 
#include <Rcpp.h> 
using namespace Rcpp; 

// [[Rcpp::export]] 
std::vector<int> which_in(IntegerVector x, IntegerVector y) { 
    int nx = x.size(); 
    std::unordered_set<int> z(y.begin(), y.end()); 
    std::vector<int> output; 
    output.reserve(nx); 
    for (int i=0; i < nx; ++i) { 
    if (z.find(x[i]) != z.end()) { 
     output.push_back(i+1); 
    } 
    } 
    return output; 
} 

// [[Rcpp::export]] 
std::vector<int> which_in2(IntegerVector x, IntegerVector y) { 
    std::vector<int> y_sort(y.size()); 
    std::partial_sort_copy (y.begin(), y.end(), y_sort.begin(), y_sort.end()); 

    int nx = x.size(); 
    std::vector<int> out; 

    for (int i = 0; i < nx; ++i) { 
    std::vector<int>::iterator found = 
     lower_bound(y_sort.begin(), y_sort.end(), x[i]); 
    if (found != y_sort.end()) { 
     out.push_back(i + 1); 
    } 
    } 
    return out; 
} 

/*** R 
set.seed(123) 
library(microbenchmark) 
x <- sample(1:100) 
y <- sample(1:10000, 1000) 
identical(which_in(y, x), which(y %in% x)) 
identical(which_in2(y, x), which(y %in% x)) 
microbenchmark(
    which_in(y, x), 
    which_in2(y, x), 
    which(y %in% x) 
) 
*/ 

На моем компьютере, что дает

Unit: microseconds 
      expr min lq median uq max neval 
    which_in(y, x) 39.3 41.0 42.7 44.0 81.5 100 
which_in2(y, x) 12.8 13.6 14.4 15.0 23.8 100 
which(y %in% x) 16.8 20.2 21.0 21.9 31.1 100 

так около 30% лучше, чем базовый R.