「Perlでフィボナッチ数列を求めてみる」の続き 〜CodeIQ解答編〜

前回の続き

このエントリは以下のエントリの続きになっています。

http://blog.hylogics.com/entry/perl_fibonacci_1

http://blog.hylogics.com/entry/perl_fibonacci_1

前回のエントリではフィボナッチ数を求めるにあたり以下の問題が発生しました。

• 順当に再帰で数列を書くと計算量が大きくなる(処理が遅くなる)。
• 再帰した内容を配列に入れると処理は早くなるがメモリを逼迫する。

今回はこれらを解決したいと思います。
その前に、出題内容を振り返ってみましょう。

出題内容

挑戦者求む！下3桁のみのフィボナッチ数列から、任意の項を素早く求めてください。 by CodeIQ運営事務局 アプリケーションエンジニアを募集する企業│CodeIQ

与えられた課題は以下の通りです。

1. 普通にフィボナッチ数を求めると桁あふれが発生するので、下三桁のフィボナッチ数を求める。
2. 与えられたファイルに記載されたリストに沿ってフィボナッチ数を求める。
3. ファイルの1行目は項の数、2行目以降は項のリストとなる。
4. リストの並びはランダムである。

それぞれ解法は以下の通りです。

1. % 1000で余剰を求めて下三桁にする。
2. ファイルのインポート処理とフィボナッチ数を求める処理を実装する。
3. ファイルの1行目は除外して2行目以降をリストに入れる。
4. リストをソートして最大値でフィボナッチ数を求めると計算量が少なくなる。

上記を踏まえてコードを書いてみます。

フィボナッチ基本形

再帰を使わずにフィボナッチ数を求める処理を書いてみるとこんな感じでしょうか。

#! /usr/bin/perl

use strict;

my $fibo;
my $n;

# for debug
my $n = 10;

#$a = n-1, $b = n-2
my $a = 0;
my $b = 0;

for(1..$n){
        if( $_ == 1 ){
                $fibo = 1;
        }elsif( $_ == 2 ){
                $fibo = 1;
        }else{
                $fibo = $a + $b;
        }
        $a = $b;
        $b = $fibo;
        # for debug
        printf("%d\t%d\n",$_,$fibo);
}

課題用に改修

ファイルからの入力と出力処理、除算処理を追加してみました。

#! /usr/bin/perl

use strict;
use IO::File;

my $fibo;
my %ret;

my $in_file = './sample.in.txt';
my @list;

my $io = new IO::File "< $in_file" or die;
@list = map { chomp $_; $_ } $io->getlines;
$io->close;

# $list[0]にリスト数が入っている
my $list_num    = shift @list;

# リスト中の最大値を取得
my @sorted_list = sort { $a <=> $b } @list;
my $max_num     = $sorted_list[ $list_num - 1 ];

# $a = n-1, $b = n-2
my $a = 0;
my $b = 0;

for( 1..$max_num ){
        my $n = $_;
        if( $_ == 1 ){
                $fibo = 1;
        }elsif( $_ == 2 ){
                $fibo = 1;
        }else{
                $fibo = ($a + $b) % 1000;
        }
        $a = $b;
        $b = $fibo;

        # リストに該当した場合、一旦ハッシュに入れる
        for(1..$list_num){
                if( $n == $list[$_-1] ){
                        $ret{ $list[ $_-1 ] } = $fibo;
                }
        }
}

# 一括出力
for( 1..$list_num ){
        printf "%02d.\t%d\n", $_, $ret{ $list[ $_-1 ] };
}

実行結果

$ time ./fibo.pl
0
1
1
2
3
5
75
970
853
378

real    0m2.067s
user    0m2.066s
sys     0m0.001s

sample.out.txtと比較してみます。

$ ./fibo.pl > out.txt
$ diff out.txt sample.out.txt
$ 

一致しているので問題ないでしょう。

解説

ポイントは以下の通りです。

1. (あえて)再帰を使わずループで書いたほうが計算量が少ないため早く終わる。
2. リストの並びがランダムなので都度出力せず、一旦ハッシュに入れてからまとめて出力する。

感想

再帰が理解できているかの出題だと思っていたのですが、むしろループをべた書きした方が早かったです。 再帰処理も一回改修して配列をハッシュにした上で不要になったモノを削除する処理を書いてはみましたが、それも要らなかったですね。

かなり遠回りして着地しましたが、徒労感がひしひしと。。。

数学ガール 上 (MFコミックス フラッパーシリーズ)

数学ガール 下 (MFコミックス フラッパーシリーズ)