フィボナッチって食える?

awk


これも何度目かの紹介ですが、awk でもメモライズできます。

まず、再帰を使ってフィボナッチ数列を計算してみます。

#! /usr/bin/gawk -f
# fibonacci2.awk - calculate fibonacci numbers
# usage: gawk -f fibonacci2.awk num
#   input:  iteration numbers for ARGV[1]
#   output: fibonacci numbers

BEGIN {

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

    for (i = 1; i <= num; i++) {
        print fibonacci(i);
    }
}

# fibonacci - return fibonacci number with recursive method
function fibonacci(n) {
    if (n > 2) {
        return fibonacci(n - 2) + fibonacci(n - 1);
    } else {
        return 1;
    }
}

では、実行してみます。

$ time gawk -f fibonacci2.awk 20
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
gawk -f fibonacci2.awk 20  0.40s user 0.35s system 91% cpu 0.816 total

遅いのは Zaurus だからです。

次にメモライズしてみます。

#! /usr/bin/gawk -f
# fibonacci2_mem.awk - calculate fibonacci numbers
# usage: gawk -f fibonacci2_mem.awk num
#   input:  iteration numbers for ARGV[1]
#   output: fibonacci numbers

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 - return fibonacci number with memorize
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];
    }
}

実行してみましょう。

$ time gawk -f fibonacci2_mem.awk 20
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
gawk -f fibonacci2_mem.awk 20  0.06s user 0.02s system 93% cpu 0.085 total

ただし、なかなかスマートにメモライズが使えないのが欠点ですかね。