3

私は Project Euler を実行して、計算効率の高いプログラムを作成しようとしています。問題 1 を考えてみましょう: http://projecteuler.net/problem=1。非効率性を強調するために、範囲を 1000 から 10,000,000 に増やしました。

これが私の解決策です：

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% の時間を費やしていることを示しています。これをより速く行うためのベクトル化された方法はありますか?

二次的な懸念は、メモリが不足することです。このアプローチは、範囲が大きくなるにつれてあまりスケーラブルではありません。ベクトル化可能性を維持しながら、サブセットをメモリに保持しようとしない、これを行う良い方法はありますか?

4

3 に答える 3

7

Modulo is faster when it operates on integers and not numerics:

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

That's still far from C++ performance, but it's a step in the right direction.

于 2012-07-24T04:18:03.477 に答える
4

より迅速なソリューション

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-24T04:59:44.023 に答える
2

[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置き換えました。sequnique

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-24T04:04:20.180 に答える