M.Hiroi's Home Page

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home | 2015 年 1 月 5 月 6 月 7 月 12 月 ]
2015 年 12 月

12月31日

●大晦日

今年も残りわずかとなりました。M.Hiroi's Home Page を開設してから 15 年が過ぎましたが、ここまで続けることができるとは M.Hiroi も思っていませんでした。これもひとえに M.Hiroi's Home Page に来てくださる皆様のおかげです。本当にありがとうございました。来年の事を言えば鬼が笑うといいますが、これからも M.Hiroi's Home Page の更新を続けることができればいいなあ、と思っております。

それでは、きたるべき年も皆様にとってよいお年でありますように。

12月12日

●パズルの解答

12 月 5 日 に出題したパズルの解答です。

12月5日

●パズルに挑戦

今回は簡単な数理パズルを出題します。プログラムを作って解いてもかまいませんが、筆算 (電卓) で解くことができる問題もあるので、興味のある方は挑戦してみてください。

  1. 1000000 以下の自然数で、3 の倍数になっている数字の和を求めてください。
  2. 10000! の末尾に付く 0 の個数を求めてください。
  3. 7654321 の末尾の数字を求めてください。
  4. 将棋盤の１ずつのマスに米粒を置きます。最初のマスへは１粒、次のマスへは２粒、そのつぎのマスへは４粒というようにして、つぎつぎに倍増していきます。最後のマス (81 マス) まで置き終わったときの米粒の総数を求めてください。
-- 参考文献 --------
1. Steven G. krantz (著), 関沢正躬 (訳), 『問題解決への数学』, 丸善, 2001
2. 中村義作, 『どこまで解ける日本の算法』, ブルーバックス, 1994
3. 大村平, 『数学公式のはなし』, 日科技連, 1996

●解答１

今のパソコンは高性能なので、次のようにプログラムしても瞬時に答えを求めることができます。使用するプログラミング言語は Scheme (Gauche) です。 

リスト : 1 から n までの整数で m の倍数の和を求める

(define (sum-of-multiples n m)
  (let loop ((i 1) (a 0))
    (cond ((= i n) a)
          ((zero? (mod i m))
           (loop (+ i 1) (+ a i)))
          (else (loop (+ i 1) a)))))

gosh> (sum-of-multiples 1000000 3)
166666833333

ところが、数列の和を求める公式を使うと、もっと簡単に答えを求めることができます。 

1 + 2 + 3 + ... + n = n(n + 1)/ 2

上記公式より n 個の 3 の倍数の和は 3 + 6 + 9 + ... + 3n = 3n(n + 1) / 2 となります。したがって、1000000 以下の 3 の倍数の和は 1 から (floor (/ 1000000 3)) = 333333 までの和を 3 倍することで求めることができます。 

3 * 333333 * (333333 + 1) / 2 = 166666833333

これをプログラムすると次のようになります。 

リスト : 1 から n までの整数で m の倍数の和を求める (2)

(define (sum-of-multiples-1 n m)
  (let ((i (floor (/ n m))))
    (/ (* m i (+ i 1)) 2)))

gosh> (sum-of-multiples-1 10000000 3)
16666668333333

●等差数列の和

次のように、一定の差で並んだ数列を「等差数列」といいます。 

a, a + d, a + 2d, a + 3d, ..., a + (n - 1)d

a を「初項」、d を「公差」といいます。等差数列の一般項は次の式で表すことができます。 

an = a + (n - 1)d

初項から an までの和 Sn は次の式で求めることができます。 

Sn = n(2a + (n - 1)d) / 2

初項を 1, 公差 を 1 とすると、1 から n までの和は n(n + 1)/ 2 となります。

この公式は次のように導出することができます。 

Sn = a              + (a + d)        + ,,, + (a + (n - 2)d) + (a + (n - 1)d)
Sn = (a + (n - 1)d) + (a + (n - 2)d) + ... + (a + d)        + a

足し算すると

2Sn = (2a + (n - 1)d) + (2a + (n - 1)d) + ... (2a + (n - 1)d) + (2a + (n - 1)d)
2Sn = n(2a + (n - 1)d)
 Sn = n(2a + (n - 1)d)/2

