Discussion :

[dasycarpum]

Bonjour et bonne année à tous !

Voilà 3 algo (en C++) de recherche simultanée de min-max : le dernier (3n/2) devrait être plus rapide que les 2 autres (2n), mais en pratique c'est le second qui le devance (très largement) !

Une explication ? cela me permettrait de bien commencer 2012...

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
#define TAILLE 30000000
 
int main()
{
    srand(time(NULL));                  // initialisation de rand
    vector<double>tableau;              // initialisation du tableau
    double temps_initial = clock();
 
    for (int i = 0; i < TAILLE; ++i){
        tableau.push_back(rand()%30000);
    }
 
    double temps_final_tableau = clock ();
    double temps_cpu_tableau = (temps_final_tableau - temps_initial) / CLOCKS_PER_SEC * 1000;
    cout << "Temps construction tableau = " << temps_cpu_tableau << " millisecondes" << endl;
 
    /** Méthode avec position dans le tableau --> la plus lente */
    int MIN = 0, MAX = 0;
    double temps_initial_1 = clock();
 
    for (int i = 0; i < TAILLE; ++i){
        if(tableau[i] > tableau[MAX]) MAX=i;
        if(tableau[i] < tableau[MIN]) MIN=i;
    }
 
    double temps_final_methode1 = clock();
    double temps_cpu_methode1 = (temps_final_methode1 - temps_initial_1) / CLOCKS_PER_SEC * 1000;
    cout << "\nTemps methode 1 = " << temps_cpu_methode1 << " millisecondes" << endl;
 
    cout << "Minimum = " << tableau[MIN] << " a la position " << MIN << endl;
    cout << "Maximum = " << tableau[MAX] << " a la position " << MAX << endl;
 
    /** Méthode classique (on parcourt tous les éléments un par un) mais la plus rapide ... */
    double minimum = tableau[0], maximum = tableau[0];
    double temps_initial_2 = clock();
 
    for (int i = 0; i < TAILLE; ++i){
        if (tableau[i] < minimum)
            minimum = tableau[i];
        if (tableau[i] > maximum)
            maximum = tableau[i];
    }
 
    double temps_final_methode2 = clock ();
    double temps_cpu_methode2 = (temps_final_methode2 - temps_initial_2) / CLOCKS_PER_SEC * 1000;
    cout << "\nTemps methode 2 = " << temps_cpu_methode2 << " milisecondes" << endl;
 
    cout << "Minimum = " << minimum << endl;
    cout << "Maximum = " << maximum << endl;
 
   /** Méthode théoriquement rapide (on travaille par paire d'éléments)  */
    double mini = 0, maxi = 0;
    if (TAILLE%2 !=0){
        mini = tableau[0]; maxi = tableau[0];}
    else if (tableau[0] < tableau[1]){
        mini = tableau[0]; maxi = tableau[1];}
    else {
        mini = tableau[1]; maxi = tableau[0];}
 
    double temps_initial_3 = clock();
 
    for (int i = 0, j = 1; i < TAILLE-1; i+=2, j+=2){
        if (tableau[i] < tableau[j]){
            if (tableau[i] < mini)
                mini= tableau[i];
            if (tableau[j] > maxi)
                maxi = tableau[j];
        }
        else{
            if (tableau[j] < mini)
                mini = tableau[j];
            if (tableau[i] > maxi)
                maxi = tableau[i];
        }
    }
 
    double temps_final_methode3 = clock();
    double temps_cpu_methode3 = (temps_final_methode3 - temps_initial_3) / CLOCKS_PER_SEC * 1000;
    cout << "\nTemps methode 3 = " << temps_cpu_methode3 << " millisecondes" << endl;
 
    cout << "Minimum = " << mini << endl;
    cout << "Maximum = " << maxi << endl;
 
    return 0;
}

[pseudocode]

Toutes ces méthodes ont la même complexité algorithmique (= le même nombre d'opération de base à effectuer). La différence se fait alors par le code machine généré par le compilateur. La méthode générant le moins d'instructions machines sera sans doute la plus rapide.

Ca n'a donc rien d'étonnant que ce soit ta 2nd méthode qui gagne.

for (int i = 0; i < TAILLE; ++i) 1 incrémentation, 1 comparaison, 1 branchement conditionnel
if (tableau[i] < minimum) minimum = tableau[i]; 1 comparaison, 1 branchement conditionnel, 1 affectation (parfois)

[Franck Dernoncourt]

De façon générale :

Voilà 3 algo (en C++) de recherche simultanée de min-max : le dernier (3n/2) devrait être plus rapide que les 2 autres (2n),

O(3n/2) ~ O(2n) ~ O(kn) où k est une constante non dépendante de l'input.

mais en pratique c'est le second qui le devance (très largement) !

Une explication ? cela me permettrait de bien commencer 2012...

Beaucoup de raisons, essentiellement des raisons d'implémentation, peuvent expliquer le fait que la complexité computationnelle théorique diffère de la complexité computationnelle empirique.

Toutes ces méthodes ont la même complexité algorithmique (= le même nombre d'opération de base à effectuer).

Pour être plus précis, O(f(n)) ~ O(k(n)) ssi f(n)/k(n) tend asymptotiquement vers 1 lors n tend vers +infini. Plus d'info : http://en.wikipedia.org/wiki/Big_O_n...ndau_notations

[dasycarpum]

Beaucoup de raisons, essentiellement des raisons d'implémentation, peuvent expliquer le fait que la complexité computationnelle théorique diffère de la complexité computationnelle empirique.

Merci beaucoup à tous les 2 pour ces explications; en conclusion mieux vaut parfois une implémentation courte qu'un algorithme théoriquement rapide... et seuls des tests pourront finalement décider du choix !

Je vais pouvoir mieux dormir cette nuit

[Franck Dernoncourt]

en conclusion mieux vaut parfois une implémentation courte qu'un algorithme théoriquement rapide... et seuls des tests pourront finalement décider du choix !

Cela dépend de tes objectifs (en gros, concepteur d'algorithmes vs. développeur logiciel).
Un thread sur un sujet similaire : http://www.developpez.net/forums/d11...stion-stupide/

[zamato]

Ce que je trouve très amusant, c'est que si tu compiles avec l'option -O2, l'algorithme le moins rapide (la 1ere méthode) devient le plus rapide! Voici ce que j'ai obtenu :

Sans opti.
Temps construction tableau = 2010 millisecondes

Temps methode 1 = 610 millisecondes
Minimum = 0 a la position 93669
Maximum = 29999 a la position 14398

Temps methode 2 = 350 milisecondes
Minimum = 0
Maximum = 29999

Temps methode 3 = 450 millisecondes
Minimum = 0
Maximum = 29999

Avec option -O2
Temps construction tableau = 1490 millisecondes

Temps methode 1 = 150 millisecondes
Minimum = 0 a la position 10223
Maximum = 29999 a la position 79675

Temps methode 2 = 170 milisecondes
Minimum = 0
Maximum = 29999

Temps methode 3 = 180 millisecondes
Minimum = 0
Maximum = 29999

Selon la situation on préferera un algo plutôt qu'à un autre, même si sa complexité est moins bonne.

[Franck Dernoncourt]

Selon la situation on préferera un algo plutôt qu'à un autre, même si sa complexité est moins bonne.

D'autant plus qu'il y a d'autres paramètres à prendre en compte lors d'un choix d'algorithme que les complexités computationnelles théorique et empirique (typiquement, la complexité spatiale ou bien des caractéristiques propres aux tâches).