Salut à tous,
 
je touche chaque jour un peu plus mes lacunes, et je suis face à un problème de conception sur lequel je voudrais votre avis.
 
Je dispose d'un tableau 1D de la forme
 

qui représente une image.
 
Pour chacune de ces cases, je vais faire N calculs, les calculs ne différant que par un jeu de 2 paramètres et renvoyant un seul résultat, en faisant une boucle sur N, puis une boucle sur l'image.
J'ai besoin de garder, pour chaque case de mon tableau la liste des résultats, ainsi que, pour chaque résultat, le jeu de paramètre qui l'a engendré. Quel genre de boîte serait adapté à ce problème?

C'est très abstrait, mais p'têt un truc du genre une structure rassemblant les paramètres + résultat, et ensuite une map associant une instance de cette structure pour chaque numéro de case sur laquelle un calcul a été effectué ?

En gros t'as une image et tu fais des calculs sur chaque pixel dont tu veux conserver chaque résultat ?

ca dépend aussi de la manière dont tu voudras utiliser ces résultats associés à ces paramètres.
 
Si c'est pour faire des recherches d'une case donnée régulièrement ou si c'est pour faire toujours des parcours linéaires complets de ta structure, tu vas pas faire le même choix

Par la suite, je ferais un parcours régulier sur toute l'image. Concernant les résultats à stocker, j'aurais besoin de faire au moins un tri sur chaque vecteur de résultat. Avant que vous me disiez que je n'ai qu'à garder le premier de chaque vecteur, je précise que je cherche justement à éviter ça.

 
Perso vu qu'à priori il n'y a rien de sparse, que tailles sont identiques et que tu ne cherches pas à maintenir une structure triée, mais juste à trier à la fin, je ne vois pas pourquoi ne pas utiliser des vectors.
 

 
Et puis à la fin tu fais un std::sort(pixel.begin(), pixel.end()) pour chaque pixel.
Tu initialises avec les bonnes tailles, tu insères en temps constant au fil de tes calculs et tu tries à la fin chaque pixel en O(nlogn).

l'heritage public de vector me fait pleurer du sang.
un héritage privé me semble de meilleur aloi vu que les classes de la stl ne sont pas conçus pour etre hériter publiquement.
 
Sinon ouais

 
Comme on m'a appris comme ça en cours, je veux bien que tu développes cette aversion pour l'héritage public des std containers.
C'est parce qu'ils ne présentent pas tous la même interface ? Ou bien il y a une raison plus profonde ?
 
Je suis toujours ouvert pour m'améliorer ;-)

 
ils n'ont pas de destructeur virtuel, ca fait le premier argument lourd en défaveur d'un héritage public

Ok, là je veux bien qu'on m'explique le lien entre destructeur virtuel et héritage public.

Vu que ton image a une taille fixe, pourquoi pas un simple array de struct qui contiennent les infos dont t'as besoin ?

Pourquoi pas, je suis pas sectaire, je cherche juste à savoir quelles sont mes options, et, vu ce que je fais, laquelle serait la plus adaptée et la plus performante.

l'héritage public te permet de manipuler directement ton instance sous forme de vector, sauf que, si tu détruits ton instance en la considérant comme un vecteur, tu n'appelleras pas le destructeur de ta classe.
 

 
l'execution du prog :

 
CQFD : le destructeur de A n'a pas été appelé

 
+1
 
Je n'avais pas pensé à ce problème car quand j'hérite d'un std container, je n'utilise pas de polymorphisme sur cet héritage...
Vous m'embêtez parce j'aime bien ne pas avoir à surcharger explicitement toutes les méthodes membres des containers. Fénéant power !

si t'aimes bien faire du caca, c'est ton choix

Dans la mesure où la taille de ton image est fixe, que la taille des données à stocker est fixe et déterminée à l'avance, autant faire du tout fixe avec un array de structs, qui t'apportera haute performance niveau accès mémoire et la plus faible utilisation mémoire possible vu que tu stockes le strict minimum.

C'est tellement un cas simple et évident que je m'imagine pas utiliser autre chose, c'est carrément un exemple idéal de l'utilisation d'un array et de structs.

Je suis fénéant, mais je suis conscient quand je fais du caca .  
Enfin pour le coup du destructeur non virtuel j'y avait pas pensé. lalalala

 
Ouais enfin c'est un peu .
Bon ceci dit ça peut arriver qu'un nigaud détruise l'instance via un ptr sur std::vector<> ou autre truc dangereux, mais bon c'est un nigaud.
 
Moi le caca, je le vois surtout dans la logique du std::vector<> par pixel
Surtout qu'à priori ce sera bien le même nombre de paramètres/résultat pour tous les pixels.

bah, sur un vector, je peux appeler directement std::sort(), ou std::partial_sort(), sur une struct, c'est plus chiant, il faut que je re-fasse un truc idoine.
 
Tant qu'on y est, on écrit fainéant, hein (à moins de l'être vraiment à fond   )

Si c'est une image, pourquoi est-ce que t'aurais à appeler cette fonction ?

 
En cas d'héritage privé, tu n'as pas besoin de les surcharger. Tu peux juste publier l'interface qui te convient, et ca prend pas beaucoup de temps, en général

Oups    
 