このように、右辺を逆順に並べ替えて足し算すると、2a + (n - 1)d が n 個並ぶことになります。あとは、これを 2 で割り算すればいいわけです。

●解答２

10000! であれば、次のようなプログラムでも瞬時に答えを求めることができます。 

リスト : n! の後ろに付く 0 の個数を求める

(define (fact n)
  (if (zero? n)
      1
    (* n (fact (- n 1)))))

(define (solver n)
  (let loop ((m (fact n)) (a 0))
    (if (not (zero? (modulo m 10)))
        a
      (loop (/ m 10) (+ a 1)))))

gosh> (solver 10000)
2499

単純に n! を求めて、10 で割れる回数を求めているだけです。ところが、この方法では n が大きくなると極端に遅くなります。多倍長整数の場合、除算や余りを求める処理は乗算よりもはるかに時間がかかります。たとえば、1 桁増やした 100000! の場合、階乗の値は短時間で求めることができても、(modulo m 10) の回数が増えることにより実行時間が極端に遅くなるのです。

そこで、他の方法を考えてみましょう。階乗を計算するとき、末尾に 0 が付くのは値を 10 倍したときです。これは数字 10 や 100 を乗算するときだけではありません。次の例を見てください。 

1 = 1
1 * 2 = 2
1 * 2 * 3 = 6
1 * 2 * 3 * 4 = 24
1 * 2 * 3 * 4 * 5 = 120
1 * 2 * 3 * 4 * 5 * 6 = 720
1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320 
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 = 362880 
1 * 2 * 3 * 4 * 5 * 6 * 7  * 8 * 9 * 10 = 3628800

10 は 2 * 5 に素因数分解することができます。つまり、2 と 5 の組があれば、末尾に 0 がひとつ追加されるわけです。また、0 が複数追加されることもあります。次の例を見てください。 

24! = 620448401733239439360000
25! = 15511210043330985984000000

25 は 5 * 5 と素因数分解することができます。このとき、2 * 5 の組が 2 つできるので、末尾に 0 が 2 つ付くわけです。階乗を素因数分解したとき、因数 2 の個数は因数 5 の個数よりも多くなるので、2 と 5 は必ず組にすることができます。つまり、因数 5 の個数が末尾に付く 0 の 個数になるわけです。

階乗の場合、因数の個数を求めるのは簡単です。10000! の場合、10000 / 5 で 5 の倍数の個数 2000 を求めることができます。次に、25 (= 5 * 5) の倍数の個数を 10000 / 25 で求めます。さらに、125 (= 5 * 5 * 5) の倍数の個数を 10000 / 125 で求めます、これを 10000 > 5m が成立する m まで繰り返し、その総和が 5 の因子の個数になります。 

10000 / 5    = 2000
10000 / 25   =  400
10000 / 125  =   80
10000 / 625  =   16
10000 / 3125 =    3.2 (小数点切捨て)
----------------------
        合計 = 2499

プログラムと実行結果を示します。 

リスト : n! の後ろに付く 0 の個数を求める (2)

(define (solver-1 n)
  (let loop ((m 5) (a 0))
    (if (> m n)
        a
      (loop (* m 5) (+ a (floor (/ n m)))))))

10^1 : 2
10^2 : 24
10^3 : 249
10^4 : 2499
10^5 : 24999
10^6 : 249998
10^7 : 2499999
10^8 : 24999999
10^9 : 249999998
10^10: 2499999997

●解答３

Gauche の場合、ちょっと時間がかかりますが、次のように簡単に求めることができます。 

gosh> (mod (expt 7 654321) 10)
7

この問題は筆算で簡単に求めることができます。7n (n > 0) の末尾の数字は次のように 7, 9, 3, 1, ... と巡回します。 

7^1 = 7
7^2 = 49
7^3 = 343
7^4 = 2401
7^5 = 16807
7^6 = 117649
7^7 = 823543
7^8 = 5764801

ここで、74 の末尾は 1 になることに注目してください。末尾が 1 の数字を何回乗算しても、その結果の末尾は 1 になります。7654321 は (74)163580 * 7 なので、末尾の数字は 7 と求めることができます。

●解答４

米粒の合計値は 1 + 2 + 22 + 23 + ... + 280 になります。これを素直にプログラムすると次のようになります。 

