追記@2016/06/29:: 実は posix 対応じゃなかった。。ので、それを修正。
動機
エラトステネスの篩を実装してみようと思い立った。せっかくなので、20年後もポータブルに動くように、 POSIX の範囲でシェルスクリプトで実装してみようと思い立った。
最初の実装: 関数型っぽく
シェルには標準入力・標準出力・パイプの機構がある。これらを組み合わせれば、関数型っぽく、簡潔に、記述できるのではないか、と思い立って実装してみた。
#!/bin/sh
# usage: ./primes.sh THE_MAX_INT
elato_filter() (
read n &&
echo $n &&
awk '$1 % '$n' != 0 { print $1 }' | elato_filter
)
seq 2 "$1" | elato_filter
素晴らしく簡潔に記述できたので、ウキウキしながら実行した結果が次。
$ ./primes1.sh 100000
2
3
5
7
(略)
2833
./primes1.sh: 9: ./primes1.sh: Cannot fork
というわけで、篩のかずだけプロセスを実行している== fork しているので、ある種の fork 爆弾の様相を呈して、最後には fork の限界数に達して死亡した。
(与える数字が小さければ、正しく動きますヨ。。)
次の実装: 仕方がないので while loop で
fork をしなければいいよね!ということで、上の実装を while 文に直したものが次。パイプで並列実行するのではなく、一回一回計算しきって、その結果を変数に収納した。
#!/bin/sh
# usage: ./primes.sh THE_MAX_INT
candidates=$(seq 2 $1)
next_prime=2
view_candidates() {
cat <<EOF
$candidates
EOF
}
# sieve prime
sieve() {
awk '$0 % '$1' != 0 { print $0 }'
}
while ! [ -z "$next_prime" ]
do
echo $next_prime
candidates=$(view_candidates | sieve $next_prime)
next_prime=$(view_candidates | head -n 1)
done
ちょっと冗長になったけれども、きちんと POSIX の範囲ないで記述できたので、喜びながら実行した結果が次。
$ ./primes2.sh 100000
2
3
5
(略)
$ ./primes2.sh 1000000
(略)
というわけで、きちんと動くようにはなったが、動きがちょっともっさりしている。
で、結局。。 -> すべて awk で
#!/bin/sh
if [ $# -ne 1 ]
then
echo "usage: $0 MAX_INT" 1>&2
exit 1
fi
awk -v upper=$1 '
function is_empty(arr) {
for(elem in arr)
return 0
return 1
}
BEGIN {
for(i=2; i<=upper; i++)
candidates[i] = 1
next_prime=2
while (1) {
print next_prime
for(j=next_prime; j<= upper; j += next_prime) {
delete candidates[j]
}
if(is_empty(candidates))
break
while(!(next_prime in candidates))
next_prime++
}
}'
$ ./primes-awk.sh 1000000
2
3
5
(略)
999983
十分に高速に実行できるようになりました。
結論
POSIX シェルスクリプトで計算をごりごりやりたくなったら awk を使いましょう。