キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ring
お題は「100までの整数から素数を列挙せよ」です.
に対して
mputの日記。 - キミならどう書く 2.0 - ROUND 1 -100までではちょっと上が小さすぎる。「最初の1,000,000個」とかに変更すべき。ここまで大きければHaskellでも素朴なsieveでは表示できなくなる*1ので、腕の見せ所となる。
というツッコミが来たので、Haskell記事がunder constructionということもあってやってみた。
ただし、他との整合性から、「最初の1,000,000個」ではなく、「1,000,000までの素数」にしてある。この程度であれば、特に工夫を凝らさなくても...
エラトステネスのふるい @ Ruby - 32nd diary (2006-06-16)追記.ええと,「最初の1,000,000個」とかに変更すべき。という意見もあるようですが,少人数で腕を競いたいわけではなく,みんなで盛り上がろうという趣旨ですので100までということになりました.ご理解ください.
...皆で楽しむことが出来るので。また、以下のソースコードを「最初の1,000,000個」に変更するのはTrivialだ。
perl 5.8.8
use strict; use warnings; my @primes; sub is_prime{ my $n = shift; for my $d (@primes){ last if $d*$d > $n; return unless $n % $d; } push @primes, $n; return $n; } my $max = shift || 100; is_prime($_) for (2 .. $max); print join(" ", @primes), "\n";Mac OS X 10.4.6 @ MacBook Pro Intel Core Duo 2.0GHz
8.76 real 8.08 user 0.02 sys 0 maximum resident set size 0 average shared memory size 0 average unshared data size 0 average unshared stack size 0 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 521 voluntary context switches 0 involuntary context switches
MacOS Xの/usr/bin/time -lは見てのとおりあまり参考にならないので、以下-lなしのみ。全部521 voluntary context switchesってのもなんだかなあ。
FreeBSD 6.1 @ Dual Xeon 2.8MHz9.96 real 9.84 user 0.03 sys 6912 maximum resident set size 7 average shared memory size 1492 average unshared data size 127 average unshared stack size 1419 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 406 voluntary context switches 1328 involuntary context switches
python 2.4.3
pythonのjoinの仕様は毒々しい。
import sys primes = [] def is_prime(n): for d in primes: if d * d > n: break if n % d == 0: return 0 primes.append(n) return n max = 100 if len(sys.argv) == 2: max = int(sys.argv[1]) for i in range(2,max): is_prime(i) # not primes.join(" ") -- I love to hate python! # not " ".join(primes) print " ".join(map(str, primes))Mac OS X 10.4.6 @ MacBook Pro Intel Core Duo 2.0GHz
10.30 real 10.21 user 0.05 sysFreeBSD 6.1 @ Dual Xeon 2.8MHz
9.07 real 8.71 user 0.09 sys 20156 maximum resident set size 657 average shared memory size 17582 average unshared data size 128 average unshared stack size 4843 page reclaims 40 page faults 0 swaps 17 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 470 voluntary context switches 1198 involuntary context switches
ruby 1.8.4
コードはきれいだが、ちょっと遅め。OS Xだと高速なのはなぜ?
@primes = [] def is_prime(n) @primes.each do |d| break if d * d > n return 0 if n % d == 0 end @primes.push(n) return n end max = ARGV.size == 1 ? ARGV[0].to_i : 100 (2 .. max).each{|i| is_prime(i) } puts @primes.join(" ")Mac OS X 10.4.6 @ MacBook Pro Intel Core Duo 2.0GHz
13.65 real 13.49 user 0.02 sysFreeBSD 6.1 @ Dual Xeon 2.8MHz
24.23 real 23.60 user 0.02 sys 3036 maximum resident set size 4 average shared memory size 885 average unshared data size 128 average unshared stack size 551 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 415 voluntary context switches 2691 involuntary context switches
ANSI C
やはりぶっちぎりの速さ!
他との整合性を保つためになんちゃってjoin()を実装して使っているが、モノホンが欲しいなあ。
#include <stdio.h> #include <string.h> #define PRIMEBUFSIZ 1024*1024 #define CHARBUFSIZ 1024*1024 static int nprimes = 0; static int primes[PRIMEBUFSIZ]; int is_prime(int n){ int i, d, p; for (i = 0; i < nprimes; i++){ p = primes[i]; if (p * p > n) break; if (n % p == 0) return 0; } primes[nprimes++] = n; return n; } char *join(char *dst, int *array, int items){ char dbuf[16]; int i; for (i = 0; i < items; i++){ sprintf(dbuf, "%d ", array[i]); strncpy(dst, dbuf, 16); dst += strlen(dbuf); } return dst; } int main(int argc, char **argv){ int i; int n = 100; char obuf[CHARBUFSIZ], *tail; if (argc > 1) n = atoi(argv[1]); for (i = 2; i <= n; i++) is_prime(i); tail = join(obuf, primes, nprimes); *tail = '\n'; fputs(obuf, stdout); }Mac OS X 10.4.6 @ MacBook Pro Intel Core Duo 2.0GHz
0.34 real 0.29 user 0.01 sysFreeBSD 6.1 @ Dual Xeon 2.8MHz
0.33 real 0.24 user 0.02 sys 1404 maximum resident set size 4 average shared memory size 559 average unshared data size 1219 average unshared stack size 267 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 407 voluntary context switches 87 involuntary context switches
Haskell (GHC 6.4.1/6.5-Beta on OS X)
そして、問題のHaskell。まずNaiveな実装。
import System.Environment main = do args <- getArgs let n = if length args == 1 then read $ args !! 0 else 100 putStrLn $ unwords $ map show $ takeWhile (\x -> x <= n) primes primes = sieve [2..] sieve (p:xs) = p:(sieve [ x | x <- xs, x `mod` p /= 0])
やってみればわかるが、1,000,000までの素数とかだと、遅くて話にならない。これは、n-1以下の全素数をない方表記、じゃない内包表記中で使っているため。ちゃんと「sqrt(n)以下の素数までチェックすればOK」という条件をなんとか実装したらどうなるか?
import System.Environment main = do args <- getArgs let n = if length args == 1 then read $ args !! 0 else 100 putStrLn $ unwords $ map show $ takeWhile (\x -> x <= n) primes primes = 2 : filter sieve [3..] where sieve x = all primeTo $ takeWhile lessThanSquare primes where primeTo y = mod x y /= 0 lessThanSquare z = z * z <= xMac OS X 10.4.6 @ MacBook Pro Intel Core Duo 2.0GHz
2.94 real 2.91 user 0.02 sysFreeBSD 6.1 @ Dual Xeon 2.8MHz
6.27 real 6.26 user 0.00 sys 5828 maximum resident set size 301 average shared memory size 36 average unshared data size 128 average unshared stack size 1213 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 313 signals received 1 voluntary context switches 76 involuntary context switches
OS Xが高速なのは、6.5 Betaを使っているからだろうか?
1,000,000個目の素数は15,485,863
ちなみに、takeWhile (\x -> x <= n) primesをtake n primesに書き換えるだけで、このscriptは「素数1,000,000個」を表示するようになる。
FreeBSD 6.1 @ Dual Xeon 2.8MHz216.53 real 215.31 user 0.36 sys 58772 maximum resident set size 300 average shared memory size 36 average unshared data size 128 average unshared stack size 14437 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 10771 signals received 1 voluntary context switches 7929 involuntary context switches
そんな悪くないではないか。ちなみにCではこうなった。高速化のため、なんちゃってjoin()は使っていない。mainのみ示す。
int main(int argc, char **argv){ int i; int n = 100; if (argc > 1) n = atoi(argv[1]); for (i = 2; nprimes < n; i++) is_prime(i); for (i = 0; i < n; i++){ printf("%d ", primes[i]); } printf("\b\n"); /* \b is such a dirty hack */ }FreeBSD 6.1 @ Dual Xeon 2.8MHz
11.01 real 10.98 user 0.02 sys 4504 maximum resident set size 4 average shared memory size 4100 average unshared data size 128 average unshared stack size 1036 page reclaims 0 page faults 0 swaps 0 block input operations 0 block output operations 0 messages sent 0 messages received 0 signals received 1 voluntary context switches 557 involuntary context switches
これならPerlでも行けそうだ。やはりmain相当の部分のみ示す。
for (my $n = 2; @primes < $max; $n++){ print $n, " " if is_prime($n) } print "\b\n";FreeBSD 6.1 @ Dual Xeon 2.8MHz
345.64 real 344.65 user 0.13 sys 26000 maximum resident set size 7 average shared memory size 14892 average unshared data size 127 average unshared stack size 6145 page reclaims 0 page faults 0 swaps 0 block input operations 62 block output operations 0 messages sent 0 messages received 0 signals received 6 voluntary context switches 30162 involuntary context switches
ざっとこんなところかな。
Dan the Prime Lightweight Linguist
Javascript
追記した。やはりbrowserでdemoを見れるのはいい。
Javascriptなので、Prototypeとして作ってある。
function Prime(){ this.primes = []; this.init = function() { this.primes = []; }; this.is_prime = function(n){ for (var i = 0; i < this.primes.length; i++){ var d = this.primes[i]; if (d * d > n) break; if (n % d == 0) return 0; } this.primes.push(n); return n; }; this.find_primes = function(n){ this.init(); for (i = 2; i <= n; i++) this.is_prime(i); return this.primes }; }までの素数:
2 3 5 7
直しました。この場合、primesでも動いちゃうのが問題ですね。join()の定義が別ファイルとかにあればすぐにわかる潜在バグではありますが。
Dan the Enbugger