Tri rapide dans liste

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonjour,

Je travaille sur un petit programme qui analyse 200 images afin d'extraire la moyenne de chaque pixel.
Pour ce faire je remplis d'abord un

Code:

vector<vector<vector<int> > > v (200,vector<vector<int> >(480, vector<int>(640)));

une fois remplie, je fais un premier tri, je mets chaque pixel compris entre 0 et 29 dans une pseudo-liste (en tout 8 pseudo-listes car ça va de 0 à 255)...
Voici une partie de mon code:

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
int list1=0, n1=0, list2=0, n2=0, list3=0, n3=0, list4=0, n4=0, list5=0, n5=0, list6=0, n6=0, list7=0, n7=0, list8=0, n8=0;
 
    for (int x = 0; x < 480; x++) {
        for (int y = 0; y < 640; y++) {
            for (int i = 0; i < 200; i++) {
                if (v[i][x][y] <= 29) {
                    list1 += v[i][x][y];
                    n1 += 1;
                } else if (v[i][x][y] >= 30 && v[i][x][y] <= 59) {
                    list2 += v[i][x][y];
                    n2 += 1;
                } else if (v[i][x][y] >= 60 && v[i][x][y] <= 89) {
                    list3 += v[i][x][y];
                    n3 += 1;
                }else if (v[i][x][y] >= 90 && v[i][x][y] <= 119) {
                    list4 += v[i][x][y];
                    n4 += 1;
                } else if (v[i][x][y] >= 120 && v[i][x][y] <= 159) {
                    list5 += v[i][x][y];
                    n5 += 1;
                } else if (v[i][x][y] >= 160 && v[i][x][y] <= 189) {
                    list6 += v[i][x][y];
                    n6 += 1;
                } else if (v[i][x][y] >= 190 && v[i][x][y] <= 219) {
                    list7 += v[i][x][y];
                    n7 += 1;
                } else if (v[i][x][y] >= 220 && v[i][x][y] <= 255) {
                    list8 += v[i][x][y];
                    n8 += 1;
                }
            }
            int total = n1;
            int listfinal = list1;
            if (n2 > total) { total = n2; listfinal = list2; }
            if (n3 > total) { total = n3; listfinal = list3; }
            if (n4 > total) { total = n4; listfinal = list4; }
            if (n5 > total) { total = n5; listfinal = list5; }
            if (n6 > total) { total = n6; listfinal = list6; }
            if (n7 > total) { total = n7; listfinal = list7; }
            if (n8 > total) { total = n8; listfinal = list8; }
            int final_v = listfinal / total;
        }
    }

Cela fonctionne parfaitement cependant c'est un peu trop lent à mon goût (entre 10 et 12 secondes).

Pouvez-vous me dire comment puis-je accélérer ce tri ? utiliser une approche différente peut-être ?

Merci d'avance pour vos réponses,
Cordialement,
Nicolas.

04/03/2014, 15h38
oodini

Commence par créer, à l'intérieur du for le plus interne, une valeur intermédiaire :

Code:

const int value = v[i][x][y];

Si ta valeur t'envoyait dans le dernier if, ça te fera 3 appels de fonction plutôt que 78...
04/03/2014, 15h46
white_tentacle

En général, plutôt qu’un triple vecteur (vu que c’est de taille fixe), on utilise un seul tableau (std::array) wrappé dans une classe qui permet les accès indicés à l’aide de l’opérateur (i,j,k).

C’est déjà une première piste pour améliorer les performances.
04/03/2014, 15h58
nikobordx

Merci beaucoup pour vos réponses.

@oodini: c'était effectivement logique, et grâce à ça, je passe à 2-3 secondes de traitement.
@white_tentacle: je vais regarder pour remplacer le triple vecteur, mais étant débutant, je ne sais pas encore comment faire. ;)
04/03/2014, 16h01
oodini

Code:

std::array<std::array<std::array<int,640>,480,200) v;
04/03/2014, 16h17
white_tentacle
Citation:

Envoyé par oodini

Code:

std::array<std::array<std::array<int,640>,480,200);

Surtout pas !

Plutôt quelque chose comme :
Code:

