Hatena::ブログ(Diary)

DoMshi

カテゴリー
 | 

2009年4月8日(水)

[]Python+Psycoが速い

Python勉強にと思って素数を洗い出すプログラムを書いた。

そしたら結構速いことが分かった。

面白くなって他の言語と比較してみた。

プログラムコマンドライン引数で指定された上限(のようなもの)までの素数を洗い出すもので

上限を10000000として速度を計測した。

言語時間
Python(Psycoあり)21秒
Python(Psycoなし)137秒
Ruby(1.8)上限1000000で37秒
Ruby(1.9)上限1000000で23秒
Ruby(svn:rev23170からmake)133秒
PHP134秒
Java(OpenJDK6が最速)10.2秒
C++5.0秒
C5.0秒
D6.2秒
Lua(5.1でしか動かない)116秒
Perl96秒

先頭に二行足すだけでこの速度。すごい。

(Psycoは実行時に関数コンパイルしてくれるらしい)

Python

import psyco
psyco.full()
import sys

def isprime(n, primes):
        sqrt = n ** 0.5
        for i in primes:
                if sqrt < i: break
                if n % i == 0: return False
        return True

def main():
        primes = []

        for i in range(2, int(sys.argv[1])):
                if isprime(i, primes):
                        primes.append(i)

main()

Ruby

def isprime(n, primes)
        sqrt = n ** 0.5
        for i in primes
                break if sqrt < i
                return false if n % i == 0
        end
        return true
end

primes = []

for i in 2..ARGV[0].to_i
        primes.push(i) if isprime(i, primes)
end

PHP

<?
function isprime($n, &$primes){
        $sqrt = sqrt($n);
        foreach($primes as $i){
                if($sqrt < $i){ break; }
                if($n % $i == 0){ return false; }
        }
        return true;
}

$lim = $argv[1];
$i = 2;
$primes = array();
while($i < $lim){
        if(isprime($i, $primes)){ array_push($primes, $i); }
        $i++;
}

Java

import java.util.*;

class test {
        static boolean isprime( int n, ArrayList<Integer> primes ) {
                int sqrt = (int) Math.sqrt( n );
                for ( Integer i: primes ) {
                        if ( sqrt < i ) {
                                break;
                        } else if ( n % i == 0 ) {
                                return false;
                        }
                }
                return true;
        }

        public static void main( String args[] ) {
                Integer i = 2;
                int lim = Integer.parseInt( args[0] );
                ArrayList<Integer> primes = new ArrayList<Integer>();

                while ( i < lim ) {
                        if ( isprime ( i, primes ) ) {
                                primes.add( i );
                        }
                        i += 1;
                }
        }
}

C++

#include<cstdlib>
#include<cmath>
#include<vector>

bool isprime(int n, std::vector<int> *primes)
{
        int nsqrt = sqrt(n);
        for(std::vector<int>::iterator it = primes->begin(); it != primes->end(); it++){
                if(nsqrt < *it) { break; }
                if(n % *it == 0) { return false; }
        }
        return true;
}

int main(int argc, char *argv[])
{
        int i = 2;
        int lim = atoi(argv[1]);
        std::vector<int> primes;

        while(i < lim){
                if(isprime(i, &primes)){ primes.push_back(i); }
                i += 1;
        }

        return 0;
}

C

#include <stdlib.h>
#include <math.h>

int isprime(int n, int *primes, int len)
{
        int nsqrt = (int) sqrt((double) n);
        int i = 0;
        while(i < len){
                if(nsqrt < primes[i]){ break; }
                if(n % primes[i] == 0){ return 0; }
                i++;
        }
        return 1;
}

int main(int argc, char *argv[])
{
        int lim = atoi(argv[1]);
        int *primes = (int *) malloc(sizeof(int) * (lim / (log((double)lim) - 2)));
        int len = 0;
        int i = 2;

        while(i < lim){
                if(isprime(i, primes, len)){
                        primes[len] = i;
                        len++;
                }
                i++;
        }

        return 0;
}

D

import std.conv;
import std.math;

bool isprime(int n, int[] primes)
{
        int nsqrt = cast(int) sqrt(cast(real) n);
        foreach(int i; primes){
                if(nsqrt < i){ break; }
                if(n % i == 0){ return false; }
        }
        return true;
}

int main(string[] args)
{
        int i = 2;
        int[] primes;
        int lim = toInt(args[1]);

        while(i < lim){
                if(isprime(i, primes)){ primes ~= i; }
                i += 1;
        }

        return 0;
}

Lua

function isprime(n, primes)
        nsqrt = n ^ 0.5
        for i = 1, #primes do
                if nsqrt < primes[i] then break end
                if n % primes[i] == 0 then return false end
        end
        return true
end

primes = {}

for i = 2, arg[1] * 1 do
        if isprime(i, primes) then primes[#primes + 1] = i end
end

Perl

sub prime{
        $sqrt = sqrt($i);
        foreach(@primes){
                last if $sqrt < $_;
                return 0 if $i % $_ == 0;
        }
        return 1;
}

$i = 2;
$lim = @ARGV[0] * 1;
@primes = ();

while($i < $lim){
        push(@primes, $i) if &prime;
        $i += 1;
}

追記

Ruby1.9はもっと速い」との指摘があったので、svnから落としてmakeしたもので測ったところ、通常の3倍くらいの速度になりました。

バージョンが古かった(全てUbuntu 8.04のリポジトリのものを使いました)のがいけなかったかも知れません。

morchinmorchin 2009/04/10 13:40 Cythonはどうですか?恐らくC++との速度差はpsyco以上に縮まると思います。
http://d.hatena.ne.jp/morchin/20081029#p1

sanjaposanjapo 2009/05/23 09:52 無知で申し訳ございません。
質問させてください。
RUBYの場合は何故、上限が違うのでしょうか。
どうぞよろしくおねがいします。

pclpcl 2009/07/07 17:18 遅すぎて測る気が起こらなかったからです。
今思うと邪魔なだけなので気が向いた時に普通に測ります。

 |