Le but est pas de l'appeler sur l'image mais sur chaque vector d'expérience si je ne m'abuse.

 
BLABLA, std::vector à genre 0.1% d'overhead sur [] versus du pointeur crados, stop le FUD là

 
Je préfére faire le casse burne que laissez passser ça pour en voir 34567890 partotu aprés.
J'ai mon image de   à conserver moi monsieur.
 

 
Deja un boost::multi_array me parait mieux pour l'aspect 2D, donc un truc genre
 
boost::multi_array< boost::array<float,N> >  
 
est peut etre pas mal

 
Bah nan attends, je stockes 300 000+ octets, je peux pas me permettre de prendre 3 pointeurs en plus pour faire un std::vector
 

 
Je vais regarder mais ca me ferais mal que tu gagnes et que tu me fasses faire du boost:: (mauvaise foi inside). Ou alors la prochaine fois que tu passes, tu m'installes boost comme ça j'aurais plus d'excuses...

lol arrete:
 
./bootstrap.sh && sudo make install

Mais quand je tape ça dans Word, y'a rien qui se passe

Ce genre de chose fait vite une différence sur des larges volumes de données. Et du pointeur crados... aucune différence, le seul truc avec std::vector c'est que c'est aussi crado mais tu le vois pas.

 
don't feed the troll.
 
Sinon, t'as des benchs significatifs sur tes "larges volumes de données" (et là, je demande des benchs avec les checks sur les itérateurs et dimensions désactivés) ?
 

J'aurais plus fait un truc du genre :

typedef int result_type;
typedef int param_type;
 
struct computation {
   param_type param1;
   param_type param2;
   std::vector<result_type> result_for_all_pixels; // taille = x*y
};
 
struct computations {
   std::vector<computation> all_results; // taille = N
};

Je préfère avoir N vecteurs de x*y éléments que x*y vecteurs de N éléments, surtout que tu va itérer sur les x*y élements d'un seul set de paramètre quand tu fais ton calcul (donc autant te balader dans un seul tableau linéairement et ne pas fatiguer le cache).

[edit]
J'avais pas vu l'histoire du tri sur le vecteur de résultats Ça casse un peu l'histoire du cache, quoique si N est pas trop grand et avec un truc genre merge sort mais avec chaque phase du merge qui tourne sur tout le tableau, ça peut super bien passer en fait...

J'ai fait pas mal d'assembleur, et j'ai souvent rencontré ce genre de problème. Et il est tout à fait logique qu'une commande qui prend plus de cycles d'horloge, bien que l'augmentation soit insignifiante, engendre une différence de plus en plus notable avec l'augmentation des itérations. Je vois même pas pourquoi je me casse le cul à expliquer ça d'ailleurs, c'est un fait très largement connu. Tout dépend derrière de la puissance disponible, de ce que tu cherches à faire... mais il y a clairement une différence.

Quoi qu'il en soit, si tu penses que tu peux faire plus rapide qu'un accès direct à la mémoire... ben écoute j'attends tes benchs.

 
Ben un accès préfetché à la mémoire

 
Sauf que quand tes volumes de données deviennent grand, c'ets les c ache misses puis les tlb misses qui vont devenir préponderant devant le cycle et demi d'indirection d'adresse.
 
Et si t'en ai encore à te toucher la nouille à faire de l'assembleur, j'ai une mauvaise nouvelle pour toi, les compilos font mieux que toi depuis bientot 5 ans.
 
alors,on est en C++, donc on utilise vector, multi_array et conseour. Sinon, t'as la catégorie C à coté. Merci d'être passé.
 

Si c'est mal codé, forcément...
 

Un compilateur va plus vite, mais j'ai encore du mal à trouver un compilateur qui fasse mieux qu'un être humain. Coder des goulots d'engorgement à la main peut faire gagner des grosses perfs. On gagne toujours à concevoir ses propres solutions.
 

Me semble que la question de base c'était "c'est quoi le mieux ?"
Et vu l'époque à laquelle on vit, j'ai de plus en plus de mal à comprendre le sectarisme C/C++.
 

Excuse rejetée

Euh, on est bien entrain de parler de operator[] sur un vector versus operator[] sur de la mémoire là ? Genre le truc ou le code du premier est exactement le même que le second ? Le truc ou il faut vraiment insister et désactiver les variables d'induction et l'inlining pour que ça fasse une différence une fois compilé ?

 
je plussoie, le code généré avec optimisation du compilo est identique, d'où mon insistance pour les benchs, je ne sais pas d'où sortiraient ces miraculeuses instructions supplémentaires

 
du vilain compilo c++ qui fait qu'a faire du code lent bien évidemment

5% des gens savent ce qu'ai une TLB et 1% un cache. A part qqs experts, tout le monde code mal selon toi ?
 

je te parlais de micro optimisation à la ouanagéne.
 

Le C, c'ets 1492, le C++ c'ets 2011 c'est tout.

Si on peut faire mieux, c'est que c'est mal foutu, non ?

Ah bah oui je me doute bien, mais moi aussi je parle d'optimisation
J'ai autre chose à foutre que coder des applis complètes en assembleur

Ça sera 1492 le jour où on sera pas obligé de passer par le C pour gagner en perfs