Discussion :

[deubelte]

Bonjour,

Je cherche a remplir une matrice avec C++ au grand maximum de taille: 100*100.
Quelle est la meilleure facon de declarer une telle matrice?
Sachant que la taille est faible, faut il utiliser un code "simple" ou les <vector>,<map>.....
Merci

[JolyLoic]

A part la remplir, tu comptes en faire quoi de ta matrice ? Si c'est pour faire des opérations mathématiques, autant prendre une matrice d'une bibliothèque mathématique. Si c'est une matrice de pixels, autant prendre une matrice d'une bibliothèque d'images,...

Si c'est un cas non classique, alors si la matrice est pleine, autant choisir la solution la plus simple, c'est à dire un vecteur (ou un vector enrobé d'une légère couche afin que maMatrice(10, 42) retourne l'élément monVecteur[10*taille + 42]).

Si elle est creuse (beaucoup, une large majorité, de cases vides), une autre structure peut être intéressante, genre un map<pair<int, int>, monType >, ou une structure spécialisée pour la recherche par proximité, genre un quad tree.

[deubelte]

voici ce que je veux faire:
il s'agit de reproduire un tableau a double entrée. Dans la premiere ligne et la premiere colonnes, il y a des données.

Mettons par exemple qu'a sur la première ligne on a:
1,2,3,.........10
Premiere colonne on a: :
1
2
3
....
10

Et dans chaque case (i,j) je veux calculer le produit de la valeur de la i eme valeur de la premiere colonne par la jieme valeur de la première ligne.

voici ce que j'ai fait, pour remplir le tableau:

Code :

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

1
2
3
4
5
6
7
8
9
 
double** t2 = new double*[10];
 
for(int i=0;i<10;i++) {
	t2[i]=new double[10];
	    for(int j=0;j<10;j++){
         	t2[i][j]=......;
      	}
}

[JolyLoic]

Le problème là est que tu alloues manuellement de la mémoire, et donc que tu dois la désallouer manuellement, ce que tu n'as pas fait dans le code d'exemple, et qui au final n'est pas si simple à faire dans un vrai code.

Au minimum, je pense que j'écrirais un truc du genre (code non testé):

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
class Matrice
{
  Matrice(int largeur, int hauteur);
  double &operator()(int x, int y);
private:
  int maLargeur;
  int maHauteur;
  std::vector<double> mesDonnees;
};
 
Matrice::Matrice(int largeur, int hauteur) : 
  maLargeur(largeur), 
  maHauteur(hauteur),
  mesDonnees(largeur*hauteur)
{
}
 
double &Matrice::operator()(int x, int y)
{
  assert(x>=0);
  assert(x<maLargeur);
  assert(y>=0);
  assert(y<maHauteur);
  return mesDonnees[x + largeur * y];
}
 
int main()
{
 Matrice M(10, 10);
 for(int i=0;i<10;i++) 
 {
    for(int j=0;j<10;j++){
       	M(i, j) =......;
    }
  }
}

[loufoque]

Est-ce que la taille est statique ?

[DEVfan]

bonjour, je repique l'idee de ce topic pour l'etendre (peut-etre)...

Je souhaite egalement optimiser une sorte de tableau pour gerer des sortes d'images. Le probleme est qu'en realite, il ne s'agit ni d'image, ni d'un tableau avec plein de trou.

En realite, il s'agit de regrouper un ensemble de coordonne qui de facon pratique sera assez compact mais peut aussi avoir des points isoles , avec un tableau simple de point... enfin un objet qui sera contenu a cette coordonnee.

Le tableau lineaire ou rectangulaire de donnee est donc deconseille. Je pense le map<pair<int, int>, monType > egalement et je ne connais pas le quad tree.

QQ1 (qui s7il lit se reconnaitra) m'a propose de voir Boost.MultiIndex ou std::set <std::set <T> >.

Quel est votre avis sur la question?

