Quelle structure pour stocker et chercher efficacement des points en N dimensions ?
Bonjour à toutes et à tous,
Je suis en train de coder une marche aléatoire (particulière) sur un graphe en n dimensions. Le marcheur doit se rappeler des nœuds (en n dimensions donc) qu'il a visité par le passé dans sa marche. L'idée finale est de pouvoir étudier certains comportements de cette marche sur un très (très) long terme, c'est à dire que la marcheur va visiter beaucoup beaucoup de nœuds qu'il devra garder en mémoire pour savoir s'il les a déjà visité.
Pour vous donner un ordre de grandeur, on doit pouvoir stocker 1e6 (million) ou 1e9 (milliard) de nœuds voire potentiellement plus. Mais dans un premier temps l'ordre de 1e6 peut convenir.
L'essentiel du calcul sera de savoir si, quand le marcheur arrive sur un nœud, il a déjà visité ce nœud. Il faut donc chercher dans une liste de nœuds visités potentiellement grande.
En regardant les structures de la STL (c++11) je me suis penché sur le container std::unordered_set qui me parait intéressant pour stocker des Points multidimensionnels. J'utilise une classe PointsND (proposée ici: https://stackoverflow.com/questions/...le-point-class) que j'ai un peu adaptée pour ma problématique en 2-dimensions dans un premier temps.
Code:
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class PointND
{
public:
PointND( const unsigned int dim )
{
//impossible location:
for (unsigned int i = 0; i < dim; i++)
elements_[i] = std::numeric_limits<double>::infinity();
}
//specific constructors for dimension 2:
PointND( const double x, const double y )
{
elements_[0] = x;
elements_[1] = y;
}
unsigned int n_dim() const {
return elements_.size();
}
double& operator [] ( unsigned const i )
{
return elements_[i];
}
double const& operator [] ( unsigned const i ) const
{
return elements_[i];
}
void operator += ( PointND const& other )
{
for( unsigned i = 0; i < nDimensions; ++i )
{
elements_[i] += other.elements_[i];
}
}
void operator -= ( PointND const& other )
{
for( unsigned i = 0; i < nDimensions; ++i )
{
elements_[i] -= other.elements_[i];
}
}
bool operator == ( PointND const& other )
{
for( unsigned i = 0; i < nDimensions; ++i )
if( elements_[i] != other.elements_[i] )
return false; //we found an error
return true; //otherwise return true;
}
friend PointND operator + ( PointND const& a, PointND const& b )
{
PointND ret( a );
ret += b;
return ret;
}
friend PointND operator - ( PointND const& a, PointND const& b )
{
PointND ret( a );
ret -= b;
return ret;
}
friend std::ostream &operator<<( std::ostream &out, const PointND * nd ) {
for(unsigned i = 0; i < nd->elements_.size()-1; i++)
out << nd->elements_[i] << ",";
out << nd->elements_[nd->elements_.size()-1];
return out;
}
private:
static const unsigned int nDimensions = 2; //default number of Dimensions is 2
std::array<double, nDimensions> elements_;
}; |
J'utilise donc std::unordered_set<PointND> visited. Et elements_[] contient en réalité des valeurs d'indexes d'un tableau en 2-dimensions, c'est-à-dire que je stocke des indices de noeuds (entiers, même si déclarés en double pour l'instant) [i,j] à valeurs dans -infini, +infini (même si en pratique on atteindra jamais ces infinis, on peut donc se contenter de très grandes valeurs).
Ma question est la suivante: je dois fournir une fonction de hash qui soit bien répartie sur le domaine des points en 2 dimensions. Que me suggériez vous comme fonction de hash?
Merci!
