振動人生記録 by gifdog97

情報学,音楽,秘境,旅

簡単なシェルスクリプトを書く

情報科学をやっているしちょっとは技術的なことも書いてみる。恐らくだいぶ簡単な話なので誰かのためになることはほぼ想定していない。自分の備忘録用に書いておく。

3Sでシェルスクリプトを書かされたのだが、「は?」という感じでそれきり使わなくなっていた。3Aの明らかにシェルスクリプトを書いた方が楽に処理出来そうな課題も、そもそもシェルスクリプトの恩恵をちゃんと認識していなかったこともありマンパワーでこなしていた。

さて、最近アルゴリズムの勉強をしており、いくつかのアルゴリズムについて処理にかかる時間の比較をしたくなった。もちろん実際はO記法で結果はある程度分かっているのだが、実際にどれほど差があるのか数値で確かめてみたいのが人情というものである。そこでやっと重い腰を上げてシェルスクリプトの書き方を勉強し直すと、思ったほど大変ではなかったのでささっと書いてみた*1

ここでは蟻本の最初に書いてあるくじびきアルゴリズムの時間計測を行う。問題の概要は本筋から外れるので省略するが、3通りの実装があり、それぞれ計算量はO(n^4)O(n^3\log n)O(n^2\log n)となっている。さて、実際どれほど差があるのか。

ひとまずアルゴリズムをそれぞれkujibiki1.cpp, kujibiki2.cpp, kujibiki3.cppに書き、Makefileで実行ファイルをmain1, main2, main3と指定。
また、入力用のファイルを作成するコードを適当にmake_testfile.cppとかに書く。
その上で実際に時間計測を行うシェルスクリプトを書くと次のようになった。

#!/bin/bash

make testfile
./make_testfile
make kujibiki1
make kujibiki2
make kujibiki3

echo

for i in 1 2 3
do
echo "kujibiki$i:"
time ./main$i < testfile.txt
echo
done

make clean


cとかで時間計測をする場合はgettimeofdayとか使わなくてはならないが、シェルスクリプトの場合はtimeというクソ便利なコマンドがあり、実際の実行時間に加えて、ユーザモード・カーネルモードでの実行時間まで出力してくれる。
ちなみに入力サイズn=200としたときの実際の実行結果はこちら。

g++ -o make_testfile make_testfile.cpp
g++ -o main1 kujibiki1.cpp
g++ -o main2 kujibiki2.cpp
g++ -o main3 kujibiki3.cpp
kujibiki1:
No
real    0m0.506s
user    0m0.484s
sys     0m0.000s

kujibiki2:
No
real    0m0.068s
user    0m0.063s
sys     0m0.000s

kujibiki3:
No
real    0m0.017s
user    0m0.016s
sys     0m0.000s

思ったより差が出ました。アルゴリズムすごい。

当たり前だけど、このあといろいろ数値を変えたりアルゴリズムを改良したくなったら、該当のソースコードを変えてシェルスクリプトを叩くだけで全部勝手にやってくれる。シェルスクリプト普通にクソ便利だった(超今更)。Makefileとか工夫したらもっと効率的に書けるのかもしれない。とりあえず今後はシェルスクリプト積極的に使っていろいろ勉強する。

あと初めてブログにTeX表記やソースコードを埋め込んだけど謎の達成感がある。簡単だったので今後も何かしら投稿していきたい*2

*1:もっといろいろやろうとしたら大変なのだろう。

*2:たぶんしばらくはしょうもない備忘録が続くと思うけど、そのうち生産的なことやって公開してみたいなあ。