Schant que mes ensembles seront compact si troue, j'ai fait une petite fonction de recherche qui m'a l'air adaptee ( http://www.developpez.net/forums/sho...d.php?t=391030 ). Mais c'est pas encore au point pour le cote generique. De plus s'il existe qq chose de tout fait, ce sera sans doute mieux niveau optimisation...

Donc comment faire une classe astucieuse qui ressemble a pair< vector<Coordonnee> , vector<monType > >?
Sachant que les actions sur monType (addition, multiplication, etc si valeur) sont a optimise (tableau de 1000 facile) et que les actions sur les ensembles seront presents mais relativement rare normalement.

Merci d'avance.
PS : Si pas clair, merci de le dire...

[DEVfan]

Bon je vais preciser un peu vu les reponses

Objectif : faire une classe qui servira de base a une application. Cette classe doit constituer une "Algebre" adaptee a la manipulation de cellule : Coordonnee+INFO (conteneur 2D+contenu). Le type le plus utilise sera sans doute <abscisse, ordonnee, double>.

Le conteneur 2D doit etre ensembliste et ordonnee (je pensais donc a un std::vector avec une option unique). La recherche d'un element doit etre la plus rapide possible.
Le type INFO est value (enfin type) et doit etre "optimise" en vitesse de traitement pour des operations de masse (genre tab1+tab2....et le cote ensembliste doit determiner les communs par exemple)

Comment concilier au mieux ces deux entites? Sachant que les 2 doivent etre optimise, il s'agit d'un compromis... qu'elles sont les templates ou class deja existante que vous pourriez me conseiller dans ce sens?

[yan]

bonjour,
je n'ai pas tout compris, mais en gros tu veut faire une matrice quelconque N*M qui contienne X, avec n et m des index.
Pour cela tu peut utiliser un vector :

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
std::vector<X> notation (N*M);
 
//exemple d'accés a la cellule i,j
//mais cela dépend beaucoup 
//si tu veut les aligner suivant la ligne ou la colone
vect[i*n+j]
 
//recherche d'un élément X
std::vector<X>::iterator it;
it = std::find(vect.begin(),vect.end(),&foncteur_recherche);

pour les algorithm va voir ce tutorial

Les tableau 1D pour représenter un tableau 2D est trés utilise pour diverse raison :
- peu de problème de mémoire
- accès simple à un élément
- parcours simple et performant de tout les éléments.


Ensuite ton X c'est que tu veut. une pair, une list ou autre. Mais je pense que le mieux serait une class que tu fera toit même. Tu pourra ainsi implémenter les operateurs de comparaison, le =, définir l'état "pas de données" de ta class ...

[DEVfan]

Merci mais ca je sais... le probleme c'est que c'est pas un RECTANGLE. C'est un ensemble quelconque genre un rectangle, un cercle et un point... ou l'intersection de 2 cercles, etc.

J'ai le choix en fait entre une representation de lien, type TOC... chaque cellule est repertorie independemment mais ensuite c'est la merde pour faire des operations de voisinages, il faut lister dans cette liste ceux qui conviennent ; soit une representation comme je cherche a faire... un couplage ensemble spatial/valeur.

En gros, imagine une image dont le support est a geometrie quelconque... bande diagonale, cercle, des taches, etc.
Le rectangle convient... je met des "0" partout mais si j'ai des taches ou autres... c'est pas top...

En fait,un autre idee pourrait etre de decomposer l'ensemble en sous ensemble compact... mais ca demande un super traitement!!!

Mais seule alternative est donc de construire une classe vraiment specialise puisque personne ne donne de bonnes astuces.

Pour l'instant ca veut dire vector de coordonnee et vector de valeur trie en parallele. J'ai l'avantage de l'optimisation de vector et de gerer en consequence mon tableau. Mais ca reste lourd!
J'ai donc concu en attendant mieux une fonction de recherche specifique par saut pour rechercher dans un tableau de coordonnee (j'evite la recherche par < ou > de vector et gagne bcp de temps si c'est pas trop troue...ce qui sense etre mon cas).