リスト : 米粒の合計値

(define (solver n)
  (let loop ((m 0) (a 0))
    (if (= m n)
        a
      (loop (+ m 1) (+ a (expt 2 m))))))

gosh> (solver 81)
2417851639229258349412351

とても大きな数になるので、普通の電卓では計算できません。Windows の電卓を使用するときは関数電卓に切り替えてください。もちろん、数学の公式を使うともっと簡単に求めることができます。

●等比数列の和

次のように、一定の比で並んだ数列を「等比数列」といいます。 

a, ar, ar2, ..., arn-1, ...

a を「初項」、d を「公比」といいます。等比数列の一般項は次の式で表すことができます。 

an = arn-1

初項から an までの和 Sn は次の式で求めることができます。 

Sn = a(1 - rn) / (1 - r)

問題は初項 1 で公比 2 なので、米粒の合計は次のようになります。 

(1 - 281) / (1 - 2) = 281 - 1

gosh> (- (expt 2 81) 1)
2417851639229258349412351

この公式は次のように導出することができます。 

Sn = a + ar + ar2 + ... + arn-1
両辺を r 倍すると
rSn =    ar + ar2 + ... + arn-1 + arn
これを引き算すると
Sn - rSn = a - arn => Sn = a(1 - rn) / (1 - r)

右辺を引き算すると ar から arn-1 の項がなくなって、a - arn だけになります。あとは、1 - r で割り算すればいいわけです。

2015 年 7 月

7月20日

●末尾最適化

末尾再帰のお話です。末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call) 」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。

このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization) 」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。

また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization) 」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰最適化を行う処理系があります。なかには Scheme のように、言語仕様に末尾最適化を行うことを明記しているプログラミング言語もあります。最近では、Ｃ言語 (gcc や clang など) でも末尾最適化が可能になっています。

簡単な例を示しましょう。 

リスト : 階乗 (facti.c)

int fact(int n, int a)
{
  if (n == 0) {
    return 1;
  } else {
    return fact(n - 1, a * n);
  }
}

$ gcc -O -S facti.c

mhiroi@mhiroi-VirtualBox:~/clang$ cat facti.s
	.file	"facti.c"
	.text
	.globl	fact
	.type	fact, @function
fact:
.LFB0:
	.cfi_startproc
	subl	$12, %esp
	.cfi_def_cfa_offset 16
	movl	16(%esp), %edx
	movl	20(%esp), %ecx
	movl	%ecx, %eax
	testl	%edx, %edx
	je	.L2
	subl	$8, %esp
	.cfi_def_cfa_offset 24
	imull	%edx, %ecx
	pushl	%ecx
	.cfi_def_cfa_offset 28
	subl	$1, %edx
	pushl	%edx
	.cfi_def_cfa_offset 32
	call	fact
	addl	$16, %esp
	.cfi_def_cfa_offset 16
.L2:
	addl	$12, %esp
	.cfi_def_cfa_offset 4
	ret
	.cfi_endproc
.LFE0:
	.size	fact, .-fact
	.ident	"GCC: (Ubuntu 4.9.2-10ubuntu13) 4.9.2"
	.section	.note.GNU-stack,"",@progbits

gcc の場合、最適化オプションに -O を指定すると末尾最適化は行われません。fact を関数呼び出し (call fact) していることがわかります。-O2 を指定すると末尾最適化が行われます。 

$ gcc -O2 -S facti.c

	.file	"facti.c"
	.section	.text.unlikely,"ax",@progbits
.LCOLDB0:
	.text
.LHOTB0:
	.p2align 4,,15
	.globl	fact
	.type	fact, @function
fact:
.LFB0:
	.cfi_startproc
	movl	4(%esp), %edx
	movl	8(%esp), %eax
	testl	%edx, %edx
	je	.L2
	.p2align 4,,10
	.p2align 3
.L3:
	imull	%edx, %eax
	subl	$1, %edx
	jne	.L3
.L2:
	rep ret
	.cfi_endproc
.LFE0:
	.size	fact, .-fact
	.section	.text.unlikely
.LCOLDE0:
	.text
.LHOTE0:
	.ident	"GCC: (Ubuntu 4.9.2-10ubuntu13) 4.9.2"
	.section	.note.GNU-stack,"",@progbits

