Discussion :

[Seabirds]

Salut à toutes et à tous!

J'ai souvent le problème de devoir mapper un ensemble discret X vers les entiers naturels N grâce une relation d'ordre, pour pouvoir utiliser des structures qui fonctionnent avec des indices (matrices, vecteurs etc).

Par exemple quand je calcule des distances élément par élément d'un ensemble X, j'ai envie de stocker ces valeurs dans une matrice que je planque derrière une petite classe PairwiseMatrix, ce qui revient à devoir attribuer un indice (un peu arbitraire) à chaque élément de X. Si j'ai envie d'accéder plus tard à la distance entre deux éléments a et b de X, je dois retrouver les indices correspondants avec une code du genre:

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
 
class PairwiseMatrix {
 
  // Constructeur pour calculer f(a,b) pour tout couple a,b appartenant à X^2
  // Les indices sont donnés par l'ordre des points dans le vecteur p
  Pariwise(std::vector<T> const& p, F f):
  m_points(p),
  m_matrix(construct_matrix(p, f))
  {}
 
unsigned int ID(T const& x) const {
    auto it = std::find(m_points.begin(), m_points.end(), x); // m_points conserve l'ordre des éléments donné à la construction avec un std::vector
    assert( it != m_points.end());
    return std::distance(m_points.begin(), it);
  }
 
  auto operator()(T const& x, T const& y) const {
    return m_matrix(ID(x),ID(y));
  }
 
}

Si c'est limité à une seule classe, ça va. Le truc c'est que ce genre de code pour switcher entre X et N commence à se retrouve partout dans le projet. C'est normal/préoccupant/lourd ?

J'hésite à ordonner le vecteur d'éléments de X une bonne fois pour toute dès le début du code, et ne concevoir le reste de la bibliothèque que pour des éléments de type intégral.

Ca revient à buter pas mal de boulot (à la qualité discutable, comme vous le voyez).

Que me conseillez-vous, et comment vous y prenez vous habituellement ?

Merci

[koala01]

Salut,

La première question que j'aurais envie de te poser, c'est : ta matrice sera-t-elle a priori constante (ou rarement mise à jour) ou sera-t-elle au contraire régulièrement mise à jour

