BBS-BBS/44
キミならどう書く 2.0 - ROUND 1 - まとめ - さいとう (2006年06月26日 23時45分26秒)
はじめに
LL Ring の前哨戦として「キミならどう書く 2.0 - ROUND 1 -」という内容のイベントが催され、6/26 時点ではコメントに書き込んだ方が 23 名、トラックバックが 65 名と非常に盛況のうちに終了のゴングが鳴らされました。
100 までの整数から素数を列挙せよ
このお題は「高橋メソッド」でお馴染みの (いや、Ruby, RoR で有名な) 高橋さんのアイデアを高野さんがアレンジしたものです。
さて、素数って何でしょうか?因数分解を習う中学の時に習ったのですが、なかなか言葉にすると難しいです。Wikipedia による素数を見ると、以下のように書かれています。
素数（そすう）とは、1とその数自身以外に正の約数を持たない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のことである。
さて、実はここに出題者の引っ掛けがありました。1 は素数ではないのです。これに気が付けば 1 を特別扱いするよりも最初から除外した方が楽になります。
具体的には、
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
が素数になります。
普通に考えてみよう
ここにも書いた内容ですが、私の嫁が言うには、
素数って直感で思いつくものでは!?
だそうです。直感と言うよりも、整数 n を 2 から n -1 までで割っていって、割り切れなければ n は素数ということを頭の中で行っていたそうです。
つまり、
#! /usr/bin/gawk -f
BEGIN {
for ( num = 1; num <= 100; num++ ) {
for ( div = 2; div <= num; div++ ) {
if ( num % div == 0 ) {
if ( num != div ) {
break;
} else {
printf( "%d ", num );
}
}
}
}
print;
}
という計算を脳内で行っていたことになります。時間のかかるアルゴリズムですが、非常に素直で誰にも分かりやすいものだと言えます。
さて、分かりやすいのですが、本当に整数 n までの全ての値を検査していく必要があるのでしょうか?答えは NO です。キミならどう書く 2.0 - ROUND 1 - の各言語の解答に多く書かれているように、中の for ループで break で脱出する際には、以下のように div * div > num で脱出させると計算量が少なくなります。
for ( div = 2; div <= num; div++ ) {
if ( div * div > num ) {
return num;
break;
}
if ( num % div == 0 ) {
return 0;
}
}
エラトステネスの篩
Wikipedia によれば「エラトステネスの篩」という素数計算方法があります。
例えば、素数 2 で割り切れるものは最初に除外してしまい、次に素数 3 で割り切れるものは除外して…と徐々に篩 (ふるい) にかけていくようにして計算することからこのように呼ばれます。
awk での解法は以下のようになります。
#! /usr/bin/gawk -f
BEGIN {
max = 100;
for ( i = 2; i <= max; i++ ) {
num_arr[i] = i;
for ( j = 2; j <= max; j++ ) {
if ( num_arr[i] % j == 0 && num_arr[i] != j ) {
num_arr[i] = 0;
}
}
}
for ( i = 2; i <= max; i++ ) {
if ( num_arr[i] != 0 ) {
printf( "%d ", num_arr[i] );
}
}
print;
}
「エラトステネスの篩」にまだ残っているかどうかの情報を保持しなけえばならないため、配列を用いています。主要 LL と異なり、awk には配列操作関数が充実していません。そこで、古いから落ちたものを 0 として、あとで数え上げる時に 0 のものを除外する方法を用いています。
当然、ここでは配列を用いるため、非常に大きな数を処理する場合、大量のメモリも同時に消費してしまいます。
awk にも配列操作関数が欲しいところですが、その配列または文字列、数値列に値が入っているかどうかを検査する関数があれば、自分で書けそうな気もします。
ライブラリなど花拳繍腿、自作こそ王者の技よ
とは Ruby をはじめ多くの言語で活躍されている木村さんがパロディとして使った言葉ですが、ライブラリの少ない awk だからこそ、アルゴリズムを作る人の腕が試されるわけです。
LLR2006 - 1,000,000(番目|まで)の素数
Perl の jcode.pm や encode.pm で有名な小飼さんが、Perl5, Python, Ruby, ANSI C, Haskell, Javascript で記載されています。
同じように awk でも記載してみました。ほとんど同じアルゴリズムを使うことで、言語間の比較が容易になります。ただ、少し異なっており、
- function の内部を for a in arr でループさせていない
- awk には join がない
という部分が異なります。前者は awk の場合、配列の要素数に変更があっても、それをダイナミックに for a in arr の中で変更できないからです。(合ってます?)
#! /usr/bin/gawk -f
BEGIN {
max = 100;
if ( ARGC == 2 ) {
max = ARGV[1];
}
for ( i = 2; i <= max; i++ ) {
is_prime( i );
}
for ( i = 1; i <= num_prime; i++ ) {
printf( " %s", prime[i] );
}
print;
}
function is_prime( n ) {
for ( d = 1; d <= num_prime; d++ ) {
if ( prime[d] * prime[d] > n ) {
break;
}
if ( n % prime[d] == 0 ) {
return 0;
}
}
prime[++num_prime] = n;
return n;
}
三大言語との速度比較
手元の Celeron 600 MHz の Fedora Core 5 マシンで試すと以下のようになりました。
Perl, Python, Ruby のコードは LLR2006 - 1,000,000(番目|まで)の素数に掲載されていたものをそのまま用いています。
$ time perl prime.pl 1000000 > /dev/null real 0m30.795s user 0m30.634s sys 0m0.080s $ time ruby prime.rb 1000000 > /dev/null real 1m3.633s user 0m58.136s sys 0m0.192s $ time python prime.py 1000000 > /dev/null real 0m31.086s user 0m29.418s sys 0m0.228s $ time gawk -f prime_number_7.awk 1000000 > /dev/null real 1m28.382s user 1m23.109s sys 0m0.176s
awk は惜敗という結果になりましたが、同じものを One True AWK で行ってみると、さらに遅い結果となりました。つまり、gawk はオリジナルの awk と比較してかなり最適化されているのではないでしょうか?
以下が One True AWK の結果です。
$ time ~/bin/awk -f prime_number_7.awk 1000000 > /dev/null real 3m7.120s user 2m59.355s sys 0m0.396s
is_prime() を作っておきましょう
せっかくなので、上の is_prime() をいつでも使えるようにしておきましょう。
#! /usr/bin/gawk -f
BEGIN {
print is_prime( 13 );
print is_prime( 14 );
}
#=====================================================================
# is_prime()
# - return number, if it is prime number.
# - return 0, if it is not prime number.
function is_prime( num, div ) {
for ( div = 2; div <= num; div++ ) {
if ( div * div > num ) {
return num;
break;
}
if ( num % div == 0 ) {
return 0;
}
}
}
#=====================================================================
頻繁に使う関数とも思えませんが、載せておきます。
まとめ
素数を計算する方法を見てきたわけですが、いかがでしたでしょうか?キミならどう書く 2.0 - ROUND 1 - にはさまざまな言語で記述された素数計算方法が掲載されています。
義務教育を受けた人であれば誰でも知っている素数ですが、それをアルゴリズムにして表現する難しさ…いや、楽しさを味わってもらえたのではないでしょうか?
最後に Donald E. Knuth の台詞で終わりにします。
It has been often said that a person does not really understand something until he teaches it to someone else. Actually a person does not really understand something until he can teach it to a computer, i.e., express it as an algorithm.
以下、翻訳です。
よく他の誰かに教えるまで、人が本当に何であるかを理解していないと言われます。それをコンピュータに教えることができるまで、実際に人は本当に何であるかを理解していません、すなわち、アルゴリズムとしてそれを言い表してください。
コメント
{{comment multi|w}}