Discussion :

[tnarol]

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

[Alp]

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

[yan]

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?

[tnarol]

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

[yan]

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

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

n est de quel ordre?

[tnarol]

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 ?

[yan]

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 :

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

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 :

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

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

[JolyLoic]

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.

[corrector]

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

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

[tnarol]

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.

[yan]

Mais si vous avez plus simple je prends.

Ben tu en as eux au moins deux

[tnarol]

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.

[corrector]

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?

[tnarol]

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.

[yan]

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)

[corrector]

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

[yan]

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é

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)

[corrector]

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.

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.

[yan]

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)