### *[アドベントカレンダー 2019年]* #### *8th December 2019*

## これ、完全に身内用やねんな。
## 外野さんは細かい突っ込みは無しで頼むんやで。
## そのレベル？的な内容から書いてるでな。

さてさて、前回はリファクタリングにも下の表みたいな観点があると思うよ！
ってとこまで話していました。

内容の純粋な整理(不要な変数消したり、各種名前を整えたり。)
計算回数を減らす -> 効率性がUP!
見え方、ぱっと見の分かり易さを向上する -> 保守性がUP!
新しい記法のトライアルで -> 結論が分かっている機能だからナレッジに転化しやすい

今回はこの中でも "2." に特化して、
例のコードをリファクタする事例を見ていきましょう。

例のリファクタリングコード

まずは再掲ですが、今回の主題となっているコードが以下になります。
16人の研修生にユニークな座席番号を割り振るって機能ですね。

selecter.sh

#!/bin/sh
readonly NUMBER_OF_TRINEE=16
selected_seats=()
NUM=0
for i in `seq $NUMBER_OF_TRINEE`
do

  echo ENTERを押してくださいね。:
  read

  while true
  do
    NUMWK=`expr $RANDOM % $NUMBER_OF_TRINEE`

    for i in ${selected_seats[@]}
    do
      if [ $i = $NUMWK ]; then
        continue 2
      fi
    done

    NUM=$NUMWK
    break
  done

  selected_seats=("${selected_seats[@]}" $NUM)
  #結果を表示
  echo $NUM

done
echo 全員セットできました。
exit 0

で、これをどうリファクタするかーってのが今回の主題です。
2.は計算回数を減らすことが目的だったので、まずは現状を分析してみましょう。

現状分析

とは言っても、今回の見るべきポイントは2箇所です。

一番外のfor.sh

for i in `seq $NUMBER_OF_TRINEE`
～
done

まずはこの時点で内部の処理に対して "16回" の試行が確定します。

次に見るのは中心にある無限ループです。

無限ループの部分.sh

  while true
  do
    NUMWK=`expr $RANDOM % $NUMBER_OF_TRINEE`

    for i in ${selected_seats[@]}
    do
      if [ $i = $NUMWK ]; then
        continue 2
      fi
    done

    NUM=$NUMWK
    break
  done

ここでは、簡単に言えばランダムに1～16までの数字をもらってきて、
まだ割り当てのない席ならそのまま、既に割り当てられていたらまたランダムに数字を
割り振ってもらう機能になっています。

割り当て済みの座席番号をランダムの選択対象から外しているわけではないので、
最後の１人段階では "15/16が埋まって、残り１つの数字をランダムで引き当てるまでループする"
状態になっています。

実はどれだけのコストがかかるのか算出が非常に難しい状態になっています。
一応、それぞれの期待値をサマリすれば平均回数は求められそうですが、
安定した回数の算出と言うのは不可能になりそうです。

仮に全部をなんとなく平均化して全ての場合1/2回失敗するとすれば、
初回は絶対成功するので省くとしても、残り15回で67.5回の試行が必要となります。

そして、それが存在するか確認する、このwhileに入れ子になったforも同じくらい動くのです。

3重ループが全力で稼動するわけですね。
歯車みたいに噛み合ってる感はあるのですが、あまり良い状況ではありません。

最小の計算回数と言う観点で。

さて、ややこしくなってきたので、
この辺で結論に移りましょう。

ここで重視してるのは、不定回数の計算が毎回動くことで
膨大なリソースを消費しかねないということです。

多重ループで昔から問われてきた話にはなりますが、
爆発的に計算回数が "増える可能性のある" 処理は避けたいものです。

というところで考えると、研修生の人数分だった16回の計算は仕方ないとしても、
それ以上には増やしたくないなーと思うわけです。
※ javaとかならStreamAPIでさくっと1ライナーで書けたりしますが、
※ bashだと16回を短縮するのは難しそうかも。。？

そして、このやり方をあくまでベースにするならばwhileの無限ループも残るのは致し方なし。
せめて、そこの計算が倍加するforの入れ子だけでも何とかしたい、と思います。

じゃあどうするのかと言うと、、

ReSelecter.sh

#!/bin/sh
readonly NUMBER_OF_TRAINEE=16
selected_seats=()

for i in `seq $NUMBER_OF_TRAINEE`
do

  echo ENTERを押してくださいね。:
  read

  NUM=0
  while true
  do
    NUMWK=`expr $RANDOM % $NUMBER_OF_TRAINEE`

   if ! [ `echo ${selected_seats[@]} | grep -q "$NUMWK"` ] ; then
      NUM=$NUMWK
      break
    fi
  done

  selected_seats=("${selected_seats[@]}" $NUM)
  #結果を表示
  echo $NUM

done
echo 全員セットできました。
exit 0

一応、こんな感じでforをifに置き換えることで計算回数を抑えることが可能です。
配列の要素にまとめて[@]でアクセスすることにより、1つずつ中身を取り出すよりは計算回数を抑えられました。

さらに効率化するためにはフィッシャー–イェーツのシャッフル(もしくはダステンフェルドのアルゴリズム)を使えば16+16の32回に固定できます。
(この処理だと表示のためにさらに+16回かな。。)

が、今回の主眼は効率化するよ！って観点の話なので、
現状を残したままで計算回数を抑える観点についての記述で完了しようと思います。

まとめ

今回の例はピンポイントでしたが、
無駄なリソースを使用する処理を減らすと言うのはリファクタリングでも重要な観点だと思います。
チューニング的な要素を持ったリファクタリングですね。

とりわけWebサービス等では不必要な要素まで多重ループすることで、
表示の時間が重くなる事象なども依然として存在します。
多重ループでDBやファイルへの外部アクセスがあるとなおさらですね。

基礎的な観点だからこそ、武器として持っておくと活きるシーンが多いのがこの "2." の観点だと言えるでしょう。

次回は

　3. 見え方、ぱっと見の分かり易さを向上する -> 保守性がUP!

について書きたいと思います。

ここまで読んでくれてありがとうございましたーヽ( ･∀･)ﾉ