Quel est le conteneur approprié ?

Salut,

Je cherche à représenter des données de type ts_info (structure) relatives à la combinaison de 2 objets que j'identifie par des indices i et j appartenant à 0..n (unsigned int).

Chose importante : la combinaison de i et j est la même que celle de j et i.

Mon but est bien sûr d'accéder le plus vite possible à la donnée ts_info connaissant i et j.

Quel conteneur dois-je choisir ?

Merci

n est fixe au moment de la compilation ou bien il est renseigné par un autre morceau de code ?

Salut.
Avec le peut que tu nous dit, je dirait une
std::map<std::pair<int,int>, ts_info>,
Où std::pair<int,int> est ta combinaison i,j.
A voir s'il ne faudrait pas que tu ajoute un prédicat pour le test < sur les pair.
Ou peut être
std::map<int, ts_info>, avec int = i*j

Que vaut n?

Citation:

---

Envoyé par Mongaulois

Salut.
Avec le peut que tu nous dit, je dirait une
std::map<std::pair<int,int>, ts_info>,
Où std::pair<int,int> est ta combinaison i,j.
A voir s'il ne faudrait pas que tu ajoute un prédicat pour le test < sur les pair.
Ou peut être
std::map<int, ts_info>, avec int = i*j

Que vaut n?

---

Le n est indéterminé au moment de la compilation...mais ça ne devrait pas poser de problème avec les possibilités d'allocation dynamique offertes par le C++.

Je n'aime pas trop le map<pair<int, int>, ts_info> car une paire de i,j n'est pa la même chose qu'une paire de j,i , ça voudrait dire qu'il faut que je me force à n'utiliser que des paires où j > i par exemple et ensuite quand je demande le résultat pour i,j créer la paire dans le bon ordre.

J'aime assez l'dée du i*j sauf que 5*6 = 10*3 donc il n'y a pas unicité de la clé dans la table de clés/valeurs.

Il doit y voir quelque chose de mieux à faire...

Citation:

---

Envoyé par tnarol

Je n'aime pas trop le map<pair<int, int>, ts_info> car une paire de i,j n'est pa la même chose qu'une paire de j,i , ça voudrait dire qu'il faut que je me force à n'utiliser que des paires où j > i par exemple et ensuite quand je demande le résultat pour i,j créer la paire dans le bon ordre.

---

Tu peut ajouter un prédicat a ta map pour faire ca ;)

Citation:

---

J'aime assez l'dée du i*j sauf que 5*6 = 10*3 donc il n'y a pas unicité de la clé dans la table de clés/valeurs.

---

Je savais bien qu'il y avait un truc qui cloche :aie:

n est de quel ordre?

Citation:

---

Envoyé par Mongaulois

Tu peut ajouter un prédicat a ta map pour faire ca ;)

n est de quel ordre?

---

n est de l'ordre de quelques centaines.
pour le prédiicat je ne connais pas du tout tu peux me donner un exemple ?

Citation:

---

Envoyé par tnarol

n est de l'ordre de quelques centaines.
pour le prédiicat je ne connais pas du tout tu peux me donner un exemple ?

---

un truc comme

Code:

---

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

