Blog/2006-6-17

トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

Linux

LLR2006 - 1,000,000(番目|まで)の素数

速度が遅いのは awk の関数の少なさが起因しているし、仮に作ったとしても裏目に出て遅くなってしまうケースが非常に多いので、細かな部分は気にしないように。(w

やっている内容は小飼さんの Blog のものと同じなのですが、何箇所か異なる点があって、

  • function の内部を for a in arr でループさせていない
  • join がない (w

くらいですかね。

#! /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 で走らせると awk での速度は大敗でした。

$ 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

ライブラリなど…

ライブラリなど花拳繍腿自作こそ王者の技よ

わろた。(w

さんくすです。

嫁曰く、

素数って直感で思いつくものでは!?
計算するにしても、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;
}

嫁の頭の中はこんな感じだろうか? (嫁の脳だと計算に 1 時間くらいかかったが…)

いくつか考えたのですが、個人的にこれが一番好きですね。
最初に素数を習ったものと同じ感じがします。

確かに適したアルゴリズムとか、for ループの脱出のタイミングだとか、いろいろあるけれど、人の脳に近い気がします。

SMON Linux Tips: quicktimeを動かす

やっぱりグレーだよなぁ。

デスクトップは Windows の方が苦労はすくなさそう。

ネタ

目が悪くなった?

今まで MS ゴシック 9 pt だったけど、11 pt に putty の表示を変更。
並べて見られないのは厳しいけど、仕方ないか。

ガントチャートは突然に

MS Project も Planner (Mr Project) もイマイチなんだよなぁ。
個人的にはプロジェクト・工程管理ソフトウェア M1forWindowsクラスが欲しいと思うわけです。
trac なんかと合体してくれるといいのに…。

ただし、問題は部長の欲しいフォーマットでないので、全部部長に合わせて手書きせざるを得ないことかな。
これを無駄と言わずして何を無駄と言う。

何か変だ

もし日本がブラジルに勝ったら、湘南で、 スクール水着で、Jupiterを歌います!!

え〜と、釣られてもいい〜。(w


コメント

{{comment multi|w}}