tag:blogger.com,1999:blog-73637248295593952702024-02-20T11:32:10.731-08:00Génie Logiciel, logiciels libresYann Peniguelhttp://www.blogger.com/profile/02600962963355451800noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-7363724829559395270.post-3258103954331445072011-01-04T16:01:00.000-08:002011-01-04T16:30:14.158-08:00Performances du C et du Java, illustration par l'exempleBonjour à tous.<br />
<br />
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: <a href="http://projecteuler.net/index.php?section=problems&id=29">Problème 29</a><br />
<br />
Je me suis amusé à résoudre ce problème avec le même algorithme, en C et en Java.<br />
En C, j'ai utilisé les listes fournis par le <a href="http://library.gnome.org/devel/glib/stable/">projet glib</a>, et les types et fonctions pour le traitement des grands nombres fournis par le <a href="http://gmplib.org/manual/">projet GNU Multiple Precision Arithmetic Library</a>.<br />
<br />
Vous pouvez le compiler avec la commande suivante, sous Ubuntu:<br />
gcc -std=c99 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -lglib-2.0 -lgmp main.c -o main<br />
___ <br />
<br />
<div style="color: #cfe2f3;">#include <stdio.h></div><div style="color: #cfe2f3;">#include <stdlib.h></div><div style="color: #cfe2f3;">#include <glib.h></div><div style="color: #cfe2f3;">#include <gmp.h></div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">inline static gint compare_mpzt(const gconstpointer a, const gconstpointer b) {</div><div style="color: #cfe2f3;"> if(a == NULL || b == NULL) return -1;</div><div style="color: #cfe2f3;"> else return mpz_cmp(* (mpz_t*) a, * (mpz_t*) b);</div><div style="color: #cfe2f3;">}</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">void clean(gpointer data, gpointer user_data) {</div><div style="color: #cfe2f3;"> free(data);</div><div style="color: #cfe2f3;">}</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">int main() {</div><div style="color: #cfe2f3;"> mpz_t mpz_a;</div><div style="color: #cfe2f3;"> mpz_init_set_ui(mpz_a,2);</div><div style="color: #cfe2f3;"> GSList* list = g_slist_alloc();</div><div style="color: #cfe2f3;"> for(int a=2; a<=100;a++) {</div><div style="color: #cfe2f3;"> for(int b=2; b<=100; b++) {</div><div style="color: #cfe2f3;"> mpz_t* pt_pow = malloc(sizeof(mpz_t));</div><div style="color: #cfe2f3;"> mpz_init(*pt_pow);</div><div style="color: #cfe2f3;"> mpz_set_ui(mpz_a,a);</div><div style="color: #cfe2f3;"> mpz_pow_ui(*pt_pow,mpz_a,b);</div><div style="color: #cfe2f3;"> if(!g_slist_find_custom(list,pt_pow,(GCompareFunc) compare_mpzt)) {</div><div style="color: #cfe2f3;"> list = g_slist_append(list,pt_pow);</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"> printf("%i\n",g_slist_length(list)-1);</div><div style="color: #cfe2f3;"> g_slist_foreach(list,clean,NULL);</div><div style="color: #cfe2f3;"> g_slist_free(list);</div><div style="color: #cfe2f3;"> return 0;</div><div style="color: #cfe2f3;">}</div><br />
___ <br />
<br />
Le temps d'exécution est de 0,59s sur ma machine. <br />
<br />
En Java, j'ai utilisé la classe LinkedList et la classe BigInteger, qui sont fournies de base dans le JDK.<br />
<br />
___<br />
<br />
<div style="color: #cfe2f3;">package euler29;</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">import java.math.BigInteger;</div><div style="color: #cfe2f3;">import java.util.LinkedList;</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">/**</div><div style="color: #cfe2f3;"> *</div><div style="color: #cfe2f3;"> * @author yann</div><div style="color: #cfe2f3;"> */</div><div style="color: #cfe2f3;">public class Main {</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;"> public static void main(String[] args) {</div><div style="color: #cfe2f3;"> long before = System.currentTimeMillis();</div><div style="color: #cfe2f3;"> BigInteger bi1 = new BigInteger("1");</div><div style="color: #cfe2f3;"> BigInteger a = new BigInteger("2");</div><div style="color: #cfe2f3;"> int b = 2;</div><div style="color: #cfe2f3;"> BigInteger bi101 = new BigInteger("101");</div><div style="color: #cfe2f3;"> LinkedList<BigInteger> numbers = new LinkedList<BigInteger>();</div><div style="color: #cfe2f3;"> while(a.compareTo(bi101) == -1) {</div><div style="color: #cfe2f3;"> b = 2;</div><div style="color: #cfe2f3;"> while( b < 101) {</div><div style="color: #cfe2f3;"> BigInteger pow = a.pow(b);</div><div style="color: #cfe2f3;"> if(!numbers.contains(pow)) numbers.add(pow);</div><div style="color: #cfe2f3;"> b += 1;</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"> a = a.add(bi1);</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"> System.out.println(numbers.size());</div><div style="color: #cfe2f3;"> long after = System.currentTimeMillis();</div><div style="color: #cfe2f3;"> System.out.println(after - before + "ms");</div><div style="color: #cfe2f3;"> }</div><div style="color: #cfe2f3;"><br />
</div><div style="color: #cfe2f3;">}</div><br />
___<br />
<br />
Le temps d'exécution est de 4,35s sur ma machine.<br />
<br />
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.<br />
<br />
Que pensez vous de tels écarts de performances?<br />
<br />
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.Yann Peniguelhttp://www.blogger.com/profile/02600962963355451800noreply@blogger.com12