fact を関数呼び出しするのではなく、条件分岐命令 jne .L3 を使ってループに変換されていることがわかります。

次のような相互再帰も最適化することができます。 

リスト : 相互再帰 (testr.c)

/* 関数宣言 */
int odd(int);
int even(int);

int even(int n)
{
  if (n == 0) {
    return 1;
  } else {
    return odd(n - 1);
  }
}

int odd(int n)
{
  if (n == 0) {
    return 0;
  } else {
    return even(n - 1);
  }
}

	.file	"testr.c"
	.section	.text.unlikely,"ax",@progbits
.LCOLDB0:
	.text
.LHOTB0:
	.p2align 4,,15
	.globl	even
	.type	even, @function
even:
.LFB0:
	.cfi_startproc
	movl	4(%esp), %edx
	movl	$1, %eax
	testl	%edx, %edx
	je	.L2
	xorb	%al, %al
	cmpl	$1, %edx
	jne	.L4
.L2:
	rep ret
	.p2align 4,,10
	.p2align 3
.L4:
	subl	$2, %edx
	je	.L12
	cmpl	$1, %edx
	jne	.L4
	xorl	%eax, %eax
	ret
	.p2align 4,,10
	.p2align 3
.L12:
	movl	$1, %eax
	ret
	.cfi_endproc
.LFE0:
	.size	even, .-even
	.section	.text.unlikely
.LCOLDE0:
	.text
.LHOTE0:
	.section	.text.unlikely
.LCOLDB1:
	.text
.LHOTB1:
	.p2align 4,,15
	.globl	odd
	.type	odd, @function
odd:
.LFB1:
	.cfi_startproc
	movl	4(%esp), %eax
	testl	%eax, %eax
	jne	.L15
	xorl	%eax, %eax
	ret
	.p2align 4,,10
	.p2align 3
.L15:
	subl	$1, %eax
	movl	%eax, 4(%esp)
	jmp	even
	.cfi_endproc
.LFE1:
	.size	odd, .-odd
	.section	.text.unlikely
.LCOLDE1:
	.text
.LHOTE1:
	.ident	"GCC: (Ubuntu 4.9.2-10ubuntu13) 4.9.2"
	.section	.note.GNU-stack,"",@progbits

関数 even は関数 odd を呼び出す処理をループに展開し、関数 odd で even を呼び出す処理は無条件ジャンプ命令 jmp に変換されています。このように、末尾最適化が行われると、関数呼び出しの処理がジャンプや繰り返しに変換されることがわかります。最近のＣコンパイラはとても優秀ですね。興味のある方はいろいろ試してみてください。

7月11日

●祝！ M.Hiroi's Home Page 開設十五周年

M.Hiroi's Home Page を開設してから 15 年になりました。15 年間も続けることができたのは、M.Hiroi's Home Page に来てくださる皆様のおかげです。厚くお礼申しあげます。

これを期に、Web ページの記述を HTML4 + shift_jis から HTML5 + utf-8 に変更しました。何か不具合があればメールにてご連絡いただけると助かります。

これからもがんばりますので、今後ともよろしくお願い申しあげます。

2015 年 6 月

6月20日

●Underscore.js

JavaScript のお話です。Underscore.js は DocumentCloud と Jeremy Ashkenas 氏が開発している JavaScript で作成されたライブラリです。Underscore.js は軽量なライブラリですが、100 以上もの関数が定義されているので、とても便利に使用することができます。また、map, filter, reduce など関数型言語でお馴染みの高階関数も多数用意されています。

Underscore.js は次のページからダウンロードすることができます。

Development Version と Production Version (underscore-min.js) がありますが、ライブラリとして必要なのは underscore-min.js だけです。あとは、HTML ファイルと同じディレクトリにコピーして、HTML ファイルのスクリプトタグで読み込むだけです。 

リスト : underscore-min.js の読み込み

<!DOCTYPE html>
<html lang="ja">
<head>
  <meta charset="UTF-8">
  <title>お気楽 Underscore.js 超入門</title>
</head>
<body>
  <script src="underscore-min.js"></script>
  <script>
    console.log(_.VERSION);
  </script>
</body>
</html>

