Discussion :

[khaled_prg]

Bonjours à tous
J'ai appris en théorie que la complexité d'un algo recherche linéaire égal à n alors que celle d'un algo recherche binaire et log(n) et j'ai voulu mettre en pratique c'est pourquoi j'ai les programmé en C++, ou j'ai déclaré une matrice contenant 500.000 éléments et je l'ai rempli d'une façon aléatoire puis je l'ai trié enfin j'ai effectué une recherche dans cette matrice avec les deux algo d'un nombre qui n'existe pas dans la matrice, les résultats avec la durée m'ont été retrouvés par code::blocks, étaient inattendu car le temps d’exécution d'algo recherche binaire était 0.257 s et celui linéaire était 0.319 s !!
c'est pas la différence que j'attendais !


Merci.

[koala01]

Salut,

il faut déjà voir si tes différents algorithmes on correctement été implémentés, car il est possible de "plomber" les performances avec de mauvaises implémentations

Ensuite, il faut être attentif à ne prendre en compte que la partie qui traite de l'algorithme, en excluant tout ce qui peut "ralentir" ton test (allocation dynamique de la mémoire de ta matrice ainsi que son remplissage et son tri, affichage).

Tu ne peux donc pas "simplement" te baser sur le temps d'exécution indiqué par CodeBlocks quand il termine l'exécution d'un programme qu'il vient de compiler, car il y a, en plus de tout ce que j'ai cité plus haut, le temps de la création de la console, le temps nécessaire au fait qu'il obtienne l'information de fermeture de celle-ci, etc...

En outre, il est important de veiller à exécuter ton test en release et non en debug, car, selon le compilateur, il n'est pas impossible du tout que la version debug fasse une série de vérifications (certes utiles pour le debugging ) dont le temps est, sommes toutes, aléatoire

Enfin, il faut compter avec la charge globale du système, sur laquelle tu n'as, généralement, qu'un pouvoir très limité.

L'idéal est donc de faire en sorte d'effectuer plusieurs mesures et de prendre la moyenne de celles-ci.

Juste par curiosité, pourrais tu faire un copier / coller de ton code, afin que nous puissions nous faire une idée

Il est, en effet, particulièrement difficile de donner des explications claires si l'on ne dispose pas d'un minimum d'information

[Ekleog]

Il n'est pas étonnant d'avoir une aussi faible différence, étant donné le faible nombre d'éléments du tableau. (500.000, c'est quand même assez peu.)

Au passage, ajouter un troisième test avec std::binary_search permettrait de voir ce que ça donne par rapport à une "vraie" implémentation.

Sinon, quelle est la question ?

[Médinoc]

Le temps d'exécution donné par Code::Blocks inclut le temps d'initialisation et le temps de tri en O(n log(n)) minimum. Donc je soutiens koala01.

[khaled_prg]

Merci à tous.

Il n'est pas étonnant d'avoir une aussi faible différence, étant donné le faible nombre d'éléments du tableau. (500.000, c'est quand même assez peu.)

si je dépasse 500.000 éléments le programme plante, l'exécution s'annonce impossible :
http://sub3.rofof.com/img4/02dqnvj17.png
il semble que le problème vient de la mémoire !, comment augmenter cette dernière ?


Puisque le code::blocks donne le temps d'exécution d'un code où est y inclut

le temps de la création de la console, le temps nécessaire au fait qu'il obtienne l'information de fermeture de celle-ci, etc...

alors je dois calculer la durée juste avant l'appel de la fonction et juste après et je calcule la différence entre les deux durées.
je peux faire ceci avec la fonction _strtime mais le problème c'est qu'elle ne calcule pas la durée en millisecondes !, comment puis-je calculer le temps d’exécution en millisecondes ??

Voici mes codes :
Recherche linéaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int linearSearch(int X[], int length, int Key){
    for(int i = 0;i < length; i++)
        if(X[i] == Key)
           return i;
    return -1;
}
int main(){
    int xInt[500000];
    int key = -5;
    srand(time(NULL));
    for(int i = 0;i < 500000;i++){
        xInt[i] = rand()%10000;
    }
    int found =  linearSearch(xInt,500000,key);
    if( found == -1)
       cout<<"La valeur n'est pas trouvée !";
    else
       cout<<"La clé se trouve dans la case numéro "<<found + 1;
    return 0;
}

Recherche binaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
void bubblesort(int ptableau[], int n)
{
	int i, j, temp;
 
	for (i = 0; i < (n - 1); ++i) {
		for (j = i + 1; j < n; ++j) {
			if (ptableau[j] < ptableau[i]) {
				temp = ptableau[i];
				ptableau[i] = ptableau[j];
				ptableau[j] = temp;
			}
		}
	}
}
int binarySearch(int X[],int key,int sup,int inf){
    int m;
    while(sup >= inf){
        m=(sup + inf)/2;
        if(key < X[m])
            sup = m - 1;
        else
           if(key > X[m])
              inf = m + 1;
           else
              return m;
    }
    return -1;
}
int main(){
    int const SIZE = 50000;
    int xInt[SIZE];
    int key = -5;
    srand(time(NULL));
    for(int i = 0;i < SIZE;i++){
        xInt[i] = rand()%1000;
    }
    bubblesort(xInt, SIZE);
    int found =  binarySearch(xInt,key,SIZE,0);
    if( found == -1)
       cout<<"La valeur n'est pas trouvée !";
    else
       cout<<"La clé se trouve dans la case numéro "<<found + 1;
    return 0;
}

[JolyLoic]

Plusieurs problèmes en vrac :

- Utilises un vector au lieu d'un tableau, comme ça tes données seront dans le tas, et non sur la pile, et tu auras moins de limites de taille
- Quand tu mesures, ne mesure que la recherche, pas l'ensemble. Par exemple, sous windows, tu peux utiliser QueryPerformanceCounter et QueryPerformanceFrequency
- Bubble sort : Berk. Utilises std::sort

[Médinoc]

Attends, tu comptais un bubblesort dans le temps et tu t'étonnais de faibles performances?

[khaled_prg]

- Utilises un vector au lieu d'un tableau, comme ça tes données seront dans le tas, et non sur la pile, et tu auras moins de limites de taille.
- Bubble sort : Berk. Utilises std::sort

Le projet que j'aborde étudie des recherches sur des matrices (tableaux) donc je ne peux pas utiliser vector.

- Quand tu mesures, ne mesure que la recherche, pas l'ensemble. Par exemple, sous windows, tu peux utiliser QueryPerformanceCounter et QueryPerformanceFrequency

je travaille sur la console donc je ne peux pas utiliser les fonctions API.

Merci.