Linéaire VS Binaire

**khaled_prg** · 17/02/2012, 12h11

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** · 17/02/2012, 12h26

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** · 17/02/2012, 12h29

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** · 17/02/2012, 12h50

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** · 17/02/2012, 14h11

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** · 17/02/2012, 15h15

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** · 17/02/2012, 15h42

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

**khaled_prg** · 17/02/2012, 15h45

- 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.

**khaled_prg** · 17/02/2012, 16h03

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

Quelque soit le type d'algo qui fera le tri, je m’intéresse uniquement au temps d’exécution de la fonction de recherche binaire, donc la rapidité du tri n'a aucune importance pour moi.

**JolyLoic** · 17/02/2012, 17h59

Envoyé par khaled_prg

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

Je ne vois pas en quoi ce serait contradictoire... Déjà, là, tu parles d'un programme de tests séparé, pour lequel rien ne t'empêche d'utiliser des vectors, puisque ce que tu veux tester, c'est la recherche qui ne dépend pas trop de la manière dont la mémoire a été allouée. Ensuite, si tu veux utiliser des matrices, très bien, utilises des matrices (si tu dois faire toi même une classe de gestion des matrices, je te conseille de débuter en utilisant des vectors pour implémenter tes matrices, la preuve que ce n'est pas contradictoire). Mais n'utilise pas un tableau de taille constante (alloué sur la pile) de grande taille.

Envoyé par khaled_prg

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

Et pourquoi ? Ces fonctions marchent très bien sous windows, que l'on soit en console ou pas. Il y a d'autres fonctions qui marchent très bien sous linux. Malheureusement, pas grand-chose qui marche bien partout.

**JolyLoic** · 17/02/2012, 18h03

Envoyé par khaled_prg

Quelque soit le type d'algo qui fera le tri, je m’intéresse uniquement au temps d’exécution de la fonction de recherche binaire, donc la rapidité du tri n'a aucune importance pour moi.

Je suis globalement d'accord, à 3 bémols près :
- à la manière dont tu nous indiquais faire la mesure, le temps du tri n'était pas ignoré
- un algo de tri performant existe en standard, moins de temps passé à coder ce qui ne sert à rien, moins de risque de bug
- ça peut avoir un intérêt de ne pas être trop mauvais pour une simple raison de temps global d'exécution des tests (surtout si tu augmentes la taille de tes données). Il est très désagréable de passer 1h à attendre qu'un programme s'exécute quand il pourrait le faire en 1 minute

**khaled_prg** · 17/02/2012, 19h19

- un algo de tri performant existe en standard, moins de temps passé à coder ce qui ne sert à rien, moins de risque de bug
- ça peut avoir un intérêt de ne pas être trop mauvais pour une simple raison de temps global d'exécution des tests (surtout si tu augmentes la taille de tes données). Il est très désagréable de passer 1h à attendre qu'un programme s'exécute quand il pourrait le faire en 1 minute

Le prof nous a dit d'utiliser des matrices au lieu des vectors qu'on a pas encore étudié.

Ces fonctions marchent très bien sous windows, que l'on soit en console ou pas.

j'ai pas compris l'utilisation de la fonction QueryPerformanceCounter parce que j'ai jamais travaillé sur les fonctions API. je voudrais bien que vous m'expliquier comment on utilise cette fonction ? comment on l'integrer dans le code ?

Merci.

**JolyLoic** · 17/02/2012, 22h06

Code non testé, écrit à la volée :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <windows.h>
 
void mesure()
{
  LARGE_INTEGER t0,t1, freq;
  QueryPerformanceFrequency(&freq);
  QueryPerformanceCounter(&t0);
  f(); // Fonction à mesurer
  QueryPerformanceCounter(&t1);
  cout << "Temps pris pas la fonction " << double(t1.quadpart - t0.quadpart)/frequency.quadpart << "s" << endl;
}

Sinon, si le prof interdit d'utiliser des vecteurs, pour avoir de plus grands tableaux, il te faut passer par de l'allocation dynamique (mais s'il apprend les choses dans cet ordre, il les enseignes à l'envers...).

Code :

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

1
2
3
4
5
int *xInt = new int[50000000];
// calculs
 
// Et à la fin, on nettoie
delete[] xInt;

**khaled_prg** · 18/02/2012, 11h51

Code :

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

1
2
3
4
5
6
7
8
9
10
11
#include <windows.h>
 
void mesure()
{
  LARGE_INTEGER t0,t1, freq;
  QueryPerformanceFrequency(&freq);
  QueryPerformanceCounter(&t0);
  f(); // Fonction à mesurer
  QueryPerformanceCounter(&t1);
  cout << "Temps pris pas la fonction " << double(t1.quadpart - t0.quadpart)/frequency.quadpart << "s" << endl;
}

j'ai testé le code et j'ai obtenu les erreurs suivantes :

In function 'void mesure()':
error: 'LARGE_INTEGER' has no member named 'quadpart'
error: 'LARGE_INTEGER' has no member named 'quadpart'
error: 'frequency' was not declared in this scope
||=== Build finished: 3 errors, 0 warnings ===|

c'est quoi le problème ??

si le prof interdit d'utiliser des vecteurs, pour avoir de plus grands tableaux, il te faut passer par de l'allocation dynamique.

Merci, c'est claire.

Invité · 18/02/2012, 12h37

Pour les LARGE_INTEGER, une petite recherche t'aurait immédiatement donné une solution ( http://msdn.microsoft.com/en-us/libr...=vs.85%29.aspx ). C'est à dire qu'il faut écrite .QuadPart et pas .quadpart. Pour frequency, c'est juste une erreur de nom, il faut mettre freq.

**khaled_prg** · 18/02/2012, 16h40

Pour les LARGE_INTEGER, une petite recherche t'aurait immédiatement donné une solution ( http://msdn.microsoft.com/en-us/libr...=vs.85%29.aspx ). C'est à dire qu'il faut écrite .QuadPart et pas .quadpart. Pour frequency, c'est juste une erreur de nom, il faut mettre freq.

Vous avez raison, je suis désolé.
maintenant ça marche bien.

J'ai appliqué la fonction mesure sur la fonction de recherche linéaire dans une matrice contenant 50.000.000 éléments et j'ai obtenu le résultat suivant :
Temps pris par la fonction 9.6237e-006 s
est-ce que le temps retourné est en secondes ??
si oui ça veux dire que la recherche linéaire n'est plus lente ! sinon c'est quoi l'unité de mesure ?

j'ai trouvé que LARGE_INTEGER est un type defini comme une union et one peut utiliser le membre QuadPart (LONGLONG donc __int64) pour les opération entiere 64 bits.
les deux fonctions QueryPerformanceFrequency et QueryPerformanceCounter prennent en paramètre un pointeur sur une union de LARGE_INTEGER et elles retournent void donc le traitement se fera sur quoi exactement ??

**Flob90** · 18/02/2012, 17h12

Le s me fait dire que c'est en seconde, mais il y a un exposant 10^-6, ca donne donc des micro-seconde.

Personnelement j'appelerais la fonction plusieurs fois pour avoir une mesure correct.

Bien évidement il faut que tu fasses les deux mesures dans les même condition pour chaque méthode.

**JolyLoic** · 18/02/2012, 18h45

Extrait de la doc de QueryPerformanceFrequency :
A pointer to a variable that receives the current performance-counter frequency, in counts per second. If the installed hardware does not support a high-resolution performance counter, this parameter can be zero.

En gros, ces fonctions modifient l'argument qu'on leur passe en paramètre, plutôt que de retourner une valeur, c'est un idiome courant en C, moins en C++ (et j'espère appelé à disparaitre peu à peu avec C++11). C'est pour ça qu'on leur passe un pointeur, de manière à ce que par l'intermédiaire de ce pointeur, la fonction puisse modifier l'objet pointé, et donc la valeur que est déclaré dans ta fonction.

**khaled_prg** · 18/02/2012, 22h04

Ok merci c'est compris.
à présent je veux comprendre cette partie du code :
.

Code :

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

1
2
3
4
5
 
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&t0);
f(); // Fonction à mesurer
QueryPerformanceCounter(&t1);

Je pense que la fonction QueryPerformanceCounter affecte le nombre de micro-seconde au paramètre courant, n'est ce pas ?
et la fonction QueryPerformanceFrequency ??

**Médinoc** · 18/02/2012, 23h31

Ce n'est pas un nombre de microsecondes, c'est un nombre de Nièmes de secondes.

QueryPerformanceFrequency() te donne la valeur de N.

Linéaire VS Binaire

C++

Discussions similaires

Partager

Partager