在R中更快的模或平等檢查（或矢量化的好方法）

我一直在試圖編寫計算效率高的項目。考慮問題1：http://projecteuler.net/problem=1。我將範圍從1000增加到了10,000,000，以突出低效率。在R中更快的模或平等檢查（或矢量化的好方法）

這是我的解決方案：

system.time({ 
    x <- 1:1E7 
    a <- sum(as.numeric(x[x%%3 ==0 | x%%5==0])) 
}) 
user system elapsed 
0.980 0.041 1.011

下面是一個朋友做同樣的事情，寫了一些C++代碼。

#include <iostream> 
using namespace std; 

int main(int argc, char** argv) 
{ 
long x = 0; 
for (int i = 1; i < 10000000; i++) 
{ 
    if (i % 3 == 0) 
    x += i; 
    else if (i % 5 == 0) 
    x += i; 
} 
cout << x; 
return 0; 
} 
cbaden$ time ./a.out 
23333331666668 
real 0m0.044s 
user 0m0.042s 
sys  0m0.001s

我知道C++應該是除了R快，但這更快？ Rprof表示我用模運算符將近60％的時間花費在模運算符上，13％的時間用「==」運算。有沒有更快的矢量化方法？

次要的問題是我將耗盡內存 - 隨着範圍變大，此方法的可擴展性不高。有沒有一種好方法可以保持矢量化，但不會試圖將子集保留在內存中？

來源

2012-07-24 Christopher Aden

一個更快的解決方案

x <-1E7 
a<-x%/%3 
b<-x%/%5 
c<-x%/%15 
ans<-3*a*(a+1)/2+5*b*(b+1)/2-15*c*(c+1)/2

並沒有真正與問候模

來源

2012-07-24 04:59:44 shhhhimhuntingrabbits

哇，真是太瘋狂了！我無法真正理解它在做什麼。 n（n + 1）/ 2將是從1到n的總和，但我想我不明白爲什麼這會起作用。 – 2012-07-24 05:46:02

它可能無法幫助模，但是一個奇妙的優雅的解決方案！ – mnel 2012-07-24 06:02:06

a是可以被3整除的值的數量，並且假設我們做出一系列（1,2,3，...，a）。乘以3得到（3，6，9，...，1E9），數字可以被3整除。使用這個捷徑公式sum_ {i = 1}^ai = a（a + 1）/ 2只需要我們知道一個，而不是整個陣列。將所有可以被3整除的矢量1，...，a整除，將整個事物乘以3.對於5和15，同樣的邏輯，但是我們減去15-可分的向量以避免重複計算。即使在非常大的範圍內，我的電腦也能立即運行。美麗。 – 2012-07-24 06:17:08

略有改善[關於OP]

system.time({ 
    x_3 <- seq(3, 1E7, by = 3) 
    x_5 <- seq(5, 1E7, by = 5) 
    x_3_5 <- unique(c(x_3, x_5)) 
    a <- sum(as.numeric(x_3_5))} 
) 
## user system elapsed 
## 1.53 0.13 1.66

EDIT曾使用profr到分析代碼和替換seq和unique與內部泛型/默認方法。

new2 <- function(){ 
    x_3 <- seq.int(3, 1E7, by = 3) 
    x_5 <- seq.int(5, 1E7, by = 5) 
    x_3_5 <- unique.default(c(x_3, x_5)) 
    a <- sum(as.numeric(x_3_5)) 
    } 

system.time(new2()) 
## user system elapsed 
## 1.11 0.04 1.16

爲了比較（我的機器很慢）：

system.time({ 
    x <- 1:1E7 
    a <- sum(as.numeric(x[x %% 3 == 0 | x %% 5 == 0])) 
}) 

## user system elapsed 
## 4.47 0.18 4.64

標杆

orig <- function(){ 
    x <- 1:1E7 
    a <- sum(as.numeric(x[x %% 3 == 0 | x %% 5 == 0])) 
} 

new <- function(){ 
    x_3 <- seq(3, 1E7, by = 3) 
    x_5 <- seq(5,1 E7, by = 5) 
    x_3_5 <- unique(c(x_3, x_5)) 
    a <- sum(as.numeric(x_3_5)) 
} 

benchmark(orig(), new(), new2(), replications = 5) 
##  test replications elapsed relative 
## 2 new()   5 7.67 1.198438  
## 3 new2()   5 6.40 1.000000  
## 1 orig()   5 22.01 3.439063

來源

2012-07-24 04:04:20 mnel

幫助我喜歡你的使用seq.int的想法。我喜歡你增加了3或5.它完全避免了需要使用模數。 – 2012-07-24 05:47:02

模速度更快，當它運行在integer秒且不numeric S：

f1 <- function() { 
    x <- 1:1E7 
    a <- sum(as.numeric(x[x%%3 ==0 | x%%5==0])) 
} 

f2 <- function() { 
    x <- 1:1E7 
    a <- sum(as.numeric(x[x %% 3L == 0L | x %% 5L == 0L])) 
} 

library(rbenchmark) 
benchmark(f1(), f2(), replications = 5) 
# test replications elapsed relative user.self sys.self user.child sys.child 
# 1 f1()   5 14.78 4.976431  13.95  0.67   NA  NA 
# 2 f2()   5 2.97 1.000000  2.37  0.50   NA  NA

這仍然遠離C++性能，但它是朝着正確方向邁出的一步。

來源

2012-07-24 04:18:03 flodel

在R中更快的模或平等檢查（或矢量化的好方法）

回答

相關問題