読者です 読者をやめる 読者になる 読者になる

餡子付゛録゛

ソフトウェア開発ツールの便利な使い方を紹介。

Rで解くFizzBuzz問題

R言語

前のエントリーでFizzBuzz問題がもっと速くなるのでは無いかと指摘したら、“エレガントではないけどと速いコード”を書いて頂けたので、他のコードとあわせて紹介したいと思います。遅い順に合計7種類。

1. @kos59125 氏 Type I

@kos59125 氏が説明用に示したオーソドックスなコードです(Rで解くFizzBuzz問題)。C言語等で実装すると、それなりの速度が出るパターンですが、Rでは遅いです。

fb1<-function(n){
  fb<-character(n)
  for(i in 1:n){
    if(i%%3==0&&i%%5==0)
      fb[i]<-"FizzBuzz"
    else
      if(i%%3==0)
        fb[i]<-"Fizz"
    else
      if(i%%5==0)
        fb[i]<-"Buzz"
    else
      fb[i]<-i
  }
  fb
}

2. @kos59125 氏 Type II

@kos59125 氏が説明用に示したapply関数を使ってみたパターンのようです(Rで解くFizzBuzz問題)。(1)より高速ですが、もっと高速化が可能です。

fb2<-function(n){
  sapply(1:n,function(i){
    if(i%%3==0&&i%%5==0)
      "FizzBuzz"
    else if(i%%3==0)
      "Fizz"
    else if(i%%5==0)
      "Buzz"
    else
      i
  })
}

3. @kos59125 氏 Type III

高速版として紹介されていたコードです(Rで解くFizzBuzz問題)。ややトリッキーですが、rep()を使って剰余演算なしにしている所が改良に思えます。しかし、まだ高速化できます。

fb3<-function(n){
  isFizz<-rep(c(F,F,T),length=n)
  isBuzz<-rep(c(F,F,F,F,T),length=n)
  isNumber<-!isFizz&!isBuzz
  fizz<-ifelse(isFizz,"Fizz","")
  buzz<-ifelse(isBuzz,"Buzz","")
  number<-ifelse(isNumber,1:n,"")
  paste(fizz,buzz,number,sep="")
}

4. 裏 RjpWiki 短縮コード

ワンライナーになっていた、裏 RjpWikiの短縮版コードです(R らしく FizzBuzz)。ベクトル演算ですが、C言語スカラー演算みたいにあっさりしていますね。

fb4 <- function(n){
  i <- 1:n
  ifelse(i %% 15 == 0, "FizzBuzz", ifelse(i %% 3 == 0, "Fizz", ifelse(i %% 5 == 0, "Buzz", i)))
}

5. uncorrelatedパターン

私が速度的に改良してみたコードです。(4)からifelse()を減らしてみたパターンが「RでFizzBuzz問題を高速化」だったのですが、まだifelse()が残っていたのでそれを削ります。

fb5 <- function(n){
  i <- 1:n
  l <- c(0, "Fizz", "Buzz", "FizzBuzz")
  ii <- (0==i%%5)*2 + (0==i%%3)*1 + 1
  r <- l[ii]; ns <- which(1==ii); r[ns] <- ns; r
}

6. 裏 RjpWiki 高速コード

速度的ならより高速にできると裏 RjpWikiの人が指摘してくれたコードです(R らしいかもしれないがエレガントではない FizzBuzz)。条件演算やループ処理が無いので高速です。またr[1:(l%/%3)*3]は、r[0==i%%3]とするより高速になるようです。

fb6 <- function(n){
  r <- 1:n
  l <- length(r)
  r[1:(l%/%3)*3] <- "Fizz"
  r[1:(l%/%5)*5] <- "Buzz"
  r[1:(l%/%15)*15] <- "FizzBuzz"
  r
}

なお1:(l%/%3)*3はseq(3,l,3)と書き直すと遅くなります。Rは速度的に実行してみるまで分からない所が多いですね。

7. 裏 RjpWiki 変態チック版

マニアックに改良がされていたので、追記します(もっと変態チックな FizzBuzz)。

fb7 <- function(limit){
  ans3 <- rep(c("d", "d", "Fizz", "d", "Buzz", "Fizz",
 "d", "d", "Fizz", "Buzz", "d", "Fizz",
 "d", "d", "FizzBuzz"), ceiling(limit/15))[1:limit]
  temp <- ans3=="d"
  ans3[temp]<- which(temp)
  return(ans3)
}

3と5と15の最小公倍数が15である事を利用しているのと、3と5の倍数で無い位置にdを配置し、which関数を使って後で置き換えているのが特色です。which関数の使いどころを初めて見た気がします。

8. ベンチマーク

100万回、ループしてみて速度を比較してみました。(6)がやはり高速です。添字のために大量の配列を作っているわけですが、ループ演算とifelse()のオーバーヘッドを考慮すると、微々たるコストしかないようです。

N <- 1000000
gc();gc();system.time({ fb1(N) })
gc();gc();system.time({ fb2(N) })
gc();gc();system.time({ fb3(N) })
gc();gc();system.time({ fb4(N) })
gc();gc();system.time({ fb5(N) })
gc();gc();system.time({ fb6(N) })
gc();gc();system.time({ fb7(N) })

fb1 fb2 fb3 fb4 fb5 fb6 fb7
11.08秒 10.36秒 4.39秒 5.52秒 0.87秒 0.79秒 0.58秒