N予備校 プログラミングコース 第17回
あなたは2019年の目標って立てましたか？
どんな目標を立てたか覚えていますか？
私は2018年末に2019年の目標を立てました。
その一つにプログラミングを学び仕事として使えるようにすることをあげました。
そして、思い立ったが吉日と「N予備校のプログラミングコース」を申し込みました。
そして受講と同時に自身の振替と、これから始めようと考えている人の参考になればとブログを書き始めました。
今回ブログの移設にともない、再度そのブログを読み返しながら、今思うことを加えて記載していきたいと思います。
また私が受講したのは【2018年度】で、現在公開されている【2019年度】との違いについても書いていきたいと思います。
このブログは、初心者が学びながら書いているため、間違っている場合があります。
分かり次第修正していくつもりです。
そのあたりも含め楽しんでいただければと思います。
最後に進めていてわからなかったところや気になったところをまとめています。
プログラミング入門 webアプリコース 第17回
第三章からは、Webサービス作成を行います。作成するのは秘密の掲示板になります。
今回は、Webサービス開発において重要なアルゴリズムについて学びます。
尚、2018年度版と2019年度板では第2項と第3項の順番が逆になっています
- 今回の内容まとめ（2018年度版：第3章 03, 2019年度版：第3章 02）
・アルゴリズムについて
- 今回の目標
アルゴリズムの効率化の重要性について理解する。
- 今回新しく扱っているコマンド等
・time
アルゴリズムについて
アルゴリズムとは、問題を解くための手順を定式化した形で表現したものです。
数学などは、1つの問題を解くためには様々な方法が存在します。
どの方法でも解くことが可能ですが、どの方法を選ぶかで解くまでの時間がかかります。
車でいえば、どのルートを通っても目的地にはつきますが、高速道路を使うのか一般道路を使うかで時間が異なります。
コンピューターは人間より速く大量に計算できるので、ちょっとした計算であれば計算時間に大きなさは生じません。
しかし、繰り返し計算するなど手順が複雑であればその分処理に時間がかかってしまいます。
1つの問題を解くために、より効率的な手順を持つアルゴリズムに変更することでパフォーマンスが変化します。
今回はフィボナッチ数列を出力することで、アルゴリズムによってパフォーマンスがどう変化するかを試します。
フィボナッチ数列を40番目まで出力する
フィボナッチ数列とは、1番目が「0」、2番目が「1」で、3番目以降は、「前」と「前の前」の値を足したものになります。
つまり、3番目は、0+1=1であり、4番目は1+1=2、5番目は2+1=3、6番目は3+2=5というようになります。
この関数自体は、今までに学んだ内容でifやforを使うことによって比較的簡単に作成することが出来ます。
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));
}
1行目でまず、fib(n)関数というものを設定します。
関数の内容を2~8行目で規定しています。
2～3行目で、n=0であれば0を取るように指定し、
3～4行目で、n=1であれば1を取るように指定します。
そして、7行目でnが0でも1でもなければ、n-1の時のfib関数の結果とn-2の時のfib関数の結果を足すように指定しています。
9行目で、lengthという定数に40という数値を設定し、
10-11行目で、i=0から始めて、iが40になるまでfig関数にiを入れた結果を表示するように設定しています。
これにより、40番目までのフィボナッチ数列が表示されます。
関数の実行にかかる時間の測定（time）
続いて、今回作成した関数を実行するのにかかった時間を測定します。
その時に使うのがtimeコマンドです。
time node ○○
このコマンドで、○○というファイルのプログラムを実行するのにかかった時間が表示されます。
このコマンドを使って先ほど作成したフィボナッチ数列を表示する時間を測定すると約7秒ほどかかることがわかります。（パソコンの性能によって時間は変化します）
その理由は、この関数ではそれぞれの計算回数が
1番目：0回 fib(1) = 0
2番目：1回 fib(2) = fib(1) + fib(0)
2番目：2回 fib(3) = fib(2) + fib(1)
3番目：4回 fib(4) = fib(3) + fib(2)
4番目：7回 fib(5) = fib(4) + fib(3)
のように、計算回数がどんどん増えていき、7番目の数値であるfib(8)を実行する時には33回の計算を行うことになります
fib(7)を計算するのに20回、fib(6)を計算するのに12回の計算が必要だからです。
このアルゴリズムで100番目までの数値を出そうとすると、とても長い時間がかかってしまいます。
そこで、前回学んだ連想配列Mapを利用してアルゴリズムを改善します。
アルゴリズムの改善
さきほどの関数では、7番目の数値であるfib(8)を出す時にfib(0)~fib(7)までの計算をしなければならず、fib(2)やfib(3)等は何度も計算が行われます。
そこで、それぞれの計算結果を連想配列として保存することで計算量を大幅に減少できます。
連想配列については、奮闘記No.16に書いてありますので読んでみてください。
const A = new Map();
A.set(0,0);
A.set(1,1);
function fib(n) {
if (A.has(n)){
return A.get(n);
}
const value =fib(n-1) + fib(n-2);
A.set(n, value);
return value;
}
1行目で、連想機能Mapを呼び出し、そのことをAと名前を付けています。
2-3行目で、順番（key）が0, 1の時はそれぞれの値を0, 1とするように定義しています。つまり、fib(0)とfib(1)を先に定義しています。
続いて、4～8行目で、fib関数を設定しています。
5~6行目で、nの数値がすでに配列Aの中にkeyとして設定されていればその値(value)を使うように設定しています。
初めにfib(0)とfib(1)は定義しているので、n=0, 1のときはそれぞれの数値0,1になります、
8~9行目で、nの値が配列Aの中にkeyとして設定されていなければ、keyがn-1である値とkeyがn-2である値を足した結果をn番目の値とするように設定しています。
つまり、n=2の時は、まだ2はkeyとして設定されていないため、keyが0,1の時の値を呼び出してその和をn=2の数値として設定し配列[2, 1]となります。
この関数を用いて40番目まで表示する時間を測定すると1秒かからない結果となります。
このようにアルゴリズムを改善することでパフォーマンスが大きく改善するため、アルゴリズムの効率化が大切になります。
今回は、アルゴリズムについて学びました。
受験でも、問題を解くことは大事ですが、どうやって解くかを考えることはとても大切です。
プログラミングでも、同じ結果が出ていれば問題ないのではなく、いかに早くその処理を終わらせるかが大切になります。
1つの処理をするのに効率がいい方法はないかを考えながら進めて生野が大事です。
