tester (et améliorer ?) algo

Version imprimable

bonjour,

J'ai fait une petite fonction qui recherche une valeur dans un tableau trié : si la valeur est présente plusieurs fois dans le tableau, cette fonction doit retourner le premier élément du tableau.

Code:

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
static int find_firstElement(int val, int tab[], int len){
 
    int sup, inf, demi;
 
    //On définit les bornes de la partie du tableau à considérer
    inf = 0;
    sup = len - 1;
    if(sup < 1){
        return -1;
    }
 
    int i;
    printf("Tab[] =");
    for(i=0; i<len; i++){
        printf(" %i", tab[i]);
    }
    printf("\n");
 
 
    // ****************************
    while(1){
        demi = (sup + inf)/2;
 
        if(tab[demi] > val){
            sup = demi - 1;
            if(tab[sup] < val){
                return -1;
            }
 
        } else if(tab[demi] < val){
            inf = demi + 1;
            if(tab[inf] > val){
                return -1;
            }
 
        } else {
            sup = demi; // balise supérieure trouvée
            // => il reste a trouver le premier element de la liste
            break;
        }
    }
    printf("step1 : inf = %i, sup = %i\n", inf, sup);
 
 
    // ****************************
    //int myTab1[] = {0,1,1,1,2,3,5,7};
    while(1){
        demi = (sup + inf)/2;
 
        if(tab[demi] >= val){
            // Normalement tab[demi] ne devrait jamais etre supérieur a val
            // (mais on fait quand meme le test '<=' au lieu de '==' par sécurité
 
            sup = demi;
            printf("step2a : inf = %i, sup = %i\n", inf, sup);
 
        } else {
            inf = demi + 1;
            printf("step2d : inf = %i, sup = %i\n", inf, sup);
 
            if(inf >= sup){
                printf("step2e : inf = %i, sup = %i\n", inf, sup);
                return sup; // premier element trouvé
            }
        }
    }
 
 
    return -1;
}
 
 
int main()
{
    int index;
    int myTab1[] = {0,1,1,1,2,3,5,7};
    int myTab2[] = {0,0,1,1,1,2,3,5,7};
    int myTab3[] = {0,1,1,2,2,3,5,7};
    int myTab4[] = {0,1,1,1,2,2,3,5,7};
    int myTab5[] = {0,0,0,0,1,2,2,3,5,7};
    int myTab6[] = {0,0,0,0,2,2,3,5,7};
 
 
    // le tableau doit etre trié par odre croissant
    index = find_firstElement(1, myTab1, sizeof(myTab1) / sizeof(*myTab1));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab3, sizeof(myTab3) / sizeof(*myTab3));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab4, sizeof(myTab4) / sizeof(*myTab4));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab5, sizeof(myTab5) / sizeof(*myTab5));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab6, sizeof(myTab6) / sizeof(*myTab6));
    printf("result = %i\n\n", index);
 
    return 0;
}

ça semble fonctionner mais comment faire pour en etre sure ?
voyez-vous des améliorations afin d'optimiser la rapidité de l'algo ?

merci d'avance

06/01/2014, 22h17
Bktero

Bonsoir,

Pourquoi faire 2 while() pour chercher une valeur ?
Il y a trop de return dans la fonction à mon goût, j'ai beaucoup de mal à suivre personnellement. D'ailleurs, qu'est ce que cette fonction est censé retourner ?

En fait je crois que je ne comprend pas du tout ce que tu cherches à faire. Tu essayes d'optimiser le temps de parcours en coupant la zone de recherche à chaque fois ?:oops:
06/01/2014, 22h30
diogene

Sauf erreur de ma part, l'algo est faux dans ce cas : Si le tableau ne comporte qu'une valeur (len ==1) et que cette valeur est celle cherchée, il répond -1 au lieu de 0

@diogene : s'il n'y a qu'une seule valeur, elle ne peut être plusieurs fois dans le tableau, or le PO dit :

Citation:

si la valeur est présente plusieurs fois dans le tableau

D'ailleurs, le test fourni renvoie 4 pour int myTab5[] = {0,0,0,0,1,2,2,3,5,7};. Erreur de codage ou erreur d'énoncé ?
Edition : mauvaise interprétation de la question du PO. Le code suivant est donc incorrect.

Citation:

ça semble fonctionner mais comment faire pour en etre sure ?
voyez-vous des améliorations afin d'optimiser la rapidité de l'algo ?