Pour comprendre le lien avec cette fonction qui n'est valable que pour un tableau de valeur (pour le moment et pas encore de Coordonnee), il faut savoir que je compte faire un tableau de Coordonnee (une struct x,y en somme) et trier ce tableau en fonction de x puis y...
JE cherche actuellement a rendre plus generique cette fonction et qu'elle me permette de naviguer reellement. [ mais faire un algo de recherche 2D, c'est casse-tete tout de meme....mais ca reste faisable]

Bon si qq1 a une autre idee... et aussi un truc tout fait... je suis preneur!

[yan]

En gros, imagine une image dont le support est a géométrie quelconque... bande diagonale, cercle, des taches, etc.
Le rectangle convient... je met des "0" partout mais si j'ai des taches ou autres... c'est pas top...

je ne voit pas pourquoi?
Au pire tu peut faire des sous ensemble de rectangle pour chaque tache (c'est comme faire des bouding box)

Mais seule alternative est donc de construire une classe vraiment specialise puisque personne ne donne de bonnes astuces.

Ce ton avis. Parcourir un rectangle sous forme de tableau 1D est trés rapide. Je ne sais pas si tu va y gagner tans que ça en faisant une class spéciale, avec tout les test qui va avec.

Tes taches ont des particularité spécifique? genre elles sont quelconque, toujours convex, ...
Tu pourrai aussi faire un vecteur (dirigé sur un axe comme les y par exemple) de segment. Ou ton segment défini le point de départ sur l'autre axe, la taille et possède les élément que tu utilise. Les trous serait introduit par une valeur spéciale de ton élément.

[DEVfan]

oui effectivement, j'y avais pense mais les "taches" ne seront pas rectangulaires. C'est pas trop grave si la forme est proche, mais pour une diagonale, c'est pire (imagine une diagonale de 10000 case...ca fait bcp de memoire perdue).

Pour la particularite... oui quelconque et statistiquement sans doute assez compact localement.

Le vecteur, c'est pas idiot. J'avais effectivement un peu oublie cette possibilite. Je suis par contre pas sur de comprendre "d'un axe a un autre".
Mais effivement, je pourrais faire :
[mode faux code ON]
Matrice ou Vecteur diag => struct (coordonnee depart, coordonnee arrivee) pour definir par bloc de rectangle
ou
Vecteur (lin)=> struct (point depart, point arrivee) pour definir par bloc de ligne

puis
Vector<Vecteur> ou Vector <Matrice>...avec methode de tri par Top,Left probablement.

Cela me donne l'idee que ca existe deja... si qq1 trouve de quoi il s'agit... je suis toujours preneur. (ca doit simplement etre une architecture vectorielle mais ou est la bibliotheque?)
RQ : la diagonale est toujours perdante mais on ne fait que doubler la memoire (10000*2*2 (=taille diag*case*taillecoord) est bien mieux que 10000*10000*2 ). Un rectangle peut devenir 2*2 (vecteur diag) ou n*2*2 (vecteur lin)

Par contre, ca me donne pas envie de faire un tableau tout simple de data a cote, je vais sans doute les regrouper aussi avec la meme forme! Creer une struct(Vecteur, data) est impossible dans ce cas mais struct (vecteur, vector<data> ) peut-etre.
Remarque, si je compare 2 blocs et que seule une partie est commune... ca veut dire rouvrir la boite mais c'est sans doute le prix du compromis et il ne me parai pas eleve ) )

Merci pour ton idee (meme si j'ai du la modifier... en fait, j'suis pas sur d'avoir tout compris mais ca m'a fait imaginer ca).
Je vais m'amuser pour faire les regroupements : et oui, y aura une interface graphique de dessin donc je pourrais sans doute utiliser les regions de Qt!!




RQ (encore une) : cela va demander de decomposer des objets non triviaux (genre cercle) en plusieurs rectangles ou lignes. Si dans le cas des lignes, c'est simple, le cas de la decomposition en rectangle est fractale. Si je ne trouve pas de bibliotheque toute faite, cette problematique me fera sans doute choisir un decoupage en ligne (un peu moins performant pour du 2D bien sur).

[yan]

c'est l'algo du K mean que tu veut implémenter?

Je suis par contre pas sur de comprendre "d'un axe a un autre".

Si dans le premier tu utilise y, dans l'autre tu utilise x.

Par contre, ca me donne pas envie de faire un tableau tout simple de data a cote, je vais sans doute les regrouper aussi avec la meme forme! Creer une struct(Vecteur, data) est impossible dans ce cas mais struct (vecteur, vector<data> ) peut-etre.

Un truc qui pourrai être bien serait de séparer les elements et la forme de tes tâche. C'est a dire :
- utiliser un vecteur qui contient tout les éléments d'une tache
- avoir des class forme (ligne,rectangle, cercle, quelconques,... ) ,qui représenteront les forme de tes taches et donnera un accé spacial aux element.

les avantage sont :
- tableau 1D pour des traitements sur les éléments
- abstraction de la forme et des donnés
- tu as en mémoire que ce que tu as besoin
- des lib pour les forme doivent déjà exister, avec tout plein de fonction que tu aura besoin pour tes traitement sur les forme

Je vais m'amuser pour faire les regroupements : et oui, y aura une interface graphique de dessin donc je pourrais sans doute utiliser les regions de Qt!!

Attention ( au cas ou). Ne mélange pas tes traitements avec l'interface!!!, sinon tu va te casser les doigts.
C'est un peut comme mélanger le blanc et couleur dans une machine a laver

[DEVfan]

Merci pour le nom, je connaissais pas, ca peut etre interessant mais je crois pas que ce soit la meme chose. Pour la decomposition en rectangle (je pense que c'est a ca que tu faisais allusion), je pensais plutot fractal normal : http://local.wasp.uwa.edu.au/~pbourk...tals/apollony/ pour un exemple de decomposition de triangle en cercle... Bon c'est pas super utile comme ca en info


Pour le coup des axes... tu peux developper stp? a part un vector<vector< axe,data> > je comprends pas.

Separer les elements de la forme... ben oui et non :

LE bien : separation forme/contenu ; regroupement d'objet tout fait en lib
LE ni oui ni non : faire un vecteur de ligne permet de representer n'importe quoi et c'est independant de la forme.
LE pas bien : tu decris comment les formes quelconque? Ca prends plus ou moins de place? Faire une operation sur deux cercles de taille differentes et de centre different... ca me parait chaud meme si j'ai des fonctions qui me cache comment on accede aux donnees. JE pense qu'on perd la rapidite du tableau 1D.

Pour la gestion interface/ traitement... ouais c'est vrai. Il me faut donc un couche intermediaire de transfert interface/ interface... et ca par contre, je peux utiliser les proprietes des Qregions (enfin, oui, c'est un artifice).
Interface graphique, dessin canvas // bascule en objet compact //bascule dans ma classe comme y faut (je sais pas tout de suite mais il faudra )

[yan]

Dans un premier temps, c'est pas trés gentil d'avoir piqué le thread de quelqu'un d'autre
es qu'un moderateur pourrai deplacer cette discution dans un autre thread?
Ce sera mieux pour le problème de deubelte et de DEVfan

Pour la décomposition en rectangle (je pense que c'est a ca que tu faisais allusion),

euh... non

Pour le coup des axes... tu peux developper stp? a part un vector<vector< axe,data> > je comprends pas.

c'etait une façon de représente tes tache.
1 - Tu utilise un vecteur qui correspondra à l'axe Y(par exemple ). Il aura donc la taille du nombre de donné de la tache suivant Y
2 - dans ce vecteur tu y stocke des segments . Ce segments contient le début et la fin et les valeur suivant l'axe X (dans notre cas).

Separer les elements de la forme... ben oui et non :

LE ni oui ni non : faire un vecteur de ligne permet de representer n'importe quoi et c'est independant de la forme.

Je dirait plustôt oui : reutilisabilité, deparation des problème, plus facile a maintenir ...

LE pas bien : tu decris comment les formes quelconque?

par le contour par exemple.

Ca prends plus ou moins de place? Faire une operation sur deux cercles de taille differentes et de centre different... ca me parait chaud meme si j'ai des fonctions qui me cache comment on accede aux donnees. JE pense qu'on perd la rapidite du tableau 1D.

Comment peut tu perdre la rapidité du tableau 1D? si la forme et les éléments sont separé?
Pour accéder aux donnés, tu peut aisaiment utiliser un ensemble d'indice lié a ta forme pour accéder à la donné que tu veut.
Par exemple :
rectangle N*M : vect[x*N+y]

[DEVfan]

Pour le detournement de topic... le titre est pas trop loin et apres 10 jours sur un tableau sans reponse...

Pour les axes... ok, en fait c'est un peu un tab** ameliore. Si je resume :
(xdebut,xfin)<-(yi)<-(ydebut-yfin)= 1Compact. Pas mal pour le stockage Et pour l'acces, on y va en 2 temps rapide et on peut savoir si (X,Y) appartient rapidement. En fait, c'est ce que j'avais propose au debut en condense grace au vectoriel, donc SUPER, MERCI, ca me fait deja une solution facile et efficace!!
Le seul defaut est qu'on priviligie un axe... donc pour stocker une colone, c'est pas gagnant mais c'est deja bcp mieux.

Pour l'autre solution... je suis d'accord tant que ca reste des objets reconnus (rectangle, cercle, etc) mais pour les objets quelconques, la fonction d'acces... ben elle existe pas (et je risque d'utiliser bcp de shape quelconque). L'alternative a mon avis serait de decouper les objets inconnus en elements simples (du cubisme ? ) mais ca fait un pre-traitement et du coup, ca me refroidit!


Bon et promis, je vais aussi regarder Boost.MultiIndex ou std::set <std::set <T> > pour la prochaine fois.

[yan]

Pour le detournement de topic... le titre est pas trop loin et apres 10 jours sur un tableau sans reponse...

Pour les axes... ok, en fait c'est un peu un tab** ameliore. Si je resume :
(xdebut,xfin)<-(yi)<-(ydebut-yfin)= 1Compact. Pas mal pour le stockage Et pour l'acces, on y va en 2 temps rapide et on peut savoir si (X,Y) appartient rapidement. En fait, c'est ce que j'avais propose au debut en condense grace au vectoriel, donc SUPER, MERCI, ca me fait deja une solution facile et efficace!!
Le seul defaut est qu'on priviligie un axe... donc pour stocker une colone, c'est pas gagnant mais c'est deja bcp mieux.

Pour l'autre solution... je suis d'accord tant que ca reste des objets reconnus (rectangle, cercle, etc) mais pour les objets quelconques, la fonction d'acces... ben elle existe pas (et je risque d'utiliser bcp de shape quelconque). L'alternative a mon avis serait de decouper les objets inconnus en elements simples (du cubisme ? ) mais ca fait un pre-traitement et du coup, ca me refroidit!


