[R] efficient rolling rank

zerdna azege at yahoo.com
Sun Apr 18 17:51:09 CEST 2010

Gabor, Charles, Whit -- i've been walking the woods of R alone so far, and i
got to say that your replies to that trivial question are eye-opening
experience for me. Gentlemen, what i am trying to say in a roundabout way is
that i am extremely grateful and that you guys are frigging awesome.

Let me outline the times i am getting for different proposed solutions on
the same machine, same data, same version of R

x<-rnorm(50000); len<-100

1. my naive  roll.rank

user    system    elapsed
6.405   0.488       6.94

2. Gabor's zoo

system.time(rollapply(z,len, function(x) rank(x)[len]))
user    system    elapsed
6.195    0.361      6.554

3. Charles embed

 system.time(x.rank <- rowSums(x[ -(1:(len-1)) ] >= embed(x,len) )) 
user    system    elapsed
0.181    0.055      0.236

4. Whit's fts
system.time(x.rank<-moving.rank(dat, len))
user    system    elapsed
0.036      0           0.036

5. Charles suggestion with inline, my crude implementation

sig<-signature(x="numeric", rank="integer", n="integer", len="integer")
code<-"int k=0; for(int i=*len-1; i< *n; i++) {int r=1; for(int j=i-1; j>
i-len;j--) r+=(x[i]>x[j] ?1:0); rank[k++]<-r;}"
fns<-cfunction(sig,code, convention=".C")

system.time( x.rank<-fns(x, numeric(length(x)-len), length(x), len))

user    system    elapsed
0.011    0               0.011

I guess i could speed it up from time being proportional  to length(x)*len
to time proportional to length(x)*log(len) if i use slightly more
intelligent algo, but this works fine for my requirements. Only thing i
really wonder about is why  exactly R takes 640 times more than this C code.
It would be immensely enlightening if someone could point to an explanation
of how execution in R works and where and when it slows down like this. 
View this message in context: http://n4.nabble.com/efficient-rolling-rank-tp2013535p2014922.html
Sent from the R help mailing list archive at Nabble.com.

More information about the R-help mailing list