Après avoir pratiqué Python, j'ai créé un programme qui calcule la factorisation prime avec une logique simple. En passant, je l'ai créé en langage C et Java et j'ai essayé de rivaliser pour la vitesse de traitement, donc je vais le télécharger.
Le programme sera long, donc d'après les résultats.
#Langage C
$ ./a.exe 123456789
123456789 = 3 * 3 * 3607 * 3803
Le temps requis est de 2.884932 secondes.
# Java
>java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
Le temps de trajet est de 1245 millisecondes.
# Python3
>python factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
Le temps requis est de 60.498295 secondes
Java est le top. La raison pour laquelle Python est lent est que le programme que j'ai créé et qui a rarement utilisé Python est trash ^^;
Cependant, je me demande si Java est plus rapide que C. Je me posais la question, j'ai donc décidé de changer d'environnement. J'ai utilisé Cygwin comme environnement d'exécution pour C, mais par souci d'équité! Je vais essayer de tout exécuter sous Linux. J'ai utilisé EC2 d'AWS. J'ai essayé d'utiliser t2.xlarge un peu richement à des fins d'analyse comparative avec l'image Amazon Linux2. (Cela coûte de l'argent, alors supprimez-le dès que c'est fait ;;)
Le résultat est le suivant.
[ec2-user ~]$ #Langage C
[ec2-user ~]$ ./a.out 123456789
123456789 = 3 * 3 * 3607 * 3803
Le temps requis est de 2.730501 secondes.
[ec2-user ~]$ #Java
[ec2-user ~]$ java -jar Factorization.jar 123456789
123456789 = 3803 * 3607 * 3 * 3
Le temps de trajet est de 828 millisecondes.
[ec2-user ~]$ #Python
[ec2-user ~]$ python3 factorization.py 123456789
123456789 = 3 * 3 * 3607 * 3803
Le temps requis est de 33.936324 secondes
Après tout, Java est le top. Python est probablement le plus rapide par rapport à Windows. Personnellement, je pensais que le langage C était le plus rapide, donc c'est un résultat un peu surprenant, mais je pense que la classe ArrayQueue de Java est meilleure que de créer une file d'attente par vous-même. .. ..
Voici la source que j'ai utilisée.
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
typedef unsigned long ulong_t;
//File d'attente pour collecter les facteurs premiers
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();
//Effectuer la factorisation prime
que_t* q = factrization(num);
long after = getusec();
//Voir les résultats
printf("%d = %d", num, q->prime);
while(q->next != NULL){
q = q->next;
printf(" * %d", q->prime);
}
//Afficher le temps écoulé
long spend = (after - before);
long sec = spend / 1000000;
long usec = spend % 1000000;
printf("\n Temps requis%d.%d secondes.\n", sec, usec);
}
//Décomposer le nombre naturel passé n en le produit d'un nombre premier et d'un entier naturel
que_t* factrization(ulong_t n){
//Matrice de calcul des nombres premiers
// (Puisque 0 est rempli lorsque la mémoire est sécurisée, l'élément contenant 0 est un candidat premier.)
ulong_t* p = calloc((n+1), sizeof(ulong_t));
//Déterminer les nombres premiers pour la première fois à partir de 2
for(int a = 2; a < (n/2); a++){
//Ignorer les numéros qui ont déjà été confirmés comme non principaux
if(p[a] != 0){
continue;
}
//Supprimer les multiples de nombres premiers des candidats
int b = 2;
int m = a * b;
while(m < n){
p[m] = -1; //Non nul ⇒ pas un nombre premier
b++;
m = a * b;
}
//Quand n est un multiple(Quand il s'agit d'un numéro non principal)
if(n == m){
// n = a * b(a est un nombre premier)
// printf("%d = %d * %d\n", n, a, b);
//Répétez récursivement pour b
que_t* f = factrization(b);
//Mettre un dans la file d'attente
que_t* qa = malloc(sizeof(que_t));
qa->prime = a;
//Ajouter un au début de la file d'attente
qa->next = f;
//File d'attente de retour
return qa;
}
}
//Si vous dites jusqu'à la fin, n est un nombre premier
//Générer et renvoyer une file d'attente
que_t* qp = malloc(sizeof(que_t));
qp->prime = n;
qp->next = NULL;
free(p);
return qp;
}
//Heure actuelle(Obtenez μ secondes)
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;
/**
*Défier la factorisation prime
*/
public class Factrization {
public static void main(String[] args) {
int num;
num = Integer.parseInt(args[0]);
//File d'attente pour enregistrer les facteurs premiers décomposés
Queue<Integer> queue = new ArrayDeque<>();
Calendar before = Calendar.getInstance();
//Effectuer la factorisation prime
queue = fact(num, queue);
Calendar after = Calendar.getInstance();
//Voir les résultats
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("Le temps requis est%C'est d milliseconde.\n",
(after.getTimeInMillis() - before.getTimeInMillis()));
}
/**
*Décomposer le nombre naturel passé en produit du nombre premier et du nombre naturel
*/
static Queue<Integer> fact(int n, Queue<Integer> q) {
//Définissez un tableau qui est candidat pour un nombre premier.
//En Java, il est complété par 0 au moment de la génération, donc les éléments contenant 0 sont candidats pour les nombres premiers.
int[] p = new int[n + 1];
for (int a = 2; a < (n / 2); a++) {
//Ignorer si confirmé comme non principal
if (p[a] != 0) {
continue;
}
int b = 2;
int m = a * b;
while (m < n) {
p[m] = -1; //Non nul ⇒ élément non primaire
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
#Factorisation prime
def factrization(n):
#Définir un entier jusqu'à un nombre donné
p = list(range(n+1))
#À partir de 2, supprimez les multiples
#OK si vous faites jusqu'à la moitié de la valeur maximale
for a in range(2,int(n/2)):
#S'il est décidé que a n'est pas un nombre premier, passez au suivant
if p[a] == 0 :
continue
#Nombre à multiplier par nombre premier
b = 2
m = a * b
#Multiple d'un(Autrement dit, un nombre qui n'est pas un nombre premier)À 0
while m < n:
p[m] = 0
b += 1
m = a * b
#Si n est un multiple de a
if m == n:
# n=a*b confirmé
# print('%d = %d * %d' % (n, a, b))
#Sous-factoriser davantage b
fact = factrization(b)
#Puisque le a confirmé est un nombre premier, il est émis.
return [a] + fact
#Si n ne devient pas 0, n est un nombre premier
return [n]
#Passez un nombre naturel comme argument de ligne de commande
num = eval(sys.argv[1])
before = time.time()
#Effectuer la factorisation prime
f = factrization(num)
after = time.time()
#Afficher le résultat de l'exécution
print('%d = %d' % (num, f[0]), end='')
for p in f[1:]:
print(' * %d' % p, end='')
print('\n Temps requis%f secondes' % (after - before))
Recommended Posts