Je pense que tes tableaux sont beaucoup trop petits pour tester ton algo quant à sa performance. Vu la taille, une banale recherche le long du tableau sera sans doute aussi rapide, voire même plus rapide. As-tu d'ailleurs un algo de ce genre pour faire des comparatifs de perf ? Une fonction telle que celle-ci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 static int find_firstElement_(int val, int tab[], size_t len) { int first = -1; unsigned int occurrences = 0; for(unsigned int i = 0; i < len && tab[i] <= val; i++) { if(tab[i] == val) { occurrences++; if(first == -1) { first = i; } } } return occurrences > 1 ? first : -1; }

06/01/2014, 22h47
diogene

@Bktero
J'interprète son énoncé comme la recherche de la position d'une valeur dans un tableau et dans le cas où elle est présente en plusieurs exemplaires (ce qui pourrait amener à donner des réponses différentes) de donner la position de la première.

D'où ma remarque.
07/01/2014, 07h59
Bktero

@diogene : :oops:
Ca aurait été plus simple de dire : la fonction renvoie l'indice de la première valeur trouvée ou -1 si la valeur n'est pas trouvée...
07/01/2014, 08h22
boboss123

Bonjour,

Citation:

Envoyé par diogene

@Bktero
J'interprète son énoncé comme la recherche de la position d'une valeur dans un tableau et dans le cas où elle est présente en plusieurs exemplaires (ce qui pourrait amener à donner des réponses différentes) de donner la position de la première.

D'où ma remarque.

C'est exactement ça que je veux faire : je suppose qu'il y a plusieurs méthodes pour faire ça mais quelle est la meilleure ?
07/01/2014, 08h47
boboss123

Citation:

Envoyé par Bktero

Bonsoir,
Pourquoi faire 2 while() pour chercher une valeur ?

Dans mon premier while, je fais une recherche par dichotomie classique pour trouver un élément qui soit égal à la valeur recherchée. Donc à la fin de cette étape, on sait que le "resultat final" sera forcement inférieur ou égal au résultat trouvé.
Le second while affine donc le résultat pour trouver le premier élément ... sauf que vous m'avez fait remarqué que ça ne fonctionne pas.

De manière générale, comment faites-vous pour être sure qu'un algo fonctionne ? ... c'est peut être impossible à savoir ?
=> actuellement, je teste mes fonctions avec un certain nombre de tests aléatoires et si ça fonctionne, "j'admets" que ma fonction est opérationnelle : cette méthode n'est pas fiable à 100% car là, je n'ai pas vu qu'il y avait des problèmes (je n'ai pas fait assez de tests => comment définir le nombre de tests min à faire ?).

voici mon nouvel alogo corrigé :

Code:

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
94
 
static int find_firstElement(int val, int tab[], int len){
 
    int sup, inf, demi;
    int max_interation;
 
 
    int i;
    printf("Tab[] =");
    for(i=0; i<len; i++){
        printf(" %i", tab[i]);
    }
    printf("\n");
 
 
    // ****************************
    inf = 0;
    sup = len - 1;
    if(sup < 0){
        return -1;
    }
    if(inf == sup){
        if(tab[sup] == val){
            return sup; // élément trouvé
        } else {
            return -1;
        }
    }
 
 
    // ****************************
    max_interation = 15;
    //while(max_interation){
    while(1){
        demi = (sup + inf)/2;
        printf("step1a : inf = %i, sup = %i, demi = %i\n", inf, sup, demi);
 
         if(tab[demi] > val){
            sup = demi - 1;
            if(tab[sup] < val){
                return -1;
            }
 
        } else if(tab[demi] < val){
            inf = demi + 1;
            if(tab[inf] > val){
                return -1;
            }
 
        } else {
            sup = demi; // balise supérieure trouvée
            // => il reste a trouver le premier element de la liste
            break;
        }
        max_interation--; // protection pour eviter boucle infinie
    }
    printf("step1b : inf = %i, sup = %i\n", inf, sup);
 
 
    // nouveau test car sinon risque de bug
    if(inf == sup){
        return sup; // élément trouvé
    }
 
 
    // ****************************
    max_interation = 15;
    //while(max_interation){
    while(1){
        demi = (sup + inf)/2;
        printf("step2a : inf = %i, sup = %i, demi = %i\n", inf, sup, demi);
 
        if(tab[demi] >= val){
            // Normalement tab[demi] ne devrait jamais etre supérieur a val
            // (mais on fait quand meme le test '<=' au lieu de '==' par sécurité
 
            sup = demi;
            printf("step2b : inf = %i, sup = %i\n", inf, sup);
 
        } else {
            inf = demi + 1;
            printf("step2c : inf = %i, sup = %i\n", inf, sup);
 
            if(inf >= sup){
                printf("step2d : inf = %i, sup = %i\n", inf, sup);
                return sup; // premier element trouvé
            }
        }
        max_interation--; // protection pour eviter boucle infinie
    }
 
 
    return -1;
}

