image

  • フォト Amazonギフト券
    ※この時計の時刻は、閲覧しているパソコンのものであり、必ずしも正確な時間とは限りません

検索

最近のトラックバック

無料ブログはココログ

« ピックアップ:AndroidとChrome OSはいずれ統合される, スティーブ・ジョブズからのメールはやたら短く簡潔だった, etc... | トップページ | ピックアップ:ノーベル賞・フィールズ賞受賞者による事業仕分けに対する緊急声明, 紀伊国屋書店がポイントサービス開始, etc... »

2009-11-25

Scala の末尾再帰の最適化を確認する

Scala の末尾再帰の最適化を確認してみた。
まず、実験につかったソースコード (java と scala) を示し、それぞれを走らせた結果をします。

$ cat SumJava.java
// See http://d.hatena.ne.jp/unageanu/20080504/1209870210

class SumJava {

    // 1から引数までの総和を計算する関数
    // 末尾再帰でない版
    static long sum( long i ) {   
    return (i == 0) ? i : i + sum(i - 1);
    }

    // 1から引数までの総和を計算する関数
    // 末尾再帰版
    static long sumTailCalls( long i ) {
    return _sumTailCalls( i, 0 );
    }
    static long _sumTailCalls( long i, long total ) {
    return i == 0 ? total  : _sumTailCalls( i - 1, total + i );
    }

    // メイン
    public static void main( String[] args ) {
    long[] params = { 4, 100, 1000, 10000, 100000, 1000000 };

    for(long i : params) {
        try {
        System.out.println( "Sum( " + i + " ) = " + sumTailCalls(i) );
        System.out.println( "Sum( " + i + " ) = " + sum(i) );
        } catch (Throwable th) {
        System.out.println(th.getClass().getName());
        }
    }   
    }
}

$ cat SumScala.scala
// See http://d.hatena.ne.jp/unageanu/20080504/1209870210

object SumScala {
  // 1から引数までの総和を計算する関数
  // 末尾再帰でない版
  def sum( i :Long ) :Long = {
    if ( i == 0 ) i else i + sum(i - 1)
  }

  // 末尾再帰版
  def sumTailCalls( i :Long ) :Long = {
    def _sum( j :Long, total :Long ) :Long = {
      if ( j == 0 ) total else _sum( j - 1, total + j )
    }
    _sum( i, 0 )
  }

  def main(args :Array[String]) {
    val params = List(4, 100, 1000, 10000, 100000, 1000000)
    params.foreach { i =>
      try {
    Console.println( "Sum( " + i + " ) = " + sumTailCalls(i))
    Console.println( "Sum( " + i + " ) = " + sum(i) )
      } catch {
    case th: Throwable => Console.println( th )
      }
    }
  }
}

コンパイルして走らせよう。

$javac SumJava.java
$ java -cp . SumJava

Sum( 4 ) = 10
Sum( 4 ) = 10
Sum( 100 ) = 5050
Sum( 100 ) = 5050
Sum( 1000 ) = 500500
Sum( 1000 ) = 500500
java.lang.StackOverflowError
java.lang.StackOverflowError
java.lang.StackOverflowError

java では 1...10000 以上は再帰呼び出しが深くなりすぎて スタックオーバーフローとなってしまう。
(末尾再帰かどうかには関係なく)

$ scalac SumScala.scala
$ scala SumScala

Sum( 4 ) = 10
Sum( 4 ) = 10
Sum( 100 ) = 5050
Sum( 100 ) = 5050
Sum( 1000 ) = 500500
Sum( 1000 ) = 500500
Sum( 10000 ) = 50005000
java.lang.StackOverflowError
Sum( 100000 ) = 5000050000
java.lang.StackOverflowError
Sum( 1000000 ) = 500000500000
java.lang.StackOverflowError

Scala では、末尾再帰の方法ではスタックオーバーフローが発生せずに 合計計算ができている。

« ピックアップ:AndroidとChrome OSはいずれ統合される, スティーブ・ジョブズからのメールはやたら短く簡潔だった, etc... | トップページ | ピックアップ:ノーベル賞・フィールズ賞受賞者による事業仕分けに対する緊急声明, 紀伊国屋書店がポイントサービス開始, etc... »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/184434/46860223

この記事へのトラックバック一覧です: Scala の末尾再帰の最適化を確認する:

« ピックアップ:AndroidとChrome OSはいずれ統合される, スティーブ・ジョブズからのメールはやたら短く簡潔だった, etc... | トップページ | ピックアップ:ノーベル賞・フィールズ賞受賞者による事業仕分けに対する緊急声明, 紀伊国屋書店がポイントサービス開始, etc... »

mokuji

2013年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

google

  • twitter
  • __
  • _
    Googleボットチェッカー

合わせて読む

  • 合わせて読む
    フィードメーター - katoy: cocolog あわせて読みたい

リンク