unserscore-min.js を読み込むと、アンダースコア ( _ ) というオブジェクトが生成されます。このオブジェクトに便利な関数 (メソッド) などが多数定義されています。あとは、<script> と </script> の間に JavaScript のプログラムを記述するだけで、Underscore.js を試してみることができます。たとえば、_.VERSION は Underscore.js のバージョンを格納しているプロパティです。M.Hiroi の環境でこのプログラムを実行すると、Web ブラウザの JavaScript コンソールに 1.8.3 と表示されます。

Node.js で使用する場合は npm で簡単にインストールすることができます。 

npm install underscore

この場合、Underscore.js はカレントディレクトリにインストールされます。プログラムの実行は同じディレクトリで行ってください。このとき、require('underscore') で Underscore.js を読み込むことができます。ただし、REPL で実行する場合、変数 _ には直近の実行結果がセットされるので、require の結果を他の変数 (たとえば _u とか __ など) にセットしてください。 

> 1 + 2
3
> _
3
> var _u = require('underscore')
undefined
> _
undefined

あとは、_ のかわりに _u を使って Underscore.js の関数を REPL で使用することができます。簡単な実行例を示しましょう。 

> _u.VERSION
'1.8.3'
>> _u.map([1,2,3,4,5], function(x) { return x * x; })
[ 1, 4, 9, 16, 25 ]
> _u.filter([1,2,3,4,5], function(x) { return x % 2 == 0; })
[ 2, 4 ]
> _u.reduce([1,2,3,4,5], function(a, n) { return a + n; }, "")
'12345'
> _u.reduce([1,2,3,4,5], function(a, n) { return a + n; }, 0)
15
> _u.reduce([1,2,3,4,5], function(a, n) { return a + n; }, "")
'12345'
> _u.reduceRight([1,2,3,4,5], function(a, n) { return a + n; }, "")
'54321'

このほかにも、便利な関数が多数用意されているので、興味のある方はいろいろ試してみてください。

6月6日

●Node.js と babel

JavaScript のお話です。古川さんの記事 で紹介されているトランスパイラ babel で「末尾再帰最適化」を試してみたかったので、Node.js をインストールしました。

Node.js は JavaScript で Web アプリケーションを作成するためのプラットフォームです。JavaScript エンジンは Google Chrome の V8 が使われています。Node.js を使って Web サーバーを構築し、そこでアプリケーションを動作させます。Apache など従来のサーバーに比べて、大量のリクエストを高速にさばくことができるそうです。

M.Hiroi は Node.js の機能をほとんど理解していませんが、REPL (Read-Eval-Print-Loop) が用意されているので、コマンドラインで高速に動作する JavaScript 処理系として使ってみるのも面白そうです。Node.js は次のページからダウンロードすることができます。

Windows 用のインストーラーが用意されているので、簡単にインストールすることができます。

Node.js をインストールすると、npm というパッケージマネージャもいっしょにインストールされます。Node.js で使用するモジュールやコマンドは npm を使って簡単にインストールやアンインストールすることができます。babel は次のコマンドでインストールすることができます。 

C>npm install -g babel

babel の使い方ですが、コマンド babel で ECMAScript2015 (今後 ES6 と略記) で書かれた JavaScript ファイルを ES5 に変換します。すぐに実行したい場合はコマンド babel-node を使ってください。

それでは簡単な例題として、1 から n までの和を求める関数 sum_rec を末尾再帰でプログラムしてみましょう。 

リスト : 1 から n までの和を求める

function sum_rec(n, a) {
  if (n == 0) return a;
  return sum_rec(n - 1, a + n);
}

console.log(sum_rec(100000, 0));

このプログラムを node で実行するとスタックオーバーフローします。 

C>node test.js
C>test.js:1
n (exports, require, module, __filename, __dirname) { function sum_rec(n, a) {
                                                                      ^
RangeError: Maximum call stack size exceeded
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:1:79)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)
    at sum_rec (C:\Users\m_hiroi\WORK\JS\test.js:3:10)

babel-node で実行すると末尾再帰最適化により、答えを求めることができます。 

C>babel-node test.js
5000050000

プログラムは babel により次のように変換されます。 

リスト : 変換結果

"use strict";

