आर इस यादृच्छिक क्रमपरिवर्तन समारोह पर धीमा क्यों है?

Question

मैं आर (क्रांति एनालिटिक्स आर) के लिए नया हूँ और आर

में

प्रश्न कुछ मैटलैब कार्यों का अनुवाद किया गया है: क्यों समारोह GRPdur (एन) इतनी धीमी गति से है?

> system.time(GRPdur(10^6)) 
    user system elapsed 
    15.30 0.00 15.32 
> system.time(sample(10^6)) 
    user system elapsed 
    0.03 0.00 0.03 

यहाँ है कि मैं क्या मैटलैब 2011b

>> tic;p = GRPdur(10^6);disp(toc) 
    0.1364 

tic;p = randperm(10^6);disp(toc) 
    0.1116 

में मिलता है:

GRPdur = function(n){ 
# 
# Durstenfeld's Permute algorithm, CACM 1964 
# generates a random permutation of {1,2,...n} 
# 
p=1:n       # start with identity p 
for (k in seq(n,2,-1)){  
    r = 1+floor(runif(1)*k); # random integer between 1 and k 
    tmp = p[k]; 
    p[k] = p[r];    # Swap(p(r),p(k)). 
    p[r] = tmp;     
} 
return(p) 
} 

यहाँ मैं एक Dell प्रेसिजन 690 पर क्या मिलेगा, 2xQuadcore जिऑन 5345 @ 2.33 गीगा, विंडोज 7 64 बिट है

यहाँ है कि मैं क्या मैटलैब 2008a में मिलता है

>> tic;p=GRPdur(10^6);toc 
Elapsed time is 0.124169 seconds. 
>> tic;p=randperm(10^6);toc 
Elapsed time is 0.211372 seconds. 
>> 

---

लिंक: GRPdur RPGlab का हिस्सा है, कि मुझे लगता है कि लिखा Matlab कार्यों का एक पैकेज उत्पन्न करता है और परीक्षण विभिन्न यादृच्छिक क्रमपरिवर्तन जेनरेटर। नोट्स को यहां अलग से देखा जा सकता है: Notes on RPGlab।

मूल Durstenfeld अल्गोल कार्यक्रम here

Answer 1

है क्योंकि आप एक आर-त्वचा

n = 10^6L 
p = 1:n 
system.time(sample(p,n)) 
0.03 0.00 0.03 

Answer 2

दोनों मैटलैब और एस (बाद में आर) FORTRAN कार्यों के आसपास के रूप में पतली रैपर बाहर शुरू कर दिया में एक सी प्रोग्राम लिखा था गणित सामग्री करने के लिए।

एस/आर में फॉर-लूप में "हमेशा" धीमा रहा है, लेकिन यह ठीक रहा है क्योंकि समस्या को व्यक्त करने के आमतौर पर वेक्टरकृत तरीके होते हैं। इसके अलावा, आर में फोरट्रान या सी में हजारों कार्य हैं जो उच्च स्तर की चीजें जल्दी करते हैं। उदाहरण के लिए, sample फ़ंक्शन जो आपके फॉर-लूप करता है - लेकिन बहुत तेज़ी से करता है।

तो फिर मैटलैब स्क्रिप्ट किए गए फॉर-लूप को निष्पादित करने में बहुत बेहतर क्यों है? दो सरल कारण: संसाधन और प्राथमिकताएं।

MATWorks जो MATLAB बनाते हैं, लगभग 2000 कर्मचारियों के साथ एक बड़ी कंपनी है। उन्होंने स्क्रिप्ट के प्रदर्शन में सुधार को प्राथमिकता देने के लिए कई साल पहले फैसला किया था। उन्होंने कंपाइलर विशेषज्ञों का एक समूह किराए पर लिया और जस्ट-इन-टाइम कंपाइलर (जेआईटी) विकसित करने में सालों बिताए जो स्क्रिप्ट कोड लेते हैं और इसे असेंबलर कोड में बदल देते हैं। उन्होंने भी बहुत अच्छा काम किया। उन्हें कुडोस!

