Pour ce premier article d'une liste que j'espère grandissante, je vous ferais part d'un constat tout frais, que j'ai fait en résolvant l'un des problèmes du site projecteuler.net: Problème 29
Je me suis amusé à résoudre ce problème avec le même algorithme, en C et en Java.
En C, j'ai utilisé les listes fournis par le projet glib, et les types et fonctions pour le traitement des grands nombres fournis par le projet GNU Multiple Precision Arithmetic Library.
Vous pouvez le compiler avec la commande suivante, sous Ubuntu:
gcc -std=c99 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -lglib-2.0 -lgmp main.c -o main
___
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
#include <gmp.h>
inline static gint compare_mpzt(const gconstpointer a, const gconstpointer b) {
if(a == NULL || b == NULL) return -1;
else return mpz_cmp(* (mpz_t*) a, * (mpz_t*) b);
}
void clean(gpointer data, gpointer user_data) {
free(data);
}
int main() {
mpz_t mpz_a;
mpz_init_set_ui(mpz_a,2);
GSList* list = g_slist_alloc();
for(int a=2; a<=100;a++) {
for(int b=2; b<=100; b++) {
mpz_t* pt_pow = malloc(sizeof(mpz_t));
mpz_init(*pt_pow);
mpz_set_ui(mpz_a,a);
mpz_pow_ui(*pt_pow,mpz_a,b);
if(!g_slist_find_custom(list,pt_pow,(GCompareFunc) compare_mpzt)) {
list = g_slist_append(list,pt_pow);
}
}
}
printf("%i\n",g_slist_length(list)-1);
g_slist_foreach(list,clean,NULL);
g_slist_free(list);
return 0;
}
___
Le temps d'exécution est de 0,59s sur ma machine.
En Java, j'ai utilisé la classe LinkedList et la classe BigInteger, qui sont fournies de base dans le JDK.
___
package euler29;
import java.math.BigInteger;
import java.util.LinkedList;
/**
*
* @author yann
*/
public class Main {
public static void main(String[] args) {
long before = System.currentTimeMillis();
BigInteger bi1 = new BigInteger("1");
BigInteger a = new BigInteger("2");
int b = 2;
BigInteger bi101 = new BigInteger("101");
LinkedList<BigInteger> numbers = new LinkedList<BigInteger>();
while(a.compareTo(bi101) == -1) {
b = 2;
while( b < 101) {
BigInteger pow = a.pow(b);
if(!numbers.contains(pow)) numbers.add(pow);
b += 1;
}
a = a.add(bi1);
}
System.out.println(numbers.size());
long after = System.currentTimeMillis();
System.out.println(after - before + "ms");
}
}
___
Le temps d'exécution est de 4,35s sur ma machine.
Le temps de développement, que j'aurais dû prendre la précaution de mesurer précisément aussi, était grosso modo 3 à 4 fois plus grand avec la version en C.
Que pensez vous de tels écarts de performances?
Loin de vouloir relancer le célèbre troll C VS Java, j'aimerais plutôt montrer le prix de la facilité offerte par le couple NetBeans/Java, et peut être avoir un retour sur les questions d'optimisation.