strut myPredicat { bool operator() (const pair<int, int> & P1, const pair<int, int> & P2) { //tu met ton test qui correspondra à l'operatur P1 < P2 // Je n'ai pas testé, mais ca devrait ressembler à ca int min1 = std::min(P1.first,P1.second); int min2 = std::min(P2.first,P2.second);   int max1 = std::max(P1.first,P1.second); int max2 = std::max(P2.first,P2.second);   return min1<min2 && max1<max2; } }

---

et ta map

Code:

---

map<pair<int, int>, ts_info,myPredicat>

---

Je te conseil ce tuto
http://r0d.developpez.com/articles/algos-stl/
ce n'est pas tout à fait le même problème mais ca t'apprendra pas mal de chose sur l'utilisation de la STL

Citation:

---

Envoyé par tnarol

J'aime assez l'dée du i*j sauf que 5*6 = 10*3 donc il n'y a pas unicité de la clé dans la table de clés/valeurs.

---

min(i, j)*n + max(i,j)

Mais ça revient à peu près au même que d'avoir une paire en clef, dont on aurait trié les valeurs.

Citation:

---

Envoyé par tnarol

Je cherche à représenter des données de type ts_info (structure) relatives à la combinaison de 2 objets que j'identifie par des indices i et j appartenant à 0..n (unsigned int).

Chose importante : la combinaison de i et j est la même que celle de j et i.

Mon but est bien sûr d'accéder le plus vite possible à la donnée ts_info connaissant i et j.

Quel conteneur dois-je choisir ?

---

Est-ce que toutes les combinaisons (i,j) correspondent à un ts_info, ou seulement quelques unes?

(Accessoirement : pourquoi utiliser des unsigned int?)

Apparemment, un couple (i,j) équivaut au couple (j,i).
De plus, un tel couple correspond à un et un seul ts_info ("bijection" => il n'y a que 2 couples pour un ts_info, donc ce n'est pas vraiment une bijection, mais si on raisonne en ensembles {i,j} on a bien une bijection).

Citation:

---

Envoyé par Alp

Apparemment, un couple (i,j) équivaut au couple (j,i).
De plus, un tel couple correspond à un et un seul ts_info ("bijection" => il n'y a que 2 couples pour un ts_info, donc ce n'est pas vraiment une bijection, mais si on raisonne en ensembles {i,j} on a bien une bijection).

---

Pour répondre aux questions précédentes :

- tous les couples i, j ont un ts_info associé
- les couples i,j et j,i ont le même ts_info

Finalement j'ai choisi une méthode un peu bourrine qui consiste à créer dynamiquement un tableau à 2 dimensions de pointeurs de ts_info (créé dynamiquement aussi) soit un " ts_info*** " . Pour éviter de me poser la question de l'ordre je copie simplement le même pointeur dans la case i,j et la case j,i.

Mais si vous avez plus simple je prends.

Citation:

---

Envoyé par tnarol

Mais si vous avez plus simple je prends.

---

Ben tu en as eux au moins deux

Citation:

---

Envoyé par Mongaulois

Ben tu en as eux au moins deux

---

Oui mais les deux impliquent un test de supériorité effectué au moment de l'appel qui potentiellement dégrade les performances (critère important pour moi) par rapport à la solution que j'ai employée.

Citation:

---

Envoyé par tnarol

Oui mais les deux impliquent un test de supériorité effectué au moment de l'appel qui potentiellement dégrade les performances (critère important pour moi) par rapport à la solution que j'ai employée.

---

Par rapport à trois indirections?

Citation:

---

Envoyé par corrector

Par rapport à trois indirections?

---

Oui. Est ce que je me trompe ? J'imaginais que d'aller taper une adresse mémoire (accès à temps fixe) demandais moins d'opérations élémentaires que de faire 2 comparaisons plus l'accès proprement dit à une clé du conteneur (accès en log de la taille) sans compter tout l'enrobage qu'il peut y avoir quand on utilise une classe de conteneur.

Citation:

---

Envoyé par tnarol

Oui. Est ce que je me trompe ? J'imaginais que d'aller taper une adresse mémoire (accès à temps fixe) demandais moins d'opérations élémentaires que de faire 2 comparaisons plus l'accès proprement dit à une clé du conteneur (accès en log de la taille) sans compter tout l'enrobage qu'il peut y avoir quand on utilise une classe de conteneur.

---

Perso,
je pense que la méthode de JolyLoic avec une map (voir un vector si N n'est pas trop grand ou si tu utilise toutes les possibilitées i,j) sera plus rapide et moins buggé par rapport à trois indirections.
A verifier ;).

En tout cas avec un vector c'est sur (plus qu'une seul in direction)

Citation:

---

Envoyé par tnarol

Oui. Est ce que je me trompe ? J'imaginais que d'aller taper une adresse mémoire (accès à temps fixe) demandais moins d'opérations élémentaires que de faire 2 comparaisons plus l'accès proprement dit à une clé du conteneur (accès en log de la taille) sans compter tout l'enrobage qu'il peut y avoir quand on utilise une classe de conteneur.

---

Ah oui, par rapport à la map, le ts_info*** sera plus efficace. Je ne vois pas de raison d'utiliser la map de toutes façons, puisque toutes les paires (i,j) | i<j correspondent à un ts_info unique.

Le plus simple me semble de tester i<j, intervertir i et j si besoin est, et ensuite d'accèder à un vector<vector<ts_info> > (ou un ts_info** si tu préfères).

Citation:

---

Envoyé par corrector

Ah oui, par rapport à la map, le ts_info*** sera plus efficace. Je ne vois pas de raison d'utiliser la map de toutes façons, puisque toutes les paires (i,j) | i<j correspondent à un ts_info unique.

---

ca va dépendre de la taille de N. L'intérêt d'utiliser une map est si N est grand et que peut de paire i,j sont utilisé

Citation:

---

Envoyé par corrector

Le plus simple me semble de tester i<j, intervertir i et j si besoin est, et ensuite d'accèder à un vector<vector<ts_info> > (ou un ts_info** si tu préfères).

---

Pourquoi faire un vector de vector??
un simple vector<ts_info> suffit. Où l'on accède par ce que propose JolyLoic
id = min(i, j)*n + max(i,j)

Citation:

---

Envoyé par Mongaulois

ca va dépendre de la taille de N. L'intérêt d'utiliser une map est si N est grand et que peut de paire i,j sont utilisé

---

Il me semble que l'OP a indiqué que toutes les paires possibles ((i,j) | i<j) sont utilisées.

Citation:

---

Envoyé par Mongaulois

Pourquoi faire un vector de vector??
un simple vector<ts_info> suffit. Où l'on accède par ce que propose JolyLoic
id = min(i, j)*n + max(i,j)

---

Pour ne pas stocker les deux paires (i,j) et (j,i) pour n'en utiliser qu'une seule.

Citation:

---

Envoyé par corrector

Pour ne pas stocker les deux paires (i,j) et (j,i) pour n'en utiliser qu'une seule.

---

C'est le but du calcul min(i, j)*n + max(i,j)

Citation:

---

Envoyé par Mongaulois

C'est le but du calcul min(i, j)*n + max(i,j)

---

Je parle du nombre d'éléments dans le tableau :
pour (i,j) = (n-1,n-1),
min(n-1,n-1)*n + max(n-1,n-1) = (n-1)*n+n-1 = n*n-1
donc il y a n*n éléments, au lieu de (n+1)*n/2

Au fait, j'ai parlé de (i,j), i<j, ça devrait être "inférieur ou égal" je crois!

Mon hypothèse de numérotation partait sur l'idée d'une structure creuse. Si ce n'est pas le cas, on peut encore trouver des numérotations uniques, mais qui reviennent à avoir une structure en double tableau mise à plat. Genre :

Code:

---

1 2 3 4

m = min(i,j); M = max(i,j); // à calculer d'un bloc, avec une fonction genre minmax) tableau[M*(M+1)/2 + m];

---

Est-ce plus coûteux ou pas qu'une double indirection ? Je n'en sais rien, seule une mesure permettrait de trancher.

utilise un vector a une dimension. tu as n(n+1)/2 combinaisons possible (c'est la taille de ton vector).

accede a l'element (i,j) ou i>=j par : j + i(i+1)/2
accede a l'element (i,j) ou i < j par l'acces a j,i

temps constant en acces, et tu as juste l'espace suffisant.

ca fait deux fois que je ne vois pas la seconde page d'un post, ca suffit!!! grrrr :[

Citation:

---

Envoyé par screetch

ca fait deux fois que je ne vois pas la seconde page d'un post, ca suffit!!! grrrr :[

---

et en plus il y en as qu'une :aie:

ca doit dependre de tes options d'affichage :) chez moi ca fait deux pages.

hein ? hors sujet ? quissa??? non! pas moi!