今回は、アルゴリズムの改善について紹介します。お題は、フィボナッチ数列（n番目の値が、その前の値と、その前の前の値を足した数になっているような数列）です。
フィボナッチ数列の実装
まずは、お馴染みExcelマクロで、40番目までをA1セル〜A10セルまで出力してみます。
Dim length as integer
For length = 1 to 40
If length = 1 then
Cells(length,1) = 0
Elseif length = 2 then
Cells(length,1) = 1
Else
Cells(length,1) = Cells(length - 1,1) + Cells(length - 2,1)
End If
Next lengthでは、これをNode.jsで実装してみましょう。前回（サーバーサイドプログラミング(2)Node.js）の「準備」のセクションで紹介した内容を転用して、作業ディレクトリを用意しましょう。なお、前回のプロジェクトディレクトリ名は、”nodejs-study”でしたが、ここを任意の名称（例えば、今回は”fibonacci”等）に変更しましょう。
※ShellにもDockerfileにもDocker-compose.ymlファイルにもファイル名の入力箇所があります。
次に、Dockerを起動します。こちらについても、前回の「Dockerの起動と終了」のセクションを参考にしてみてください。
さて、それでは早速、今回用意したディレクトリにapp.jsファイルを用意して、以下のJSコードを入力します。
'use strict';
function fib(n){
if(n===0){
return 0;
} else if(n===1){
return 1;
}
return fib(n - 1) + fib(n - 2)
}
const length = 40;
for (let i = 0; i <= length; i++){
console.log(fib(i));
}では、これを実行してみます。
node app.js成功していれば、
0
1
1
2
3
5
8
13
…
と続いていたと思います。
ただ、このコードだと少々時間がかかります。今回は40までだったのですぐだったと思いますが、100などの数字だといつまで経っても終わりません。なお、時間を測定するtimeコマンドでそれがわかります。
time node app jsなぜ時間がかかるかというと、先のJSコードは、再帰で前の項の数字を呼び出して都度、その前の項も計算しているからなんです。なお、このように沢山時間がかかっている処理がどれ位メモリを使っているのかを調べる方法にプロファイルというものがあります。具体的には、Node.jsに組み込まれたツールを利用するのですが、詳細は省略します。ネット検索や、N予備校の教材を確認して下さい。参考までに、実行するコマンドは下記の通りです。
node --prof app.jsアルゴリズムの改良
では、どうすればよいかというと、Excelマクロの速度改善でもお馴染みの配列を利用します。すなわち、一度計算した項は、その計算結果を配列に入れてしまい、何度も計算し直さないようなアルゴリズムにするのです。
連想配列Map
ここでの配列は、特に添字に数字だけでなく文字も使うことができる連想配列Mapを利用します。以下、REPLを起動して、動作確認します（REPLについては前回の「REPL」のセクションを参考にしてみてください）。Mapの使い方ですが、まずnewして、今回用の新しいオブジェクトをつくります。
let etoMap = new Map();
let calenderMap = new Map();次にこの配列に入れるデータをsetで追加していきます。1番目にキー（文字でも数字でも可）、2番目に値を入れます。
etoMap.set('子','mouse');
calenderMap.set(1,'January');そして、呼び出すときには、getを使います。
etoMap.get('子');
calenderMap.get(1);これで、
‘mouse’
‘January’
と出力されれば成功です。なお、定義していないキーをgetしようとすると、undefinedを返します。
Mapを使用したフィボナッチ数列の実装
'use strict';
const memo = new Map();
memo.set(0,0);
memo.set(1,1);
function fib(n){
if(memo.has(n)){
return memo.get(n);
}
const value = fib(n - 1) + fib(n - 2);
memo.set(n,value);
return value;
}
const length = 40;
for(let i = 0; i <=length; i++){
console.log(fib(i));
}ポイントは、中央部分のfib(n)関数の定義です。まず、if文でmemo配列がnをキーに持っていれば、その値を返します。そうでない場合には、改めて再帰関数を計算して（”value = fib(n-1) + fib(n-2)”の部分）、それをmemo配列に入れた後で返すという関数になります。ここで都度memo配列に入れることにより、再度同じ計算することを避けることができるわけです。
今回は、以上となります。最後までお読み頂き、ありがとうございました。
※こちらの内容は、N予備校の教材を参考しております。
コメント