Note que je pourrais poser la question différemment : sachant que ce que tu "gagnes" d'un coté, tu le "perds" forcément de l'autre (tu ne pourras réellement gagner du temps sur la recherche d'un élément que si tu "perds un peu de temps" sur la mise à jour, et vice versa), sur quel aspect préfères tu "perdre du temps" pour gagner du temps sur l'autre aspect

Car, a priori, tout partira de ce choix "cornélien" :

Si tu fais une mise à jour de temps en temps (fut-elle "complète" ou non), tu préférera que la recherche se fasse rapidement, quitte à "perdre un maximum de temps" lors de la mise à jour.

A l'inverse, si tu fais de nombreuses mises à jour de ta matrices pour très peux de recherches, tu préféreras sans doute que la recherche soit "(très) lente", mais que la mise à jour soit "la plus rapide possible".

Et, forcément, les structures et les algorithmes que tu pourras mettre en place refléteront clairement ce "choix de base".

Je ne crois pas qu'il soit possible de te conseiller tant que tu n'auras pas clairement établi tes priorités à ce niveau là ... même sije peux aussi me tromper sur ce coup

[Pyramidev]

Salut,

Si tu as seulement besoin de numéroter tes points de manière arbitraire et que tu veux éviter que la recherche du numéro d'un point soit coûteuse, alors il suffit de travailler directement avec un type qui contient à la fois un point et son numéro sur place :

Code :

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

1
2
3
4
5
6
7
8
9
10
class PointWithId {
public:
	...
	Point  getPoint() const { return m_point; }
	size_t getId()    const { return m_id; }
	...
private:
	Point  m_point;
	size_t m_id;
};

Ainsi, quand tu veux récupérer la distance entre deux points via ta matrice des distances, il te suffit d'appeler getId() sur tes deux points puis de récupérer la distance correspondante à cette paire de numéros.

Si de plus tes points sont ordonnés dans un vecteur qui ne change pas alors, pour t'assurer que les numéros de tes points soient cohérents, tu pourrais remplacer m_id par la position du point dans le vecteur :

Code :

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

1
2
3
4
5
6
7
8
9
10
class PointWithId {
public:
	// ...
	Point  getPoint() const { return m_vector[m_index]; }
	size_t getId()    const { return m_index; }
	// ...
private:
	std::vector<Point> const& m_vector;
	size_t                    m_index;
};

Mais ce n'est qu'un détail d'implémentation. Je pense que le code qui gère la matrice des distances ne devrait pas dépendre du fait que les points soient stockés dans un vecteur. Tout ce que ce code devrait savoir, c'est que les numéros de tes points vont de 0 à la taille de la matrice moins un.

Voici un bout de code plus complet :

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <algorithm>
#include <cassert>
#include <vector>
 
class Point {
public:
	Point(double x, double y) :
		m_x{x}, m_y{y}
	{}
 
	double getX() const { return m_x; }
	double getY() const { return m_y; }
 
	bool operator==(Point const& other) const {
		return m_x == other.m_x && m_y == other.m_y;
	}
	bool operator!=(Point const& other) const {
		return !(*this == other);
	}
 
private:
	double m_x;
	double m_y;
};
 
size_t getIndexOfPointInVector(Point const& p, std::vector<Point> const& vect) {
	auto it = std::find(vect.begin(), vect.end(), p);
	assert(it != vect.end());
	return std::distance(vect.begin(), it);
}
 
class PointWithId {
public:
	PointWithId(std::vector<Point> const& vect, size_t index) :
		m_vector{vect}, m_index{index}
	{}
	PointWithId(std::vector<Point> const& vect, Point const& p) :
		m_vector{vect}, m_index{getIndexOfPointInVector(p, vect)}
	{}
 
	Point  getPoint() const { return m_vector[m_index]; }
	size_t getId()    const { return m_index; }
	double getX()     const { return getPoint().getX(); }
	double getY()     const { return getPoint().getY(); }
 
	bool operator==(PointWithId const& other) const {
		return getPoint() == other.getPoint();
	}
	bool operator!=(PointWithId const& other) const {
		return !(*this == other);
	}
 
private:
	std::vector<Point> const& m_vector;
	size_t                    m_index;
};

Remarque : l'interface de PointWithId est volontairement proche de celle de Point afin que l'on puisse facilement changer le code en remplaçant des Point par des PointWithId.

[Seabirds]

Encore une fois, merci à vous deux pour vos réponses toujours aussi pertinentes

Salut,
La première question que j'aurais envie de te poser, c'est : ta matrice sera-t-elle a priori constante (ou rarement mise à jour) ou sera-t-elle au contraire régulièrement mise à jour

Ca dépend.

-- La matrice des distances est construite une seule fois.
-- On rentre ensuite dans une grosse boucle de simulation (environ 10^6 reps)
----La matrice est copiée et une transformation est appliquée à chacun des termes
----Ensuite il y a deux grosses stratégies:
------ option A: Les nouveaux coefficients sont soit transmis à des distributions discrètes de la STL pour pouvoir échantillonner un point d'arrivée conditionnellement à un point de départ
------ option B: Les termes de la matrice sont utilisés pour multiplier un vecteur de valeurs

Salut,
Et, forcément, les structures et les algorithmes que tu pourras mettre en place refléteront clairement ce "choix de base".
Je ne crois pas qu'il soit possible de te conseiller tant que tu n'auras pas clairement établi tes priorités à ce niveau là

Moui c'est en général à ce moment que je viens papoter ici: quand c'est le bazar dans mes priorités ahaha ! C'est plus clair maintenant merci

Pyramidev, je crois que c'est effectivement quelque chose du genre dont j'avais besoin... J'avais bien pensé à "externaliser" le vecteur, mais pas comme ça. Ca a effectivement l'air beaucoup plus léger, tu relègues tout ce qui concerne l'indiçage à cette petite classe PointWithID waaaah