image

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

検索

最近のトラックバック

無料ブログはココログ

« 2009年11月24日 | トップページ | 2009年11月26日 »

2009年11月25日

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...

Ainomukidashi

今日は 新文芸座で "愛のむきだし" の上映だ。 http://www.shin-bungeiza.com/schedule.html#d1123

- http://news.cocolog-nifty.com/cs/article/detail/magazine-200911241000/1.htm
> 小西真奈美 脱・癒し系? ココログニュース:@nifty

- http://news.livedoor.com/article/detail/4466603/
> 【エンタがビタミン♪】「いつも下着姿」。親太朗が明かした姉・山田優の仰天私生活。 - livedoor ニュース

- http://blog.livedoor.jp/kazu_fujisawa/archives/51618276.html
> 金融日記:JALって日本という国の縮図だね・・・

- http://d.hatena.ne.jp/noiehoie/20091124/1259075328
> 学生よ! もっと暴れろ!!  - 麻布論壇

- http://japanese.engadget.com/2009/11/24/android-chrome-os-/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+engadgetjp+%28Engadget+Japanese%29
> AndroidとChrome OSはいずれ統合される。たぶん(Google創業者セルゲイ・ブリン)

- http://blog.goo.ne.jp/gan_chan_kadoya/e/6470ff75afb3d3dec01b348d08cebc03
> 国立国会図書館における書籍・雑誌のデジタル化の取組 - マッコリはカルピスです。

- http://www.lifehacker.jp/2009/11/091124time_machine.html
> 「Time Machine」をもう一歩使いやすくするには : ライフハッカー[日本版], 仕事も生活も上手くこなすライフハック情報満載のブログ・メディア

- http://www.yasuhisa.com/could/article/why-email-is-still-the-king/
> メールがこれからも残り続ける理由 : could

- http://www.itmedia.co.jp/news/articles/0911/24/news064.html
> B&Nの電子書籍リーダー「Nook」、予想以上の人気で売り切れに - ITmedia News

- http://yaplog.jp/ha-chu0122/archive/1281
> 全然悔しくなんて無い。-〜はあちゅう主義。〜

- http://gigazine.net/index.php?/news/comments/20091124_jobs_mail/
> スティーブ・ジョブズからのメールはやたら短く簡潔だった - GIGAZINE

- http://blogs.technet.com/ime/archive/2009/11/24/IME_C130FC30E0306E30E5652C679E8A065290679230397DCB4E57307E3059300230_.aspx
> IME : IMEチームの日本語分析を紹介します。

- http://it.blog-jiji.com/0001/2009/11/post-b1a2.html
> 湯川鶴章のIT潮流 powered by ココログ: ソーシャルメディアのマネタイズ方法が見えてきた。ということは、そろそろ最終ラウンドか

- http://d.hatena.ne.jp/nowokay/20091123#1258955562
> TwitterはGoogleの長期的な目標をすでに達成し、Googleには不可能なことを実現している

« 2009年11月24日 | トップページ | 2009年11月26日 »

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 あわせて読みたい

リンク