HackerRank: Compute the Average

投稿日 投稿者 YOMOGITA

HackerRankのこちらの問題 “Compute the Average”を解きます。

問題はタイトル通り、与えられた数字たちの平均を求めるというモノ。僕の回答はこちら。

read N
SUM=0

for ((i=0;i<${N};i++));do
    read X
    SUM=$((${SUM}+${X}))
done
printf "%.3f\n" $(echo ${SUM}/${N} | bc -l)

入力の1行目で与えられる数字の個数Nを読み取り、以下略。見たまんまです。
このくらいならawkのワンライナーでいけるんじゃないの、と思って作った別解がこちらです。

awk 'NR==1{N=$0;SUM=0} NR>1{SUM=SUM+$0} END{printf("%.3f\n",SUM/N)}'

コレも解説は省略です。

この問題を解いていく過程で2つほど新しい気づきがあったので、シェアしたいと思います。サマリとしてはこちら。

  1. bcコマンドより$(())のほうが軽い
  2. bcコマンドは四捨五入じゃなくて切り捨てする（だから最後の出力はprintfを介してます）

2はそのまんまです。1について、もうちょい詳しく説明します。

気づいたキッカケはあるテストケースで時間切れでNGとなったことです。そのときは、forループの中の計算もbcコマンドでやってました。比較用のスクリプトを書いてtimeコマンドで比較してみます。

tc1.sh

#!/bin/bash
for ((i=0;i<1000000;i++));do
    echo $((1+1))>/dev/null
done

tc2.sh

#!/bin/bash
for ((i=0;i<10000;i++));do
    echo 1+1 | bc>/dev/null
done

ループの回数にご注意ください。100倍違います。

で、それぞれ計測した結果がこちらです。

$ time ./tc1.sh

real 0m7.277s
user 0m4.475s
sys 0m2.659s

$ time ./tc2.sh 

real 0m19.721s
user 0m16.516s
sys 0m8.084s

100倍回してるtc1.shのほうが速いです。
ブレース展開ではseqに負けてたBashですが、やればできる子です（違。
さて、こうなると気になってくるのは、seqとブレース展開、たくさん実行したときはどちらが速いか、です。試してみました。結果はこちら。

$ time for ((i=0;i<10000;i++));do seq 3 >/dev/null; done 
real 0m13.548s
user 0m8.710s
sys 0m5.435s

$ time for ((i=0;i<10000;i++));do echo {1..3} >/dev/null; done

real 0m0.128s
user 0m0.071s
sys 0m0.056s

Bash、できる子！！

こんな比較をしてわかるのは、多重ループ回すときに外側はseqで、内側はブレース展開でやるほうが早そうということくらいです。が、そんな事をしたら可読性が落ちます。可読性とスピードはなかなか両立しませんねぇ。

今日はここまでです。最後までお付き合いいただきありがとうございました。