Code:

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
 
int main(){
 
    int index;
    int myTab1[] = {0,1,1,1,2,3,5,7};
    int myTab2[] = {0,0,1,1,1,2,3,5,7};
    int myTab3[] = {0,1,1,2,2,3,5,7};
    int myTab4[] = {0,1,1,1,2,2,3,5,7};
    int myTab5[] = {0,0,0,0,1,2,2,3,5,7};
    int myTab6[] = {0,0,0,0,2,2,3,5,7};
    int myTab7[] = {1};
    int myTab8[] = {1,5,5,5,5,5,5};
    int myTab9[] = {1,10,10,10,10,10,10,10};
    int myTab10[] = {0,0,0,0,0,0,1};
    int myTab11[] = {0,0,0,0,0,0,0,1};
    int myTab12[] = {0,0,0,1,5,5,10};
    int myTab13[] = {0,0,0,1,6,7,10,20};
    int myTab14[] = {14};
 
    // le tableau doit etre trié par odre croissant
    index = find_firstElement(1, myTab1, sizeof(myTab1) / sizeof(*myTab1));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab3, sizeof(myTab3) / sizeof(*myTab3));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab4, sizeof(myTab4) / sizeof(*myTab4));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab5, sizeof(myTab5) / sizeof(*myTab5));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab6, sizeof(myTab6) / sizeof(*myTab6));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab7, sizeof(myTab7) / sizeof(*myTab7));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab8, sizeof(myTab8) / sizeof(*myTab8));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab9, sizeof(myTab9) / sizeof(*myTab9));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab10, sizeof(myTab10) / sizeof(*myTab10));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab11, sizeof(myTab11) / sizeof(*myTab11));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab12, sizeof(myTab12) / sizeof(*myTab12));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab13, sizeof(myTab13) / sizeof(*myTab13));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab14, sizeof(myTab14) / sizeof(*myTab14));
    printf("result = %i\n\n", index);
 
    return 0;
}

=> ça semble fonctionner
=> je ne vois pas trop comment faire pour l'optimiser (si c'est possible)

Je viens d'ajouter une fonctionnalité à ma fonction : si l'élément n'est pas trouvé, la variable errIndex retourne l'index où l'on devrait insérer cet élément dans le tableau pour qu'il soit toujours triés.
Comme ça, avec une unique fonction fonction, on peut :
- savoir où se trouve un élément
- savoir où il faut insérer un élément

Code:

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
94
95
96
97
98
99
100
101
102
103
 
static int find_firstElement(int val, int tab[], int len, int * errIndex){
 
    int sup, inf, demi;
    int max_interation;
 
 
    int i;
    printf("Tab[] =");
    for(i=0; i<len; i++){
        printf(" %i", tab[i]);
    }
    printf("\n");
 
 
    // ****************************
    inf = 0;
    sup = len - 1;
    if(sup < 0){
        *errIndex = 0;
        return -1;
    }
    if(sup == 0){
        if(tab[0] == val){
            return 0; // élément trouvé
        } else {
            if(tab[0] > val){
                *errIndex = 0;
            } else {
                *errIndex = 1;
            }
            return -1;
        }
    }
 
 
    // ****************************
    max_interation = 15;
    //while(max_interation){
    while(1){
        demi = (sup + inf)/2;
        printf("step1a : inf = %i, sup = %i, demi = %i\n", inf, sup, demi);
 
         if(tab[demi] > val){
            sup = demi - 1;
            if(tab[sup] < val){
                *errIndex = demi;
                return -1;
            }
 
        } else if(tab[demi] < val){
            inf = demi + 1;
            if(tab[inf] > val){
                *errIndex = inf;
                return -1;
            }
 
        } else {
            sup = demi; // balise supérieure trouvée
            // => il reste a trouver le premier element de la liste
            break;
        }
        max_interation--; // protection pour eviter boucle infinie
    }
    printf("step1b : inf = %i, sup = %i\n", inf, sup);
 
    if(inf == sup){
        *errIndex = sup;
        return sup; // élément trouvé
    }
 
 
    // ****************************
    max_interation = 15;
    //while(max_interation){
    while(1){
        demi = (sup + inf)/2;
        printf("step2a : inf = %i, sup = %i, demi = %i\n", inf, sup, demi);
 
        if(tab[demi] >= val){
            // Normalement tab[demi] ne devrait jamais etre supérieur a val
            // (mais on fait quand meme le test '<=' au lieu de '==' par sécurité
 
            sup = demi;
            printf("step2b : inf = %i, sup = %i\n", inf, sup);
 
        } else {
            inf = demi + 1;
            printf("step2c : inf = %i, sup = %i\n", inf, sup);
 
            if(inf >= sup){
                printf("step2d : inf = %i, sup = %i\n", inf, sup);
                *errIndex = sup;
                return sup; // premier element trouvé
            }
        }
        max_interation--; // protection pour eviter boucle infinie
    }
 
    // normalement, on ne devrait jamais arrver ici
    *errIndex = -1;
    return -1;
}