Bon et promis, je vais aussi regarder Boost.MultiIndex ou std::set <std::set <T> > pour la prochaine fois.

C'est cool, t'as compris mon histoire des axe . Mais tu faire aussi une class qui va privilégier soit un axe, soit l'autre.

Pour les objet quelconque, tu pourrai faire les contour pour la forme et mon histoire de segment pour les index. Mais cherche, il existe sûrement des lib qui sont spécialisé dans la 2D avec les test que tu as besoin . T'aura ainsi tout ta partie forme et il te restera plus que l'autre

[DEVfan]

J'avoue que j'ai deja cherche ca hier mais je tombe souvent sur openGl et compagnie et tout ce que je trouve c'est des bibliotheques photos (enfin image rectangle) ou des bibliotheques materielles.
C'est pour ca que l'une de mes alternatives est d'utiliser la QRegion de Qt... mais comment l'exploiter pour mon application, la est la question.
Mais si tu cherches une lib, bonne chance. Bon, j'ai peut-etre pas tape les bons mots clef

Un peu de news sur le set, c'est une recherche de complexite log par clef. Je devrais donc etre tout de meme gagnant avec les compact .

Pour la selectivite de l'axe, on pourrait imaginer faire une fonction de seuil simple X//Y pour le determiner... faut que je regarde si ca peut valoir vraiment le coup.

