時代遅れひとりFizzBuzz祭り　/bin/sh編

久々の時代遅れひとりFizzBuzz祭り、今回は/bin/sh。要はシェルスクリプト。前回のTclとの繋がりは……何となく雰囲気が似ているから。まあ元々TclはUnixアプリケーションの標準の拡張スクリプト言語としてデザインされたらしいだが、シェルスクリプトはUnix環境でポピュラーな伝統的プログラマブル・ツールの1つなので、参考にした可能性は低くはないと思う*1。

実はシェルスクリプトを書く機会は少ない。長時間作業する環境がWindowsな為、バッチファイルを書く方が多い。MinGW、MSYS、GnuWin32の各種ツールの混成で独自のUnixライク環境を作っているので*2、色々と制約が多いことも理由の一つだ。

あまりにも書く機会が少ないのでなかなか上達せず、シェルスクリプトを書いたり修正したりする時はいつも苦労する。でも、本心ではバッチファイルより/bin/shなシェルスクリプトを選びたい。でも選べない。ああ、アンビバレンス。

そんな背景もあって、今回のFizzBuzzはリハビリを兼ねている。動作環境はMSYS付属のbash 2.04上で、bashの実行ファイル名をsh.exeに変更したものを使用している。

#!/bin/sh

pfizbuz() {
	RETVAL=$1

	if [ `expr $1 % 3` -eq 0 ]; then
		RETVAL=Fizz
	fi
	if [ `expr $1 % 5` -eq 0 ]; then
		RETVAL=Buzz
	fi
	if [ `expr $1 % 15` -eq 0 ]; then
		RETVAL=FizzBuzz
	fi

	echo $RETVAL
}

i=1
while [ $i -le 100 ]
do
	pfizbuz $i
	i=`expr $i + 1`
done

遅い。手元のWindows環境*3では、全て表示されるまで30秒強掛かる。正直発狂したくなる状況だ。

Intel Atom 330マシン*4上のUbuntu 8.04LTSでも試してみた所、圧倒的に速くなったものの、それでもgawkなどで書いたFizzBuzzと比べると目に見えて分かる程度には遅い。gawk版は一瞬で終わるが、このシェルスクリプトだと文字が流れていくことが分かる速度だ。

これは何とかしなくてはならない。

一体、何が原因だろうか？　恐らく最も高くついているのはコマンドの実行だろう。組み込み関数やシェル関数以外のコマンドを実行する時に毎回プロセスが生成されているはずだし、多分プロセス生成の度にウイルスバスター2009の監視網に引っかかっているので*5、その分だけ遅くなっているはずだ。

ということで、まずpfizbuz内でのexprの呼び出し回数をほんの少し減らしてみた。

#!/bin/sh

pfizbuz() {
	RETVAL=$1

	if [ `expr $1 % 15` -eq 0 ]; then
		RETVAL=FizzBuzz
	elif [ `expr $1 % 3` -eq 0 ]; then
		RETVAL=Fizz
	elif [ `expr $1 % 5` -eq 0 ]; then
		RETVAL=Buzz
	fi

	echo $RETVAL
}

i=1
while [ $i -le 100 ]
do
	pfizbuz $i
	i=`expr $i + 1`
done

しかし目に見える効果は確認できなかった。

念の為、シェル変数を毎回定義するのも止めてみた。

#!/bin/sh

pfizbuz() {
	if [ `expr $1 % 15` -eq 0 ]; then
		echo FizzBuzz
	elif [ `expr $1 % 3` -eq 0 ]; then
		echo Fizz
	elif [ `expr $1 % 5` -eq 0 ]; then
		echo Buzz
	else
		echo $1
	fi
}

i=1
while [ $i -le 100 ]
do
	pfizbuz $i
	i=`expr $i + 1`
done

これも効果なし。やはり小手先の変更では効果はない。

ということで発想を変えてみた。pfizbuz本体ではなく、呼び出し側に問題があるのではないか？　よく見てみたら、ループの時にexprでカウントアップしている。これは無駄だ。

#!/bin/sh

pfizbuz() {
	if [ `expr $1 % 15` -eq 0 ]; then
		echo FizzBuzz
	elif [ `expr $1 % 3` -eq 0 ]; then
		echo Fizz
	elif [ `expr $1 % 5` -eq 0 ]; then
		echo Buzz
	else
		echo $1
	fi
}

for i in `seq 1 100`
do
	pfizbuz $i
done

