2011年11月17日

「関数型は再帰関数めちゃめちゃ使うよ」と聞いて心配になる事(in Scala)

「関数型は再帰関数めちゃめちゃ使うよ」と聞いて心配になる事(in Scala)

C,C++,Javaとかをメインとしてやってる人が関数型について

「関数型は変数の値変更を良しとしない言語だから再帰関数を多用するよー」

って聞くと、即座に思い浮かぶ懸念は、

1.えっ、再帰関数多用って関数呼び出しコストどうするのよ?重いよねそれ?
2.えっ、再帰関数多用すると何処でスタックオーバーフローするか分からないし怖いよ。

だと思うんですよ(私はそうでした)。 Scalaは関数型も書ける言語なのでどうなのかというと結論からいうと

「大丈夫。気にすんな」

です。 Scalaでは「末尾再帰の最適化」がサポートされています。再帰関数の最後で自分自身を呼び出すようにすればコンパイル時に最適化されるのです(単純にwhileみたいに置き換えられる)。 ですので、

・関数呼び出しコスト
・スタックオーバーフロー

は大丈夫なのです。

論より証拠。 

◆テストコード1
単純に数値カウントアップするだけ

非再帰

var i = 0
while(i <= high){
i += 1
}

再帰

def countUp(now: Int,high: Int):Int={
if(now <= high) countUp(now+1, high) else now
}
val i = countUp(0,high)


◆テストコード2
下限値(low)から上限値(high)までの合計値を求めるコード

非再帰

var sum = 0
var i = low
while(i <= high){
sum += i
i += 1
}
println("sum="+sum)

再帰

def sumRange(sum: Int,now: Int,high: Int):Int={
if(now <= high) sumRange(sum+now,now+1,high) else sum
}
val sum = sumRange(0,low,high)
println("sum="+sum)



で、ベンチマーク取ってみる

object CompRecursive{
import scala.testing.Benchmark
def main(args:List[String]){
//カウントアップバージョン
test1(100000000)
//合計計算バージョン
test2(0,100000000)
}
//テスト1:ただのカウントアップ
def test1(high: Int){
println("countUp")
val benchmarkNoRecursive = new Benchmark{
def run={
var i = 0
while(i <= high){
i += 1
}
println("count="+i)
}}
println("非再帰関数バージョン処理時間="+benchmarkNoRecursive.runBenchmark(1)(0)+"(/ms)")
val benchmarkRecursive = new Benchmark{
def run={
def countUp(now: Int,high: Int):Int={
if(now <= high) countUp(now+1, high) else now
}
val i = countUp(0,high)
println("count="+i)
}}
println("再帰関数バージョン処理時間="+benchmarkRecursive.runBenchmark(1)(0)+"(/ms)")
}
//テスト2:合計求める
def test2(low: Int,high: Int){
println("calculate sum")
val benchmarkNoRecursive = new Benchmark{
def run={
var sum = 0
var i = low
while(i <= high){
sum += i
i += 1
}
println("sum="+sum)
}}
println("非再帰関数バージョン処理時間="+benchmarkNoRecursive.runBenchmark(1)(0)+"(/ms)")
val benchmarkRecursive = new Benchmark{
def run={
def sumRange(sum: Int,now: Int,high: Int):Int={
if(now <= high) sumRange(sum+now,now+1,high) else sum
}
val sum = sumRange(0,low,high)
println("sum="+sum)
}}
println("再帰関数バージョン処理時間="+benchmarkRecursive.runBenchmark(1)(0)+"(/ms)")
}
}
CompRecursive.main(List(""))

私の環境だとこうなった

countUp
count=100000001
非再帰関数バージョン処理時間=93(/ms)
count=100000001
再帰関数バージョン処理時間=63(/ms)


calculate sum
sum=987459712
非再帰関数バージョン処理時間=141(/ms)
sum=987459712
再帰関数バージョン処理時間=110(/ms)

マジかよ再帰使ったほうが速いっ。


posted by purigen at 00:00| Comment(1) | TrackBack(0) | Scala | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
newbie on xxx(scala,iphone,objective-c,ajax,javascript,html and more...): 「関数型は再帰関数めちゃめちゃ使うよ」と聞いて心配になる事(in Scala)
Posted by gucci 店 at 2013年07月21日 12:45
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。