1 2 3 4 5 6 7 class my_array { std::array<int, 640*480*200> arr; public: int& operator()(int i, int j, int k) { return arr[i*480*200 + j*200+k]; } };
(de tête, probablement à adapter/vérifier)

Citation:

Envoyé par white_tentacle

Surtout pas !

Il n'y à aucune différence pour un std::array entre
Code:

1 2 3 4 5 6 7 8 std::array<std::srray<std::array<int, 200>, 200>, 480> // et class my_array { std::array<int, 640*480*200> arr; public: int& operator()(int i, int j, int k) { return arr[i*480*200 + j*200+k]; } };
Avec l'utilisation de std::vector, il y à bien une différence par contre.

04/03/2014, 17h41
nikobordx

Finalement j'utilise:

Code:

array<array<array<int, 640>, 480>, 200> v;

Et je gagne encore 1 seconde !
Merci beaucoup pour vos réponses.
Cordialement,
Nicolas.

Citation:
Envoyé par Iradrille
Il n'y à aucune différence pour un std::array entre
Code:

1 2 3 4 5 6 7 8 std::array<std::srray<std::array<int, 200>, 200>, 480> // et class my_array { std::array<int, 640*480*200> arr; public: int& operator()(int i, int j, int k) { return arr[i*480*200 + j*200+k]; } };
Avec l'utilisation de std::vector, il y à bien une différence par contre.
Pas de différence sur la quantité de mémoire utilisée, en revanche, les accès sont plus lents avec l’array d’array d’array (pas de possibilité pour le compilateur de les optimiser, donc, tu te tapes à chaque fois l’appel à operator[] en triple au lieu d’un appel simple). Rajoute à ça le fait tu exposes ton mapping mémoire, et donc, t’empêche d’en changer un pour être plus adapté à tes parcours sans changer aussi le code client, et au final il n’y a que des inconvénients (à part peut-être la flemme ?) à utiliser des array imbriquées :).

04/03/2014, 18h33
nikobordx

Je voudrais bien essayer d'utiliser un tableau wrappé dans une classe, mais je ne trouve pas d'exemple complet (remplissage, lecture) simple sur le net. :(
04/03/2014, 18h51
white_tentacle
Le my_array que j’ai donné compile en l’état.

Pour l’utiliser, tu changes simplement :

Code:

v[i][j][k];

par

Code:

v(i,j,k);

Petite correction toutefois, par rapport à ce que j’ai posté, c’est plutôt :
Code:

1 2 int& operator()(int i, int j, int k) { return arr[i*480*640 + j*640+k]; } int const& operator()(int i, int j, int k) const { return arr[i*480*640 + j*640+k]; } // version const
(pour garder une matrice 200 * 480 * 640, et pas 640 * 480 * 200 comme j’avais fait).

Citation:

Envoyé par white_tentacle

Rajoute à ça le fait tu exposes ton mapping mémoire, et donc, t’empêche d’en changer un pour être plus adapté à tes parcours sans changer aussi le code client, et au final il n’y a que des inconvénients (à part peut-être la flemme ?) à utiliser des array imbriquées :).

La dessus on est d'accord.

Citation:

Envoyé par white_tentacle

en revanche, les accès sont plus lents avec l’array d’array d’array (pas de possibilité pour le compilateur de les optimiser, donc, tu te tapes à chaque fois l’appel à operator[] en triple au lieu d’un appel simple)

