Allocation dynamique et imbrication "paramétrée"

Salut à tous !

Mon problème est le suivant :
Lorsqu'on veut parcourir un tableau à une dimension, on écrit une boucle "for"...
Pour 2 dimensions, 2 boucles "for" imbriquées... Ainsi de suite. N'est-ce pas ?

Ma question c'est donc de savoir comment généraliser cela à un tableau à n dimension, n étant un entier (>0)

donné par l'utilisateur lors de l'exécution (pour stocker par exemple un tenseur d'ordre n).

Clairement, 2 problèmes se posent :

1)Comment créer dynamiquement le tableau à n dimension (hypercube de dimension n) qui va recevoir les

composantes qui sont au nombre de L^n, si on considère que chaque dimension possède un nombre constant L de lignes/colonnes/etc. ?

2)Comment "paramétrer" la profondeur d'imbrication des boucles "for" pour le parcours, puisqu'il faut a priori

quelque chose du type

Code:

---

1 2 3 4 5 6 7 8

for(i) { for(j) { etc... //tab[i][j][k][...] } }

---

C'est à dire n boucles imbriquées...

Citation:

---

Envoyé par ulr2012

Mon problème est le suivant :
Lorsqu'on veut parcourir un tableau à une dimension, on écrit une boucle "for"...
Pour 2 dimensions, 2 boucles "for" imbriquées... Ainsi de suite. N'est-ce pas ?

Ma question c'est donc de savoir comment généraliser cela à un tableau à n dimension, n étant un entier (>0)

---

En général, une fonction récursive est adaptée pour cela. La question qui se pose étant alors : quelles opérations comptes-tu appliquer à chaque niveau d'imbrication des boucles ?

Citation:

---

Clairement, 2 problèmes se posent :

1)Comment créer dynamiquement le tableau à n dimension (hypercube de dimension n) qui va recevoir les

composantes qui sont au nombre de L^n, si on considère que chaque dimension possède un nombre constant L de lignes/colonnes/etc. ?

2)Comment "paramétrer" la profondeur d'imbrication des boucles "for" pour le parcours, puisqu'il faut a priori

---

Les classes template donnent de bons résultats. Mais il y a plusieurs paramètres à prendre en compte. Cette discussion traitait d'un problème similaire :

http://www.developpez.net/forums/d12...late-heritage/

Pour un tableau de dimension N il existe aussi Boost.MultiArray, mais N doit être connu à la compilation. As-tu en tête un exemple où N devrait être connu à l'exécution ?

Si c'est le cas, comme le dit Obsidian, il faut regarder du côté des fonctions récursives :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

template <typename _T, typename _DimIter> void workOn(_T* data0, _DimIter beg, _DimIter end) { if (beg==end) return; /* ici traitement qui varie selon std::distance(beg,end) */ workOn(data0,beg+1,end); }   int dims[] = { 3, 4, 5, 6 }; double arr[3][4][5][6];   workOn(&arr[0][0][0][0], dims, dims+4);

---

Un exemple de pb où N devrait être connu à l'exécution c'est typiquement l'acquisition d'un tenseur d'ordre N, dont on pourra faire un traitement par la suite...

une dimensionnalité connue à l'exécution est assez impractivable et donne des perfs moisies. Il vaut mieux avoir une dimensionalité maximale statique et autorisé les dimensionalité intermediaires. Ensuite, au dela de 3D, la pression sur les registre spour l'indexage va dramatiquement faire chuter les performances, empecher la vectorisation et rendre le code générer assez moche. EN gros si N = 1 faire 1 boucle, N> 1 faire 2 boucle en traitant les données nD comme des plaques 2D ordonnées proprement.

Pour les operations elementwise, ca ne changera rien. POur les quelques opérations dependantes de la position, il faudra localement revenir de la position 2D "physique" a la dimension nD logique.

Quant à faire une fonction récursive pour enchainer des boucle for, j'emets des doutes sur l'efficacité de la chose au final.

Citation:

---

Envoyé par ulr2012

Ma question c'est donc de savoir comment généraliser cela à un tableau à n dimension, n étant un entier (>0)
donné par l'utilisateur lors de l'exécution (pour stocker par exemple un tenseur d'ordre n).

---

En premier lieu, un valarray (dans la STL), et les splice qui vont avec. C'est fait pour ce type de problème. Les "pros" les méprisent un peu, parce qu'ils ont la réputation d'être inefficaces, mais ils sont souvent plus rapides que pas mal de code "fait main" écrit pour les remplacer...


Ensuite, si le tableau n'est pas trop grand (assez petit pour tenir dans un bloc de mémoire contigue), le plus simple est d'en faire un tableau monodimensionnel de taille adaptée (L^N ici) Si on a juste besoin de parcourir tous les éléments, une boucle unique suffira (et les coordonnées de chaque élément sont assez facile à déduire de sa position)

S'il est un peu trop grand, un tableau de tableaux comme précédemment, sur la première dimension (ou les deux premières). Ca rend le parcours et le calcul des coordonnées un peu plus complexes.

S'il est carrément énorme, et contenant relativement peu d'éléments non nuls, on va vers des matrices creuses, et ca devient un peu spécialisé (mais il y a beaucoup de littérature sur le sujet).

L'intérêt de l'approche est qu'elle fonctionne même si le tenseur n'est pas "hypercubique" (c'est à dire même si toutes les dimensions n'ont pas la même taille).

Francois

Citation:

---

Envoyé par ulr2012

Un exemple de pb où N devrait être connu à l'exécution c'est typiquement l'acquisition d'un tenseur d'ordre N, dont on pourra faire un traitement par la suite...

---

Tu peux très bien passer l'ordre du tenseur en paramètre template d'une fonction.
Tu es peut-être trop pessimiste sur la quantité d'infos qu'on peut déduire dès la compilation.