今回はn番目までの素数をリストに格納し続けるプログラムを使用してpythonとJavaの速度の比較をしていきます。
目次
素数生成
コードが長くなるのでエラトステネスの篩は使わずに、素数判定の探索範囲をsqrt(num)にして無駄な処理を省きます。
Python
Python + 通常配列
import math
import time
class Prime:
def __init__(self,n) -> None:
self.n = n
self.array = []
pass
def isPrime(self,num):
i = 2
while i<=math.sqrt(num):
if num%i == 0:
return False
i += 1
return True
def calcPrimeN(self):
i = 0
num = 2
while i != self.n:
if self.isPrime(num):
self.array.append(num)
i += 1
num +=1
print(self.array)
return self.array(self.n-1)
t0 = time.clock_gettime_ns(time.CLOCK_MONOTONIC)
prime = Prime(10000)
print(prime.calcPrimeN())
t1 = time.clock_gettime_ns(time.CLOCK_MONOTONIC)
print(t1-t0)実行結果
104729
477429000(ns)Python リスト初期化
最初にテーブルを初期化しておきます。
import math
import time
class Prime:
def __init__(self,n) -> None:
self.n = n
self.array = [0 for i in range(n)]
pass
def isPrime(self,num):
i = 2
while i<=math.sqrt(num):
if num%i == 0:
return False
i += 1
return True
def calcPrimeN(self):
i = 0
num = 2
while i != self.n:
if self.isPrime(num):
self.array[i] = num
i += 1
num +=1
return self.array[self.n-1]
t0 = time.clock_gettime_ns(time.CLOCK_MONOTONIC)
prime = Prime(10000)
print(prime.calcPrimeN())
t1 = time.clock_gettime_ns(time.CLOCK_MONOTONIC)
print(t1-t0)実行結果
104729
428623000(ns)Appendよりも気持ち速い気がします。
Java
Java+通常配列
多分これが一番高速です（であって欲しい。）
class Prime {
int[] prime ;
int n;
public Prime(int n){
prime = new int[n];
this.n = n;
}
public static void main(String[] args){
double t0 = System.nanoTime();
Prime prime = new Prime(10000);
prime.calcPrime();
System.out.println(prime.prime[prime.n-1]);
double t1= System.nanoTime();
System.out.println(t1-t0);
}
public void calcPrime(){
int inserted = 0;
int num = 2;
while (inserted != n){
if (isPrime(num)){
prime[inserted] = num;
inserted +=1;
}
num += 1;
}
}
public static boolean isPrime(int num){
for (int i = 2;i<=Math.sqrt(num);i++){
if (num%i ==0){
return false;
}
}
return true;
}
}Pythonの100倍くらい速いです。
104729
5809208.0(ns)Java + ArrayList
ArrayListクラスを使用します。
import java.util.ArrayList;
class Prime {
ArrayList<Integer> prime = new ArrayList<>();
int n;
public Prime(int n){
this.n = n;
}
public static void main(String[] args){
double t0 = System.nanoTime();
Prime prime = new Prime(10000);
prime.calcPrime();
System.out.println(prime.prime.get(prime.n-1));
double t1= System.nanoTime();
System.out.println(t1-t0);
}
public void calcPrime(){
int inserted = 0;
int num = 2;
while (inserted != n){
if (isPrime(num)){
prime.add(num);
inserted +=1;
}
num += 1;
}
}
public static boolean isPrime(int num){
for (int i = 2;i<=Math.sqrt(num);i++){
if (num%i ==0){
return false;
}
}
return true;
}
}実行結果
104729
7037875.0(ns)
