[Rcpp-devel] What is the most efficient method to check if a Rcpp vector contains an element?

Romain Francois romain at r-enthusiasts.com
Tue Dec 31 16:47:57 CET 2013


In any case, for things like this the best thing to do is to not trust what anyone says and actually benchmark with realistic data. 


Le 31 déc. 2013 à 16:29, Hadley Wickham <h.wickham at gmail.com> a écrit :

>> I believe you are mistaken. sorting is an expensive O( N log(N) ) operation.
>> I’d use something like std::find (or std::any_of if you use C++11). Those
>> are O(N)
>> Otherwise, you might like Rcpp::any or Rcpp::any_of
> It depends on the scenario - if you want to look up M values in a
> vector of length N, then sorting + binary search will be O(M log(N) +
> N log(N)) where scanning each time will be O(MN). If M = 1, there's no
> point presorting, but if it's large, it pays to sort first.
> Hadley
> -- 
> http://had.co.nz/

More information about the Rcpp-devel mailing list