[yan]

J'avoue que j'ai deja cherche ca hier mais je tombe souvent sur openGl et compagnie et tout ce que je trouve c'est des bibliotheques photos (enfin image rectangle) ou des bibliotheques materielles.
C'est pour ca que l'une de mes alternatives est d'utiliser la QRegion de Qt... mais comment l'exploiter pour mon application, la est la question.
Mais si tu cherches une lib, bonne chance. Bon, j'ai peut-etre pas tape les bons mots clef

http://www.applelinks.com/index.php/...y_library_110/
Mais pourquoi pas Qt. Il fait d'autre chose que des ihm. Le seul problème est que si tu utilise Qt pour cela aussi, ton projet aura du mal à s'en débarrasser si il faut une.Sauf si tu encapsule bien tout cela et que l'utilisation de Qt (ou autre lib) soit transparent au interface de tes sources. I.e. : les .h n'ont aucune connaissant de la lib utilisé pour faire gérer tes formes

[yan]

y as http://www.cgal.org/ aussi peut être. Y as une partie qui est open source

[DEVfan]

La premiere n'est effectivement opensource... et en plus ya pas grand chose. Par contre la deuxieme me plait beaucoup. Je ne sais pas si je vais m'en servir pour ce projet mais sur un autre, c'est sur!!!