function sum_rec(_x, _x2) {
  var _again = true;

  _function: while (_again) {
    var n = _x,
        a = _x2;
    _again = false;

    if (n == 0) return a;
    _x = n - 1;
    _x2 = a + n;
    _again = true;
    continue _function;
  }
}

console.log(sum_rec(100000, 0));

末尾再帰が繰り返し (while ループ) に変換されていることがわかります。

ただし、次のような相互再帰は最適化されないようです。 

リスト : 相互再帰

function odd(n) {
    if (n == 0) return false;
    else return even(n - 1);
}

function even(n) {
    if (n == 0) return true;
    else return odd(n - 1);
}

また、末尾再帰最適化された場合でも、実行速度が速くなるとは限りません。たらいまわし関数を node と babel で試してみました。 

リスト : たらいまわし関数 (tak.js)

function tak(x, y, z) {
    if(x <= y) return z;
    return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
}

function test(x, y, z) {
    var s = new Date().getTime();
    console.log(tak(x, y, z));
    var e = new Date().getTime();
    console.log(e - s);
}

C>node tak.js
11
3525

C>babel-node tarai.js
11
3615

babel-node のほうが少し遅くなるようです。トランスパイラで末尾再帰最適化を効率的に実装するのは難しいのかもしれませんね。興味のある方はいろいろ試してみてください。また、今後は JavaScript エンジンに末尾再帰最適化が実装されていくでしょうが、どのくらい速くなるのか楽しみにしたいと思います。

2015 年 5 月

5月16日

●ECMAScript6

JavaScript のお話です。Rubyist Magazine 0050 号 の 古川さんの記事 によると、ECMAScript2015 (旧 ECMAScript6) は 『今年の 6 月に公式に次の ECMAScript として仕様が公開されます。』 とのことです。

詳細は古川さんの記事を読んでもらうとして、M.Hiroi が興味を持ったのは「末尾呼び出し最適化」です。JavaScript は関数型言語からいろいろな機能を取り込んではいますが、Python や Ruby と同じくオブジェクト指向スクリプト言語であって関数型言語ではありません。繰り返しであれば for 文や while 文を使うことがほとんどでしょう。

ところが、再帰的なデータ構造やアルゴリズムを取り扱う場合、繰り返しよりもやっぱり再帰呼び出しのほうが素直にプログラムできる場合があります。このようなとき、末尾呼び出しが最適化されると、末尾再帰はループに変換されるので、プログラムを効率的に実行することができます。Web ブラウザが新しい仕様に対応するのはまだまだ先の話でしょうが、今後は JavaScript に注目しようと思っています。

●たらいまわし関数

ところで、Google Chrome に搭載されている JavaScript エンジン (V8) はとても速いといわれています。そこで、実際に拙作のページ Algorithms with Python 再帰定義 の「たらいまわし関数」で実行速度を比較してみました。 

リスト : たらいまわし関数 (tak.js)

function tak(x, y, z) {
    if(x <= y) return z;
    return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
}

function test(x, y, z) {
    var s = new Date().getTime();
    console.log(tak(x, y, z));
    var e = new Date().getTime();
    console.log(e - s);
}

HTML ファイルで JavaScritp プログラムが書かれたファイルを読み込む場合は、script タグで次のように指定します。 

リスト : tak.js の実行

<!DOCTYPE html>
<html lang="ja">
<head>
  <meta charset="UTF-8">
  <title>JavaScript のテスト</title>
</head>
<body>
  <script src="tak.js"></script>
</body>
</html>

最近の Web ブラウザには JavaScript 用のコンソールが用意されていて、コンソールからプログラムを入力して実行することが可能です。Google Chrome の 場合、JavaScript コンソールはメニューや設定から開くことができますが、ショットカットキー (Ctrl-Shift-J) でも開くことができます。あとは、コンソールで関数 test を実行すると、時間が msec 単位で表示されます。

それでは実行結果を示します。tak(22, 11, 0) を計算しました。なお、下表では JavaScript を JS と表記します。

