Exercice n°1
- L'objectif est de comparer les différentes implémentations de liste que vous avez soit créés dans le TP 2, soit celles proposées par l'API Java.
- Pour cela, créez un répertoire dans lequel vous copiez les solutions du TP2, c'est-à-dire les classes Cell.java, CellDouble.java, ListSimple.java et ListDoubleCirc.java.
- Ensuite, copiez/collez le code suivant pour créer le fichier TestPerf.java :
import java.util.*;
class TestPerf {
public static void main(String[] args) {
ListSimple myListSimple = new ListSimple();
ListDoubleCirc myListDouble = new ListDoubleCirc();
List<Integer> arrayList = new ArrayList<Integer>();
List<Integer> linkedList = new LinkedList<Integer>();
if (args.length != 1) {
System.err.println("usage: java TestPerf nb_cell");
System.exit(1);
}
int nbCell = Integer.parseInt(args[0]);
/* liste simplement chaînée */
System.out.print("liste simple : insertion début ... ");
long time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListSimple.insert(i+1,0);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
myListSimple = new ListSimple();
System.out.print("liste simple : insertion milieu ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListSimple.insert(i+1,i/2);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
myListSimple = new ListSimple();
System.out.print("liste simple : insertion fin ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListSimple.append(i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
/* liste doublement chaînée */
System.out.print("liste double : insertion début ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListDouble.prepend(i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
myListDouble = new ListDoubleCirc();
System.out.print("liste double : insertion milieu ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListDouble.insert(i+1,i/2);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
myListDouble = new ListDoubleCirc();
System.out.print("liste double : insertion fin ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
myListDouble.append(i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
/* LinkedList de l'API Java */
System.out.print("linked list de l'API java : insertion début ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
linkedList.add(0,i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
linkedList = new LinkedList<Integer>();
System.out.print("linked list de l'API java : insertion milieu ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
linkedList.add(i/2,i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
linkedList = new LinkedList<Integer>();
System.out.print("linked list de l'API java : insertion fin ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
linkedList.add(linkedList.size(),i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
/* ArrayList de l'API Java */
System.out.print("array list de l'API java : insertion début ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
arrayList.add(0,i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
arrayList = new ArrayList<Integer>();
System.out.print("array list de l'API java : insertion milieu ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
arrayList.add(i/2,i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
arrayList = new ArrayList<Integer>();
System.out.print("array list de l'API java : insertion fin ... ");
time = Calendar.getInstance().getTimeInMillis();
for(int i=0;i<nbCell;i++) {
arrayList.add(i+1);
}
time = Calendar.getInstance().getTimeInMillis() - time;
System.out.println((time/1000.0)+"s");
}
}
- Commencez par exécuter le programme principal avec comme argument 1000 pour voir si tout fonctionne. Vous devriez constater des temps ridicules dans tous les cas.
- Essayez ensuite avec 10000 insertions, puis 50000. Vous pouvez aller plus loin mais vous risquez d'attendre longtemps !
- Vous devriez constater que les versions "faite maison" ne sont pas si mauvaise que ça. En revanche ArrayList les bat à plat de couture. Si vous lisez la documentation de la classe, vous devriez aisément comprendre pourquoi.
Exercice n°2
- L'objectif est maintenant de comparer les résultats précédents avec une version C.
- Pour cela, copiez les fichiers listdouble.h et listdouble.c des solutions du TP n°2 dans le répertoire.
- Créez le fichier testperf.c avec le code suivant :
#include <stdio.h>
#include <stdlib.h>
#include "listdouble.h"
#include <sys/time.h>
#include <time.h>
#include <math.h>
#include <string.h>
#define CLOCK_S 0
#define CLOCK_MS 1
#define CLOCK_US 2
double dclock(int mode) {
double time;
struct timeval t;
gettimeofday(&t,NULL);
if (mode == CLOCK_US) {
time = 1.0e6 * (double)t.tv_sec + (double)t.tv_usec;
}
else if (mode == CLOCK_MS) {
time = 1.0e3 * (double)t.tv_sec + 1.0e-3 * (double)t.tv_usec;
}
else if (mode == CLOCK_S) {
time = (double)t.tv_sec + 1.0e-6 * (double)t.tv_usec;
}
return(time);
}
int main(int argc, char** argv) {
if( argc != 2) {
fprintf(stderr,"usage : testperf nb_cell\n");
exit(1);
}
int nbCell = atoi(argv[1]);
List* l1;
List* l2;
List* l3;
int i;
l1 = listCreate();
l2 = listCreate();
l3 = listCreate();
printf("liste doublement chaînée circulaire, insertion début ...");
double t = dclock(CLOCK_S);
for(i=0;i<nbCell;i++) {
listPrepend(l1,i+1);
}
t = dclock(CLOCK_S) - t;
printf("%fs\n",t);
printf("liste doublement chaînée circulaire, insertion milieu ...");
t = dclock(CLOCK_S);
for(i=0;i<nbCell;i++) {
listInsert(l2,i+1,i/2);
}
t = dclock(CLOCK_S) - t;
printf("%fs\n",t);
printf("liste doublement chaînée circulaire, insertion fin ...");
t = dclock(CLOCK_S);
for(i=0;i<nbCell;i++) {
listAppend(l3,i+1);
}
t = dclock(CLOCK_S) - t;
printf("%fs\n",t);
return 0;
}
- Création de l'exécutable : gcc testperf.c listdouble.c -o testperf
- Exécutez le programme avec les mêmes paramètres que pour l'exercice n°1. Vous devriez avoir une surprise en comparant les temps Java et C.