Nach dem Üben von Python habe ich ein Programm erstellt, das die Primfaktorisierung mit einfacher Logik berechnet. Übrigens habe ich es in C-Sprache und Java erstellt und versucht, um die Verarbeitungsgeschwindigkeit zu konkurrieren, also werde ich es hochladen.
Das Programm wird lang sein, also aus den Ergebnissen.
#C Sprache
$ ./a.exe 123456789
123456789 = 3 * 3 * 3607 * 3803
Die benötigte Zeit beträgt 2.884932 Sekunden.
# Java
>java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
Die Fahrzeit beträgt 1245 Millisekunden.
# Python3
>python factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
Die benötigte Zeit beträgt 60.498295 Sekunden
Java ist die Spitze. Der Grund, warum Python langsam ist, ist, dass das Programm, das ich gemacht habe und das Python selten verwendet hat, trash ^^ ist;
Ich frage mich jedoch, ob Java schneller als C ist. Ich habe mich gefragt, also habe ich beschlossen, die Umgebung zu ändern. Ich habe Cygwin als Ausführungsumgebung für C verwendet, aber der Fairness halber werde ich versuchen, alles unter Linux auszuführen. Ich habe EC2 von AWS verwendet. Ich habe versucht, t2.xlarge ein wenig zu verwenden, um ein Benchmarking mit dem Amazon Linux2-Image durchzuführen. (Es kostet Geld, also lösche es, sobald es fertig ist ;;)
Das Ergebnis ist wie folgt.
[ec2-user ~]$ #C Sprache
[ec2-user ~]$ ./a.out 123456789
123456789 = 3 * 3 * 3607 * 3803
Die benötigte Zeit beträgt 2.730501 Sekunden.
[ec2-user ~]$ #Java
[ec2-user ~]$ java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
Die Fahrzeit beträgt 828 Millisekunden.
[ec2-user ~]$ #Python
[ec2-user ~]$ python3 factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
Die benötigte Zeit beträgt 33.936324 Sekunden
Immerhin ist Java die Spitze. Python ist im Vergleich zu Windows wahrscheinlich das schnellste. Persönlich dachte ich, dass die C-Sprache die schnellste ist, daher ist es ein wenig überraschendes Ergebnis, aber ich denke, Javas ArrayQueue-Klasse ist besser, als selbst eine Warteschlange zu erstellen. .. ..
Die verwendeten Quellen sind unten aufgeführt.
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef unsigned long ulong_t;
//Warteschlange zum Sammeln von Primfaktoren
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();
//Primfaktorisierung durchführen
que_t* q = factrization(num);
long after = getusec();
//Ergebnisse anzeigen
printf("%d = %d", num, q->prime);
while(q->next != NULL){
q = q->next;
printf(" * %d", q->prime);
}
//Verstrichene Zeit anzeigen
long spend = (after - before);
long sec = spend / 1000000;
long usec = spend % 1000000;
printf("\n Zeitaufwand%d.%d Sekunden.\n", sec, usec);
}
//Zerlegen Sie die übergebene natürliche Zahl n in das Produkt einer Primzahl und einer natürlichen Zahl
que_t* factrization(ulong_t n){
//Matrix zur Berechnung von Primzahlen
// (Da 0 gefüllt ist, wenn der Speicher gesichert ist, ist das Element, das 0 enthält, ein Hauptkandidat.)
ulong_t* p = calloc((n+1), sizeof(ulong_t));
//Bestimmen von Primzahlen zum ersten Mal aus 2
for(int a = 2; a < (n/2); a++){
//Überspringen Sie Nummern, die bereits als nicht primär bestätigt wurden
if(p[a] != 0){
continue;
}
//Entfernen Sie Vielfache von Primzahlen von Kandidaten
int b = 2;
int m = a * b;
while(m < n){
p[m] = -1; //Nicht Null ⇒ keine Primzahl
b++;
m = a * b;
}
//Wenn n ein Vielfaches ist(Wenn es sich um eine nicht primäre Nummer handelt)
if(n == m){
// n = a * b(a ist eine Primzahl)
// printf("%d = %d * %d\n", n, a, b);
//Wiederholen Sie rekursiv für b
que_t* f = factrization(b);
//Stellen Sie ein in die Warteschlange
que_t* qa = malloc(sizeof(que_t));
qa->prime = a;
//Fügen Sie am Anfang der Warteschlange ein hinzu
qa->next = f;
//Warteschlange zurückgeben
return qa;
}
}
//Wenn Sie bis zum Ende sagen, ist n eine Primzahl
//Generieren Sie eine Warteschlange und geben Sie sie zurück
que_t* qp = malloc(sizeof(que_t));
qp->prime = n;
qp->next = NULL;
free(p);
return qp;
}
//Aktuelle Uhrzeit(Holen Sie sich μ Sekunden)
long getusec(){
struct timeval _time;
gettimeofday(&_time, NULL);
long sec = _time.tv_sec;
sec *= 1000000;
long usec = _time.tv_usec;
return sec + usec;
}
package example;
import java.util.ArrayDeque;
import java.util.Calendar;
import java.util.Iterator;
import java.util.Queue;
import java.util.Scanner;
/**
*Fordern Sie die Primfaktorisierung heraus
*/
public class Factrization {
public static void main(String[] args) {
int num;
num = Integer.parseInt(args[0]);
//Warteschlange zum Registrieren zerlegter Primfaktoren
Queue<Integer> queue = new ArrayDeque<>();
Calendar before = Calendar.getInstance();
//Primfaktorisierung durchführen
queue = fact(num, queue);
Calendar after = Calendar.getInstance();
//Ergebnisse anzeigen
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("Die benötigte Zeit ist%Es ist d Millisekunde.\n",
(after.getTimeInMillis() - before.getTimeInMillis()));
}
/**
*Zerlegen Sie die übergebene natürliche Zahl in das Produkt aus der Primzahl und der natürlichen Zahl
*/
static Queue<Integer> fact(int n, Queue<Integer> q) {
//Definieren Sie ein Array, das für eine Primzahl in Frage kommt.
//In Java wird es zum Zeitpunkt der Generierung mit 0 aufgefüllt, sodass Elemente mit 0 Kandidaten für Primzahlen sind.
int[] p = new int[n + 1];
for (int a = 2; a < (n / 2); a++) {
//Überspringen, wenn als nicht primär bestätigt
if (p[a] != 0) {
continue;
}
int b = 2;
int m = a * b;
while (m < n) {
p[m] = -1; //Nicht Null ⇒ Nicht primäres Element
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;
}
}
import sys
import time
#Primfaktorisierung
def factrization(n):
#Definieren Sie eine Ganzzahl bis zu einer bestimmten Zahl
p = list(range(n+1))
#Entfernen Sie ab 2 Vielfache
#OK, wenn Sie bis zur Hälfte des Maximalwerts ausführen
for a in range(2,int(n/2)):
#Wenn entschieden wird, dass a keine Primzahl ist, fahren Sie mit der nächsten fort
if p[a] == 0 :
continue
#Zahl, die mit der Primzahl multipliziert werden soll
b = 2
m = a * b
#Vielfaches von a(Das heißt, eine Zahl, die keine Primzahl ist)Auf 0
while m < n:
p[m] = 0
b += 1
m = a * b
#Wenn n ein Vielfaches von a ist
if m == n:
# n=a*b bestätigt
# print('%d = %d * %d' % (n, a, b))
#Weitere Subfaktorisierung b
fact = factrization(b)
#Da das bestätigte a eine Primzahl ist, wird es ausgegeben.
return [a] + fact
#Wenn n nicht 0 wird, ist n eine Primzahl
return [n]
#Übergeben Sie eine natürliche Zahl als Befehlszeilenargument
num = eval(sys.argv[1])
before = time.time()
#Primfaktorisierung durchführen
f = factrization(num)
after = time.time()
#Zeigen Sie das Ausführungsergebnis an
print('%d = %d' % (num, f[0]), end='')
for p in f[1:]:
print(' * %d' % p, end='')
print('\n Zeitaufwand%f Sekunden' % (after - before))
Recommended Posts