Code:

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
 
int main(){
 
    int index, errIndex;
    int myTab1[] = {0,1,1,1,2,3,5,7};
    int myTab2[] = {0,0,1,1,1,2,3,5,7};
    int myTab3[] = {0,1,1,2,2,3,5,7};
    int myTab4[] = {0,1,1,1,2,2,3,5,7};
    int myTab5[] = {0,0,0,0,1,2,2,3,5,7};
    int myTab6[] = {0,0,0,0,2,2,3,5,7};
    int myTab7[] = {1};
    int myTab8[] = {1,5,5,5,5,5,5};
    int myTab9[] = {1,10,10,10,10,10,10,10};
    int myTab10[] = {0,0,0,0,0,0,1};
    int myTab11[] = {0,0,0,0,0,0,0,1};
    int myTab12[] = {0,0,0,1,5,5,10};
    int myTab13[] = {0,0,0,1,6,7,10,20};
    int myTab14[] = {14};
 
    // le tableau doit etre trié par odre croissant
    errIndex = -1;
    index = find_firstElement(1, myTab1, sizeof(myTab1) / sizeof(*myTab1), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab3, sizeof(myTab3) / sizeof(*myTab3), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab4, sizeof(myTab4) / sizeof(*myTab4), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab5, sizeof(myTab5) / sizeof(*myTab5), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab6, sizeof(myTab6) / sizeof(*myTab6), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab7, sizeof(myTab7) / sizeof(*myTab7), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab8, sizeof(myTab8) / sizeof(*myTab8), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab9, sizeof(myTab9) / sizeof(*myTab9), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab10, sizeof(myTab10) / sizeof(*myTab10), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab11, sizeof(myTab11) / sizeof(*myTab11), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab12, sizeof(myTab12) / sizeof(*myTab12), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab13, sizeof(myTab13) / sizeof(*myTab13), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    errIndex = -1;
    index = find_firstElement(1, myTab14, sizeof(myTab14) / sizeof(*myTab14), &errIndex);
    printf("result = %i (errIndex = %i)\n\n", index, errIndex);
 
    return 0;
}

Des commentaires sur ce code (qui semble fonctionner) ?

07/01/2014, 17h41
dinobogan

Je supprimerais la seconde boucle while et modifierais la condition d'arrêt de la première boucle while : la valeur est trouvée si la valeur de la case précédente dans le tableau est différente.
Niveau temps d'exécution ce sera similaire, par contre le code de ta fonction sera environ divisé par 2 !
Ensuite, quitte à faire du dichotomique, autant faire du récursif (sauf contraintes). Le nombre de ligne de la fonction se réduit encore, et elle devient plus simple à comprendre.
Enfin, il faut arrêter la récursivité lorsque le tableau devient petit. Ca dépend du processeur. Mais un nombre aux alentours de 24 devrait faire l'affaire. A partir de N (24, ou autre selon tes tests) tu arrêtes la dichotomie et tu passes en simple boucle for. Cette dernière astuce va te faire gagner en temps d'exécution.
07/01/2014, 17h53
boboss123

Merci pour les conseils.

Pour ce qui est d'utiliser de la récursivité, je voudrais éviter car je travaille sur un µControlleur => j'aimerais autant que possible limiter la consommation excessive de RAM (je ne suis pas à l'octet près).
08/01/2014, 11h31
dinobogan

Oui, d'où le "sauf contrainte". Mais les autres remarques sont toujours valables.
Pour l'arrêt dichotomique, je parlais d'une taille de tableau d'environ '24' suite à quelques tests sur powerPC et x86. Mais sur ton micro-contrôleur, tu devras faire des tests pour trouver le meilleur "nombre magique".
Lorsque j'avais travailler sur les algorithmes de tri rapide sur très grosse volumétrie, j'étais tombé sur un rapport de thèse (Mr Yaroslevski je crois) développant le quicksort dual-pivot. Il démontrait l'utilité d'arrêter la dichotomie lorsque le tableau devenait trop petit. Si tu as un peu de temps, je t'encourage vivement à lire ce qu'il a écrit.
08/01/2014, 14h05
boboss123

ok merci