Skip to content

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

3 messages · Asis Hallab, Romain Francois, Dirk Eddelbuettel

Original
Asis Hallab
# 
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!
Romain Francois
# 
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 :
Dirk Eddelbuettel
#
On 23 July 2014 at 15:30, Asis Hallab wrote:
| 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?

Why don't you time / profile both and pick the faster one?

Profiling is generally a good idea.  Bottlenecks are sometimes seen in
corners you least suspected.

Dirk