Pythonの練習がてら、素因数分解を簡単なロジックで計算させるプログラムを作成してみました。ついでにC言語、Javaでも作成して処理速度を競わせてみたのでアップします。
プログラムは長くなるので結果から。
# C言語
$ ./a.exe 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は2.884932秒です。
# Java
>java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
所要時間は1245ミリ秒です。
# Python3
>python factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は60.498295秒です
なんとJavaがトップ。
Pythonが遅いのは、Pythonをほとんど使ったことがない私が作ったプログラムがゴミなのでしょう^^;
しかし、CよりJavaが早いかなぁ。というのが疑問だったので、環境を変えてみることに。Cの実行環境はCygwinを使用していたのですが、公平を期すために!? Linuxですべて動かしてみます。
使用したのはAWSのEC2です。Amazon Linux2 イメージで、ベンチマーク目的なのでちょっとリッチにt2.xlargeを使ってみました。(お金がかかるので終わったらすぐ削除;;)
結果は以下の通り。
[ec2-user ~]$ #C言語
[ec2-user ~]$ ./a.out 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は2.730501秒です。
[ec2-user ~]$ #Java
[ec2-user ~]$ java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
所要時間は828ミリ秒です。
[ec2-user ~]$ #Python
[ec2-user ~]$ python3 factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
所要時間は33.936324秒です
やはりJavaがトップです。Windowsに比べて一番早くなったのはPythonかな。
個人的にはC言語が一番速いかと思っていたのでちょっと意外な結果ですが、自分でキューを作成するより、JavaのArrayQueueクラスのほうが優秀ということなんでしょうね。。。
以下に、使用したソースを掲載しておきます。
- C言語
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef unsigned long ulong_t;
// 素因数を収集するキュー
typedef struct _que {
ulong_t prime;
struct _que* next;
} que_t;
que_t* factrization(ulong_t);
long getusec();
void main(int argc, char** argv){
ulong_t num;
char* e;
num = strtoul(argv[1], &e, 10);
long before = getusec();
// 素因数分解を実行
que_t* q = factrization(num);
long after = getusec();
// 結果を表示する
printf("%d = %d", num, q->prime);
while(q->next != NULL){
q = q->next;
printf(" * %d", q->prime);
}
// 経過時間を表示する
long spend = (after - before);
long sec = spend / 1000000;
long usec = spend % 1000000;
printf("\n所要時間は%d.%d秒です。\n", sec, usec);
}
// 渡された自然数nを素数と自然数の積に分解する
que_t* factrization(ulong_t n){
// 素数を計算するための行列
// (メモリ確保時に0埋めするため、0が入っている要素が素数候補)
ulong_t* p = calloc((n+1), sizeof(ulong_t));
// 2から初めて、素数を割り出す
for(int a = 2; a < (n/2); a++){
// すでに非素数と確定している数は飛ばす
if(p[a] != 0){
continue;
}
// 素数の倍数を候補から外していく
int b = 2;
int m = a * b;
while(m < n){
p[m] = -1; // 非0⇒素数ではない
b++;
m = a * b;
}
// nが倍数であるとき(非素数であるとき)
if(n == m){
// n = a * b(aは素数)
// printf("%d = %d * %d\n", n, a, b);
// bについて再帰的に繰り返す
que_t* f = factrization(b);
// キューにaを入れる
que_t* qa = malloc(sizeof(que_t));
qa->prime = a;
// キューの先頭にaを追加する
qa->next = f;
// キューを返す
return qa;
}
}
// 最後まで言った場合nは素数
// キューを生成して返す
que_t* qp = malloc(sizeof(que_t));
qp->prime = n;
qp->next = NULL;
free(p);
return qp;
}
// 現在時刻(μ秒の取得)
long getusec(){
struct timeval _time;
gettimeofday(&_time, NULL);
long sec = _time.tv_sec;
sec *= 1000000;
long usec = _time.tv_usec;
return sec + usec;
}
- Java
package example;
import java.util.ArrayDeque;
import java.util.Calendar;
import java.util.Iterator;
import java.util.Queue;
import java.util.Scanner;
/**
* 素因数分解に挑戦する
*/
public class Factrization {
public static void main(String[] args) {
int num;
num = Integer.parseInt(args[0]);
// 分解した素因数を登録するキュー
Queue<Integer> queue = new ArrayDeque<>();
Calendar before = Calendar.getInstance();
// 素因数分解を実行する
queue = fact(num, queue);
Calendar after = Calendar.getInstance();
// 結果を表示する
Iterator<Integer> i = queue.iterator();
System.out.printf("%d = %d", num, i.next());
while (i.hasNext()) {
System.out.printf(" * %d", i.next());
}
System.out.println();
System.out.printf("所要時間は%dミリ秒です。\n",
(after.getTimeInMillis() - before.getTimeInMillis()));
}
/**
* 渡された自然数を素数と自然数の積に分解する
*/
static Queue<Integer> fact(int n, Queue<Integer> q) {
// 素数の候補となる配列を定義。
// Javaでは生成時に0埋めされるので、0が入っている要素を素数の候補とする
int[] p = new int[n + 1];
for (int a = 2; a < (n / 2); a++) {
// 非素数と確定している場合は飛ばす
if (p[a] != 0) {
continue;
}
int b = 2;
int m = a * b;
while (m < n) {
p[m] = -1; // 非0⇒素数でない要素
b++;
m = a * b;
}
if (n == m) {
// System.out.printf("%d = %d * %d\n", n, a, b);
Queue<Integer> f = fact(b, q);
f.add(a);
return f;
}
}
q.add(n);
return q;
}
}
- Python
import sys
import time
# 素因数分解
def factrization(n):
# 与えられた数値までの整数を定義する
p = list(range(n+1))
# 2から初めて、倍数を削除する
# 最大値の半分までやればOK
for a in range(2,int(n/2)):
# aが素数ではないことが決まっていたら次へ
if p[a] == 0 :
continue
# 素数にかける数
b = 2
m = a * b
# aの倍数(つまり素数ではない数)を0とする
while m < n:
p[m] = 0
b += 1
m = a * b
# nがaの倍数であれば
if m == n:
# n=a*bが確定
# print('%d = %d * %d' % (n, a, b))
# bをさらに素因数分解する
fact = factrization(b)
# 確定したaは素数なので出力する
return [a] + fact
#nが0にならなかったらnが素数
return [n]
# コマンドライン引数で自然数を渡す
num = eval(sys.argv[1])
before = time.time()
# 素因数分解を実行する
f = factrization(num)
after = time.time()
# 実行結果を表示する
print('%d = %d' % (num, f[0]), end='')
for p in f[1:]:
print(' * %d' % p, end='')
print('\n所要時間は%f秒です' % (after - before))