Python, Ruby, awk

つづき

素数計算するプログラムを awk でも書いてみた。普通に書くと BEGIN{} の中に全部書くことになりそうだけど、それだと awk らしくないので、

function is_prime(n) {
    j = 2
    if (n < 2) return false
    while (j*j <= n)
    {
	if (n % j == 0)
	    return false
	else
	    j++
    }
    return true
}

BEGIN{
    c = 0;
}

{
    if (is_prime($0)) {
	prime[c++] = $0
    }
}

として以下のように実行してみた。１段目の awk は整数を生成するだけ。２段目はパイプで受け取った数字の素数判定をするだけ。また、計算速度を比較するために、print はやめて、配列に素数を保存するだけにした。

$ time gawk 'BEGIN{for (i=1; i<=1000000; i++) print(i)}' | gawk -f prime.awk

real 0m14.624s
user 0m14.940s
sys 0m0.071s

実行時間はおよそ 15秒。

Python だと約10秒。

$ time python prime.py

real 0m10.286s
user 0m10.151s
sys 0m0.063s

一応コードも上げておく。

def is_prime(n):
    if n <2:
        return False
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        else:
            i += 1
    return True

prime =[]
for i in range (1000000):
    if is_prime(i):
        prime.append(i)

Ruby はなんと3秒。

$ time ruby prime.rb

real 0m3.081s
user 0m2.997s
sys 0m0.047s

コードはこちら。

class Integer
  def is_prime()
    if self < 2 then
      return false
    end
    i = 2
    while i*i <= self
      if self % i == 0
        return false
      else
        i += 1
      end
    end
    true
  end
end

prime = []
for i in 1..1000000 do
  if i.is_prime()
    prime.push(i)
  end
end

こんなに差がつくとは思いませんでした。ちなみに、awk を全部 BEGIN{} に入れてしまうと

function is_prime(n) {
    if (n < 2) return false
    j = 2
    while (j*j <= n)
    {
	if (n % j == 0)
	    return false
	else
	    j++
    }
    return true
}

BEGIN{
    for (i=1; i<=1000000; i++){
	if (is_prime(i))
	    prime[c++] = $0
    }
}

$ time gawk -f prime2.awk

real 0m15.649s
user 0m14.805s
sys 0m0.219s

パイプで渡したときとほぼ同じだけど、ちょっとだけ遅くなりました。