En attendant, si l'enregistrement par ligne semble me suffir pour l'instant, j'ai trouve comment creer les classes correspondantes et les algorythmes.

Premierement, on avait pris des patatoides et du coup, un vector de segment suffisait... mais j'ai pris une fiure quelconque (qui ressemble un peu a @ ) et la... bah ca marche plus... c'est plus un vector<segment > qu'il faut mais un vector<vector<segment> ...

Apres reflection et pour que le rectangle reste tout de meme un objet simple a memoriser... j'arrive a ca :

[mode faux code ON ]
class segment = {int debut, int fin}
class lignage (ou Trame ou pointille, etc.) = {segment axeoff, vector<segment> Lgn}
class compact = {vector<lignage>} qui pourrait aussi devenir {bool mainaxe, vector,lignage} si on veut autoriser un choix d'axe principal X ou Y...

Du coup ca fait qu'on decoupe les figure en partant du point le plus haut (si axe Y et le plus a gauche si axe X). On enregistre les segments a partir de ce point du haut vers le bas.
Si l'objet possede plusieurs zones masquees (oui ca fait un peu comme une ombre en fait), ca redonne un point haut et on recommence, c'est un nouveau lignage.

J'ai fait une image pour comprendre mais j'ai oublie ma clef donc je la transmettrais pas avant lundi... je pense.
Mais pour ceux qui veulent s'avancer, un V sera decoupe suivant l'axe Y en deux lignages (\ puis / en gros ) et un < ou > en un seul. Un tore donnera aussi 2 lignages et un arobase... 4 (voir 5...ca depend de la numerisation de la courbe).

Ensuite, si deux compact sont groupes... genre l'un qui remplit un bout de trou de l'autre, il faut modifer les lignages sinon ce sera plus coherent. Si cela parait effrayant en fait, c'est super simple... bon je ferais le code avec du commentaire.