POSIX 互換シェルスクリプトでのエラトステネスの篩いろいろ

追記@2016/06/29:: 実は posix 対応じゃなかった。。ので、それを修正。

動機

エラトステネスの篩を実装してみようと思い立った。せっかくなので、２０年後もポータブルに動くように、 POSIX の範囲でシェルスクリプトで実装してみようと思い立った。

最初の実装: 関数型っぽく

シェルには標準入力・標準出力・パイプの機構がある。これらを組み合わせれば、関数型っぽく、簡潔に、記述できるのではないか、と思い立って実装してみた。

primes1.sh

#!/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 文に直したものが次。パイプで並列実行するのではなく、一回一回計算しきって、その結果を変数に収納した。

primes2.sh

#!/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 で

primes-awk.sh

#!/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 を使いましょう。