なのでseqで1〜100まで一気に生成するようにしてみた。このスクリプトだと実行時間は20秒程度で、10秒ぐらい短縮されたことになる。

ちなみにこんな書き方もできる。

#!/bin/sh

pfizbuz() {
	if [ `expr $1 % 15` -eq 0 ]; then
		echo FizzBuzz
	elif [ `expr $1 % 3` -eq 0 ]; then
		echo Fizz
	elif [ `expr $1 % 5` -eq 0 ]; then
		echo Buzz
	else
		echo $1
	fi
}

seq 1 100 |
	while read i
	do
		pfizbuz $i
	done

但し、気がつかない程度だが、パイプを一段挟む分だけ微妙に遅くなるようだ。

10秒の短縮に成功したので、更なる短縮に挑んでみた。またまた小手先の変更だが、exprで求めた剰余を文字列として比較してみた。比較対象の2つの文字列を数値に変換してから比較するのと、そのまま文字列として比較するのでは、どちらが負荷が高いのだろうか？

#!/bin/sh

pfizbuz() {
	if [ `expr $1 % 15` = '0' ]; then
		echo FizzBuzz
	elif [ `expr $1 % 3` = '0' ]; then
		echo Fizz
	elif [ `expr $1 % 5` = '0' ]; then
		echo Buzz
	else
		echo $1
	fi
}

for i in `seq 1 100`
do
	pfizbuz $i
done

試してみたが、このケースでは特にこれといった差は無いようだった。

やはり、pfizbuz内部でのコマンドの実行回数を減らすしか、高速化は実現できないようだ。極力シェル組み込みの関数やシェル関数を使用するように変更することで、何とか高速化できないものか、試してみた。

#!/bin/sh

FIZVAL=`seq -s ' ' 3 3 100`
isfizz() {
	for i in $FIZVAL
	do
		if [ $i = $1 ]; then
			FIZVAL=`echo $FIZVAL | sed -e 's/^[0-9]*[ ]*//'`
			return 0
		fi
		break
	done
	return 1
}

BUZVAL=`seq -s ' ' 5 5 100`
isbuzz() {
	for i in $BUZVAL
	do
		if [ $i = $1 ]; then
			BUZVAL=`echo $BUZVAL | sed -e 's/^[0-9]*[ ]*//'`
			return 0
		fi
		break
	done
	return 1
}

isfizbuz() {
	for i in $BUZVAL
	do
		if [ $i = $1 ]; then
			for j in $FIZVAL
			do
				if [ $j = $1 ]; then
					FIZVAL=`echo $FIZVAL | sed -e 's/^[0-9]*[ ]*//'`
					BUZVAL=`echo $BUZVAL | sed -e 's/^[0-9]*[ ]*//'`
					return 0
				fi
				break
			done
		fi
		break
	done
	return 1
}

pfizbuz() {
	if isfizbuz $1; then
		echo FizzBuzz
	elif isfizz $1; then
		echo Fizz
	elif isbuzz $1; then
		echo Buzz
	else
		echo $1
	fi
}

for i in `seq 1 100`
do
	pfizbuz $i
done

コードが随分長くなった。実行時間は7〜8秒程度。FizzBuzzと表示されるときに動作が引っかかるのはご愛嬌、ということで勘弁してほしい。

改良の余地はありそうだけど、これで終了。というかシェルスクリプトの中にPerlやgawkのスクリプトを埋め込む方が手っ取り早くて且つ高速に動作するはずなので、これ以上あれこれ試行錯誤する気が起きない。

#!/bin/sh

seq 1 100 | gawk '
{
	str = ""
	if ($0 % 3 == 0)
		str = "Fizz"
	if ($0 % 5 == 0)
		str = str "Buzz"

	print str == "" ? $0 : str
}'

このコードの方が短いし、（awkを知っている人には）分かりやすい。しかも高速に動作する。まあこれもシェルスクリプト本来の使い方の1つ、ということか。

*1:但し本当のところは調べていないので不明。

*2:Cygwinの類はWindowsとの親和性がイマイチだし、仮想環境にLinux等を入れて作業するにはハードウェアのスペックが足りない。

*3:DELL Inspiron 2200のWindows XP SP3上でMSYSのbashを使用した場合。Pentium M 1.7GHz、内蔵メモリとPC2700 DDRメモリを合わせて1280MB搭載。ついでにウイルスバスター2009が稼働中。

*4:Intelの例のボードを使ったやつ。メモリは2GB。

*5:実際にウイルスバスターを止めて実行した所、実行時間が半分になった。