आर खुला स्रोत है, और आर कोर टीम अपने खाली समय में आर को बेहतर बनाने पर काम करती है। आर कोर के ल्यूक टियरनी ने कड़ी मेहनत की है और आर के लिए एक कंपाइलर पैकेज विकसित किया है जो आर स्क्रिप्ट को बाइट कोड में संकलित करता है। हालांकि यह इसे असेंबलर कोड में नहीं बदलता है, लेकिन बहुत अच्छी तरह से काम करता है। उसके लिए कुडोस!

... लेकिन प्रयास की मात्रा आर संकलक बनाम MATLAB संकलक में डाल बस बहुत कम है, और इसलिए परिणाम है धीमी:

system.time(GRPdur(10^6)) # 9.50 secs 

# Compile the function... 
f <- compiler::cmpfun(GRPdur) 
system.time(f(10^6)) # 3.69 secs 

आप देख सकते हैं, के लिए लूप बाइट कोड को संकलित करके 3x तेज हो गया। एक और अंतर यह है कि आर जेआईटी कंपाइलर डिफ़ॉल्ट रूप से सक्षम नहीं है क्योंकि यह MATLAB में है।

अद्यतन बस रिकॉर्ड, एक से थोड़ा अधिक अनुकूलित आर संस्करण (नुथ एल्गोरिथ्म के आधार पर) है, जहां यादृच्छिक पीढ़ी के रूप में @joran सुझाव vectorized कर दिया गया है के लिए:

f <- function(n) { 
    p <- integer(n) 
    p[1] <- 1L 
    rv <- runif(n, 1, 1:n) # random integer between 1 and k 
    for (k in 2:n) {  
    r <- rv[k] 
    p[k] = p[r]   # Swap(p(r),p(k)). 
    p[r] = k 
    } 
    p 
} 
g <- compiler::cmpfun(f) 
system.time(f(1e6)) # 4.84 
system.time(g(1e6)) # 0.98 

# Compare to Joran's version: 
system.time(GRPdur1(10^6)) # 6.43 
system.time(GRPdur2(10^6)) # 1.66 

... अभी भी एक परिमाण MATLAB से धीमी है। लेकिन फिर, बस sample या sample.int का उपयोग करें जो स्पष्ट रूप से MATLAB के randperm को 3x द्वारा धड़कता है!

system.time(sample.int(10^6)) # 0.03 

Answer 3

ओपी के अनुरोध का जवाब देते हुए भी एक टिप्पणी में लंबा होने के कारण था, तो यहाँ है कि मैं क्या करने के लिए बात कर रहे थे है:

#Create r outside for loop 
GRPdur1 <- function(n){ 
    p <- 1:n       
    k <- seq(n,2,-1) 
    r <- 1 + floor(runif(length(k)) * k) 
    for (i in 1:length(k)){  
     tmp <- p[k[i]]; 
     p[k[i]] <- p[r[i]];     
     p[r[i]] <- tmp;     
    } 
return(p) 
} 

library(compiler) 
GRPdur2 <- cmpfun(GRPdur1) 

set.seed(1) 
out1 <- GRPdur(100) 

set.seed(1) 
out2 <- GRPdur1(100) 

#Check the GRPdur1 is generating the identical output 
identical(out1,out2) 

system.time(GRPdur(10^6)) 
    user system elapsed 
12.948 0.389 13.232 
system.time(GRPdur2(10^6)) 
    user system elapsed 
1.908 0.018 1.910 

नहीं काफी 10x, लेकिन 3x टॉमी की तुलना में अधिक बस का प्रयोग करके बताया संकलक। कुछ हद तक एक और अधिक सटीक समय के लिए:

library(rbenchmark) 
benchmark(GRPdur(10^6),GRPdur2(10^6),replications = 10) 
      test replications elapsed relative user.self sys.self 
1 GRPdur(10^6)   10 127.315 6.670946 124.358 3.656   
2 GRPdur2(10^6)   10 19.085 1.000000 19.040 0.222 

तो 10x टिप्पणी था (शायद आश्चर्य की बात नहीं, एक भी system.time रन के आधार पर किया जा रहा) आशावादी है, लेकिन vectorization आप क्या बाइट संकलक करता है पर एक निष्पक्ष थोड़ा और अधिक गति लाभ ।