表 : tak(22, 11, 0) の結果
処理系秒
Python (ver 2.7.3)91.9
JS (nashorn 1.8.0_05)48.3
PyPy (ver 2.2.1)24.7
SBCL (ver 1.0.55)5.85
SML/NJ (ver 110.74)3.48
JS (Google Chrome)2.96
GCC -O (ver 4.5.3)2.37
Julia (ver 0.3.1)2.30
SBCL (最適化)2.01
Go (ver 1.2)1.98
GHC -O (ver 7.4.1)1.92
GCC -O2 (ver 4.5.3)1.89
Scala (ver 2.11.1)1.79
Java (ver 1.8.0_05)1.09
ocamlopt (ver 3.12.1)1.09

Google Chrome の JS は Python や Java 8 に付属している JS (nashorn) とは次元の異なる速さで、ネイティブコードにコンパイルするプログラミング言語に匹敵する結果になりました。こんなに速いとは M.Hiroi も予想していなかったので大変驚きました。興味のある方はいろいろ試してみてください。

2015 年 1 月

1月4日

●ジュリア (Juila)

年の初めに M.Hiroi が興味を持っているプログラミング言語を紹介しましょう。Julia (プログラミング言語) - Wikipedia によると、『Julia（ジュリア）は、 一般的なプログラミングから高水準の科学計算処理まで対処するよう設計された高水準言語及び動的プログラミング言語である。』 とのことです。

Julia は LLVM をベースにした JIT (Just-In-Time) コンパイラを搭載することで、ネイティブなコードにコンパイルするプログラミング言語にせまる実行速度を達成しています。JIT を使った動的なプログラミング言語では PyPy もかなり速いのですが、Julia はそれよりも速いようです。

Julia は次のサイトからダウンロードできます。Windows 用のバイナリが用意されているので、とても簡単にインストールすることができます。

●Julia の対話モード

Julia の基本を学ぶのであれば、Lisp / Scheme の REPL (read eval print loop) のような対話モードがあると便利です。Julia の場合、プログラムを実行するコマンド julia をコマンドプロンプトで起動すると、次のようなプロンプトが表示されて入力待ちになります。

C>julia
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "help()" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.3.1 (2014-09-21 21:30 UTC)
 _/ |\__'_|_|_|\__'_|  |
|__/                   |  i686-w64-mingw32

julia>

これで REPL のようにプログラムを入力して実行することができます。終了する場合は CTRL-D を入力する、または関数 exit() を実行してください。なお、M.Hiroi が試したバージョンでは Julia の起動に少々時間がかかるようです。

●簡単なベンチマーク

さて、肝心な Julia の実行速度ですが、いつものように「たらいまわし関数」を使って調べてみました。

リスト：たらいまわし関数 (Julia)

function tak(x, y, z)
  if x <= y
    z
  else
    tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
  end
end

# 時間計測
@time(tak(22, 11, 0))

C>julia tarai.jl
elapsed time: 2.297216908 seconds (28480 bytes allocated)

それでは実行結果を示します。tak(22, 11, 0) を計算しました。使用した Julia のバージョンは 0.3.1 です。比較のため、Python, PyPy, Java, Scala, GCC, SML/NJ, SBCL (Common Lisp), OCaml (ocamlopt), Haskell (GHC) の実行結果を示します。Python, PyPy, Java, Scala, Julia 以外の処理系はプログラムをネイティブコードにコンパイルするものです。

表 : tak(22, 11, 0) の結果
処理系秒
Python (ver 2.7.3)91.9
PyPy (ver 2.2.1)24.7
SBCL (ver 1.0.55)5.85
SML/NJ (ver 110.74)3.48
GCC -O (ver 4.5.3)2.37
Julia (ver 0.3.1)2.30
SBCL (最適化)2.01
Go (ver 1.2)1.98
GHC -O (ver 7.4.1)1.92
GCC -O2 (ver 4.5.3)1.89
Scala (ver 2.11.1)1.79
Java (ver 1.8.0_05)1.09
ocamlopt (ver 3.12.1)1.09

Julia は Python や PyPy とは次元の異なる速さで、ネイティブコードにコンパイルするプログラミング言語に匹敵する結果になりました。こんなに速いとは M.Hiroi も予想していなかったので大変驚きました。興味のある方はいろいろ試してみてください。

1月1日

あけましておめでとうございます

旧年中は大変お世話になりました
本年も M.Hiroi's Home Page をよろしくお願い申し上げます

Copyright (C) 2015 Makoto Hiroi
All rights reserved.
[ Home ]