Tri rapide dans liste

Version imprimable

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, 14h38
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, 14h46
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, 14h58
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, 15h01
oodini

Code:

std::array<std::array<std::array<int,640>,480,200) v;
04/03/2014, 15h17
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, 16h41
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, 17h33
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, 17h51
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, 18h39
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, 19h15
nikobordx

Merci, cependant je ne peux l'utiliser car ça plante (gdb ne me donne aucune information).
04/03/2014, 21h32
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, 08h19
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, 11h31
Bousk

Remplace array par vector
05/03/2014, 11h36
Iradrille
Citation:

Envoyé par nikobordx

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

C'est pas étonnant, demander ~245Mo dans la pile c'est énorme.
Ce qui est plus étonnant c'est que array<array<array<int, 640>, 480>, 200> v; ne plante pas.
Code:

1 2 3 4 std::unique_ptr<my_array> v(new my_array); // allocation sur le tas -> plus de soucis. (*v)(1, 1, 1); // a la place de v(1, 1, 1);
Ou comme dit Bousk, l'utilisation de vector est possible, (sans oublier les appels à reserve !)

Finalement j'ai modifié la classe:
Code:

1 2 3 4 5 6 7 class my_array { int* arr; public: my_array() { arr = new int[640*480*200]; } ~my_array() { delete [] arr; } int& operator()(int i, int j, int k) { return arr[i*480*640 + j*640+k]; } };
Je passe de 1900-200 ms de traitement à environ 1750 ms.
Pour vous c'est correct ?

05/03/2014, 11h51
nikobordx

Bon finalement j'ai encore modifié la classe, j'utilise des "unsigned char", je passe à 1480 ms de traitement, c'est parfait ! :mrgreen:

Je serais curieux (et sceptique) de savoir sur quoi tu te bases pour tes temps d'exécution ?
Code:

1 2 3 4 5 6 7 template<class TYPE, unsigned int D1, unsigned int D2, unsigned int D3> class Array3D { std::vector<TYPE> vec; public: Array3D() :vec(D1*D2*D3) {} int& operator()(unsigned int i, unsigned int j, unsigned int k) { return vec[i*D1*D2 + j*D2 + k]; } };
Un truc comme ça est plus joli amha.
Utiliser un std::array pour faire un new, je trouve vraiment ça d'un non-sens.

1. Ma classe est comme ceci:
Code:

1 2 3 4 5 6 7 class my_array { unsigned char* arr; public: my_array() { arr = new unsigned char[640*480*200]; } ~my_array() { delete [] arr; } unsigned char& operator()(int i, int j, int k) { return arr[i*480*640 + j*640+k]; } };
je n'utilise plus std::array ;)

2. Pour le temps d'exécution j'utilise les fonctions fournies par opencv:
Code:

1 2 3 4 5 6 double t = (double)cvGetTickCount(); // Code t = (double)cvGetTickCount() - t; cout << "Time " << t/((double)cvGetTickFrequency()*1000.) << " ms" << endl;
et, aussi, tout simplement lorsque j'arrive à la fonction de tri, je compte les secondes... ;)

05/03/2014, 14h15
white_tentacle

Citation:

Envoyé par Bousk

Un truc comme ça est plus joli amha.
Utiliser un std::array pour faire un new, je trouve vraiment ça d'un non-sens.

std::vector est, à mon sens, fait pour un tableau redimensionnable. std::array est fait pour un tableau de taille fixe. Utiliser std::vector seulement parce que tu veux allouer dans le tas et pas la pile me semble très discutable.

Après, effectivement, quitte à utiliser new, tu peux directement passer par un tableau C.
05/03/2014, 18h30
jblecanard

Citation:

Envoyé par white_tentacle

std::vector est, à mon sens, fait pour un tableau redimensionnable. std::array est fait pour un tableau de taille fixe. Utiliser std::vector seulement parce que tu veux allouer dans le tas et pas la pile me semble très discutable.

Après, effectivement, quitte à utiliser new, tu peux directement passer par un tableau C.

Aucun rapport, rien ne t'empêche d'allouer un std::array sur le tas avec un new :aie:. Quant à allouer volontairement dans le tas, c'est tout à fait justifié si la taille du tableau est très grande. Il ne faut pas oublier que la pile a une taille limitée et que son rôle n'est pas de stocker de grandes quantités de données.