Discussion :

[nikobordx]

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 :

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

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 :

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

[oodini]

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

Code :

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

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

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

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

[oodini]

Code :

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

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

[white_tentacle]

Code :

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

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

Surtout pas !

Plutôt quelque chose comme :

Code :

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

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)

[Iradrille]

Surtout pas !

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

Code :

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

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.

[nikobordx]

Finalement j'utilise:

Code :

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

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

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

[white_tentacle]

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

Code :

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

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 .

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

[white_tentacle]

Le my_array que j’ai donné compile en l’état.

Pour l’utiliser, tu changes simplement :

Code :

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

v[i][j][k];

par

Code :

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

v(i,j,k);

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

Code :

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

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

[Iradrille]

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.

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 :

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
// 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 :

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

[nikobordx]

@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...
Actuellement je fais un simple:

Code :

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

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);
            }
        }

[white_tentacle]

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.

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 :

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

v(2,3,4) = 12;

[nikobordx]

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

[Iradrille]

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.

[white_tentacle]

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.

[nikobordx]

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

Code :

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

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 :

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

my_array v; // ça plante !

[nikobordx]

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

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
#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 !

[Bousk]

Remplace array par vector