在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中更快的模或平等检查（或矢量化的好方法）

回答

相关问题