Les appels sont inline, ça sera optimisé.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 // taille des tableaux réduite, je me tapais des stackoverflow sinon ^^" class my_array { std::array<int, 64*48*20> arr; public: int& operator()(int i, int j, int k) { return arr[i*48*64 + j*64+k]; } }; int main() { std::array<std::array<std::array<int, 64>, 48>, 20> a; my_array b; int i1, i2, i3, i4, i5, i6; std::cin >> i1 >> i2 >> i3 >> i4 >> i5 >> i6; int c = a[i1][i2][i3]; std::cout << c; int d = b(i4, i5, i6); std::cout << d; return 0; }
génère
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 std::cout << c; 004012E0 mov eax,dword ptr [esp+4] 004012E4 mov ecx,dword ptr ds:[40303Ch] 004012EA lea eax,[eax+eax*2] 004012ED shl eax,4 004012F0 add eax,dword ptr [esp+14h] int c = a[i1][i2][i3]; 004012F4 shl eax,6 std::cout << c; 004012F7 add eax,dword ptr [esp+0Ch] 004012FB push dword ptr [esp+eax*4+18h] 004012FF call dword ptr ds:[403024h] std::cout << d; 00401305 mov eax,dword ptr [esp] 00401308 mov ecx,dword ptr ds:[40303Ch] 0040130E lea eax,[eax+eax*2] 00401311 shl eax,4 00401314 add eax,dword ptr [esp+8] int d = b(i4, i5, i6); 00401318 shl eax,6 std::cout << d; 0040131B add eax,dword ptr [esp+10h] std::cout << d; 0040131F push dword ptr [esp+eax*4+18h] 00401323 call dword ptr ds:[403024h]
Vu le code généré, si différence de perf il y a, elle sera minime.
Dans les 2 cas, c'est un calcul d'adresse, avec un seul accès mémoire à la fin.

@white_tentacle:
Merci de ta réponse, c'est effectivement simple pour lire les valeurs, cependant je n'ai pas compris comment je dois faire pour remplir le tableau... :oops:
Actuellement je fais un simple:
Code:

1 2 3 4 5 for (int x = 0; x < 480; x++) { for (int y = 0; y < 640; y++) { v[i][x][y] = (int)v_channel[2].at<uchar>(x, y); } }

04/03/2014, 19h39
white_tentacle

Citation:

Envoyé par Iradrille

Vu le code généré, si différence de perf il y a, elle sera minime.
Dans les 2 cas, c'est un calcul d'adresse, avec un seul accès mémoire à la fin.

J’ai un facteur 1,8 environ en release chez moi, que ce soit avec gcc ou clang (clang est notablement plus lent dans les deux cas, d’ailleurs), sur un code qui remplit le tableau.

Citation:

Merci de ta réponse, c'est effectivement simple pour lire les valeurs, cependant je n'ai pas compris comment je dois faire pour remplir le tableau...

Comme l’opérateur() renvoie un int&, tu peux faire tout simplement :

Code:

v(2,3,4) = 12;
04/03/2014, 20h15
nikobordx

Merci, cependant je ne peux l'utiliser car ça plante (gdb ne me donne aucune information).
04/03/2014, 22h32
Iradrille

Citation:

Envoyé par white_tentacle

J’ai un facteur 1,8 environ en release chez moi, que ce soit avec gcc ou clang (clang est notablement plus lent dans les deux cas, d’ailleurs), sur un code qui remplit le tableau.

Je ne pensais pas que la différence serait si grande, du coup ta solution est meilleure sur tous les points. :)
05/03/2014, 09h19
white_tentacle

Citation:

Envoyé par nikobordx

Merci, cependant je ne peux l'utiliser car ça plante (gdb ne me donne aucune information).

Peux-tu poster le code qui plante ?

À mon avis, c’est simplement une histoire de dépassement de bornes, probablement liée à une petite erreur sur les indices.

J'utilise la classe que tu m'as donnée:
Code:

1 2 3 4 5 6 class my_array { std::array<int, 640*480*200> arr; public: int& operator()(int i, int j, int k) { return arr[i*480*640 + j*640+k]; } };
et dans la fonction main:

Code:

my_array v; // ça plante !

Après un petit test, je pense qu'effectivement l'array est trop grand car:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <array>
 
using namespace std;
 
class my_array {
    array<int, 100*100*100> arr;
public:
    int& operator()(int i, int j, int k) { return arr[i*100*100 + j*100+k]; }
};
 
int main(int argc, const char *argv[]) {
    my_array vtest;
    for (int i = 0; i < 100; i++) {
        vtest(i, i, i) = i + 10;
    }
    for (int i = 0; i < 100; i++) {
        cout << "Value: " << vtest(i, i, i) << endl;
    }
    return 0;
}

fonctionne parfaitement ! :?

05/03/2014, 12h31
Bousk

Remplace array par vector

Voir 40 message(s) de cette discussion en une page