フィボナッチ数列

最初の awk には関数を定義することはできませんでしたが、後々 nawk 以降では関数を定義することができます。 この関数定義で必ず例題になるのもに再帰問題があります。 有名なものでは、クイックソートや竹内関数 (たらいまわし関数)がありますが、ここではフィボナッチ数を挙げます。

どれも関数定義の中で、その関数を用いるものとなっています。

15 Exercises for Learning a new Programming Language の中の 2 問目のひとつがフィボナッチ数です。 その特性から再帰的に解いていきます。

awk の関数定義が再帰でも使えるため、数式を素直に記述することで解くことができます。

#! /usr/bin/gawk -f
# fibonacci.awk

BEGIN {

    # check ARGV[1]
    if (ARGV[1] == "") {
        num = 10;
    } else {
        num = ARGV[1];
    }

    for (i = 1; i <= num; i++) {

        print fibonacci(i);
    }
}

# fibonacci()
# input:    number
# output:   fibonacci number
function fibonacci(n) {

    if (n > 2) {

        return fibonacci(n - 2) + fibonacci(n - 1);
    } else {

        return 1;
    }
}

関数 fibonacci() の中で関数 fibonacci() を呼び出しているのが分かると思います。 引数に 30 を与えて実行してみます。

$ time gawk -f fibonacci.awk 30
1
1
2
3
5
8
<snip>
gawk -f fibonacci.awk 30  1.53s user 0.01s system 91% cpu 1.679 total

決して遅くない CoreDuo 2.5 GHz のマシンでこのくらいかかります。

さて、この問題は高速化の手段としてメモ化を行うことが知られています。

#! /usr/bin/gawk -f
# fibonacci_mem.awk

BEGIN {

    # check ARGV[1]
    if (ARGV[1] == "") {
        num = 10;
    } else {
        num = ARGV[1];
    }

    for (i = 1; i <= num; i++) {

        print fibonacci_memo(i);
    }
}

# fibonacci_mem()
# input:    number
# output:   fibonacci number
function fibonacci_memo(n) {

    if (n <= 2) {

        return 1;
    } else if (memo[n] != 0) {

        return memo[n];
    } else {
        memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1);

        return memo[n];
    }
}

このメモ化は既に計算してある、ある数を引数とする関数 fibonacci() の結果を配列に保存しておき、既に計算してある場合には、その配列を呼び出すだけにするというものです。

$ time gawk -f fibonacci_mem.awk 30
1
1
2
3
5
8
<snip>
gawk -f fibonacci_mem.awk 30  0.00s user 0.00s system 44% cpu 0.002 total

違いは歴然としています。

ただし、どんな再帰に対しても速度が劇的に高速になるわけではありません。 awk の場合には配列の呼び出しは高速ではないため、配列に格納してそれを呼び出すのにも他の言語よりも時間がかかる場合があります。 適材適所で使っていきたいところです。