【Bash】【シェル】コードを最適化したいです

Question

##■質問内容
以下の問題に対してコードを作成し、テストは合格するのですが実行しようとしたところ「Execution Timed Out (12000 ms)」のメッセージが出てきました。
テストでは動くので恐らくコードを最適化する必要があるのではないかと思います。
このコードをどう書き換えればよいのか、また文法が間違っているところがあれば教えていただきたいです。

■問題のサイト

https://www.codewars.com/kata/growth-of-a-population/train/shell

■問題

とある町は"$1"人の住民が住んでいます。人口は毎年"$2"％増加し、さらに毎年"$3"人新しい住民が住みます。
町は住民を"$4"人以上にするために何年必要ですか？

At the end of the first year there will be:
1000 + 1000 * 0.02 + 50 => 1070 inhabitants

At the end of the 2nd year there will be:
1070 + 1070 * 0.02 + 50 => 1141 inhabitants (number of inhabitants is an integer)

At the end of the 3rd year there will be:
1141 + 1141 * 0.02 + 50 => 1213

It will need 3 entire years.

※パーセントパラメーターが2の場合、0.02に変換する必要があります

#!/bin/bash
nbYear() {
    human=$1
    year=0
    inc=`echo "scale=5; $2/100" | bc` #パーセンテージに変換
    while true
    do
      human=`echo " $human + $human * $inc + $3" | bc | sed s/.[0-9,]*$//g`　#小数点以下を切り捨て
      year=$(($year + 1))
      if [ "$(echo "$human >= $4" | bc)" -eq 1 ]; then
        echo $year
        break
      fi
    done
}

nbYear $1 $2 $3 $4

Answer 1

[[ $# -eq 5 ]] && echo $5 || echo 0

いろんな書き方がありますが、

三項演算子
https://code-examples.net/ja/q/3c53ed

[[ ]] については
https://qiita.com/Riliumph/items/f07272fa9b0834032a9d

[ ] はtestという外部コマンドで、[[ ]] はbash独自の記法（文法）です。

$total * $percent / 100

の場合、計算式中で少数化した場合の算術結果がどうなるか（どのタイミングで少数の切り捨てが起きているか）が記憶になかったので、確実そうな整数化を行いました。
とりあえずLLONGまでは扱えるからいいかな、と…。
普段はshellで少数をほとんど取り扱わないので。

Comments

[KeisukeKoga]

コメントのつもりが回答に書いてしまいました、すいません。

[otn]

昔々の sh では [ や test は外部コマンドでしたが、今はシェル組み込みコマンドになっていると思います。
bash / dash / ksh / zsh

[KARI]

教えていただきありがとうございます。
色んな書き方があるのが分かり大変勉強になりました。

Answer 2

というかbc使っていいならbcに全部やらせれば1プロセスで済むのでそれでよいのではないかとは思うのですが。

bashの演算能力だけでやれということなら、

#!/bin/bash
nbYear() {
  total=$1
  percent=$2
  inc=$3
  limit=$4
  year=$( [[ $# -eq 5 ]] && echo $5 || echo 0 )

  percent_inc=$(( $total * 100 * $percent / 10000 ))

  total=$(( $total + $percent_inc + $inc ))
  year=$(( year + 1 ))

  echo "$year : total = $total ( percent = $percent_inc , inc = $inc )"
  if [[ $total -ge $limit ]] ; then
    echo "Over : $year on Humans is $total"
  else
    nbYear $total $percent $inc $limit $year
  fi
}

nbYear $1 $2 $3 $4

とかでしょうか。
bcを介さないので一切少数を考慮せず、shellは切り捨てなので、人数のように切り捨てでよいものは切り捨てのまま取り扱ってしまったほうが素直ですね。

エラー検知していないので、bashの数値上限でループ起こしてSegmentation起こして死ぬと思います。

実行結果：

# sh test.sh 1000 2 50 1200
1 : total = 1070 ( percent = 20 , inc = 50 )
2 : total = 1141 ( percent = 21 , inc = 50 )
3 : total = 1213 ( percent = 22 , inc = 50 )
Over : 3 on Humans is 1213

Comments

[KARI]

ご回答ありがとうございます。
whileを使わずループする方法があるんですね。
year=$( [[ $# -eq 5 ]] && echo $5 || echo 0 )
　　→この部分の行われていることは分かるのですが、初めて見る文法なのでどう検索したらいいか分からないです。
　　　この書き方をまとめているサイト等ありましたら教えていただけないでしょうか。

percent_inc=$(( $total * 100 * $percent / 10000 ))
　　→これは$(( $total * $percent / 100 ))では駄目なのでしょうか？

Answer 3

そんなに遅いとは思えないのですが。
あと、ifの条件が意味不明です。これだとエラーになると思いますが。違うコードを張り付けた？

bcを使う必要もないので、bashの計算機能だけで行けます。

#!/bin/bash
nbYear() {
    year=0
    human=$1
    inc=$2
    come=$3
    limit=$4
    while true
    do
      let human+=human*inc/100+come
      let year++
      if [ $human -ge $limit ]; then
        echo $year
        break
      fi
    done
}

nbYear $1 $2 $3 $4

引数が正当か（数字が４つ）をチェックしてないので、不正な引数だと無限ループですね。

Comments

[KARI]

ご回答ありがとうございます。
if文は　if [ $human -ge $4 ]; then　と修正し忘れていました。
こんなに見やすいコードになるんですね。
1つ質問があるのですが、引数に少数が入力されるとなったらそれはbcを使うしかないのでしょうか？

[otn]

整数演算にはいろんな記法がありますが、Bashなら let がおすすめです。

小数を小数として計算したければ、bcですね。
倍精度浮動小数点の範囲で良ければawk/Perl/Python/Rubyも使えます。

あるいは、例えば 0.02 という入力を 2 ÷ 100 として整数演算に帰着することは文字列処理すれば十分可能です。

[KARI]

ありがとうございました！
これからは let を活用していきます。

Answer 4

　#小数点以下を切り捨て

コメントの前に全角スペースが入っています。

あと、if...thenの条件判定は、

if [ $human -ge $4 ]; then

で良くないですか？

Comments

[KARI]

ご回答ありがとうございます。
humanの小数点以下を切り捨てるコードを作る前のIF文が修正しないままになってました。
コメント部とIF文を修正して実行してもタイムアウトになってしまうのですが、もはやコードを根本から変えるしかないのでしょうか？

[KojiDoi]

私がやってみた範囲では再現せずちゃんと結果が出ています。タイムアウトということですが、その間なんのメッセージも出力されていないのですか？

[KARI]

Shell Stdout
15
Shell Stdout
10
Shell Stdout
94
Shell Stdout
151
Shell Stdout
116
Basic tests
Shell Stdout
15
Shell Stdout
10
Shell Stdout
94
Shell Stdout
151
Shell Stdout
116
STDERR
Execution Timed Out (12000 ms)

とメッセージが出ています。

[KojiDoi]

数字は$yearなんでしょうか。
Shell Stdout とかBasic testsは誰が出しているのでしょうか、質問の通りのスクリプトだとすればあり得ない出力です。

[KARI]

出力されている数字に関しては$yearです。
https://www.codewars.com/kata/growth-of-a-population/train/shell
このページでコードを実行した際のメッセージが↑になります。
説明不足で申し訳ありません。