[Rcpp-devel] Faster lookup: Named Rcpp::List or std::map?

Romain Francois romain at r-enthusiasts.com
Wed Jul 23 16:01:12 CEST 2014


Lookup in Rcpp::List is linear on something that is quite cheap (comparing pointers, because strings in R are cached). 

Lookup in std::map is logarithmic on whatever it means to compare the keys (so in your case comparing strings). 
on top of that, copying the data across is linear in the best case scenario (when the data is already sorted) or N log(N) otherwise. See: http://www.cplusplus.com/reference/map/map/map/

Best is to try both and see which is best for your case. Don't make this just one dimensional and consider things like maintainability of your code, ...

Romain

Le 23 juil. 2014 à 15:30, Asis Hallab <asis.hallab at gmail.com> a écrit :

> Dear Rcpp-Experts,
> 
> trying to optimize my algorithm I face the question wether a lookup by
> a string key like e.g.
> 
> myRcppList( "my_entry" ) is as fast as the lookup in std::maps?
> 
> That said, would you recommend converting myRcppList to a std::map
> before searching it?
> 
> Thank you for your help in advance!
> Cheers!




More information about the Rcpp-devel mailing list