Discussion :

[Grasshoper]

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 :

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

[Mat.M]

bonjour simple question : une simple std::multimap peut suffire ?
Pour ce qui est de la fonction pas certain d'avoir tout pigé ; en général les foncteurs pour les templates s'occupent d'insérer, de trier des éléments, de les comparer.

je recommenderais de faire simple dans la création de structures et de classes car les conteneurs et les templates ça risque d'être coûteux en temps d'exécution pour effectuer des tris des manipulations dessus

[Grasshoper]

merci pour ce retour, std::multimap à l'air bien et si la recherche est moins couteuse qu'un unordered_set alors c'est tout à fait ce qu'il me faudrait.
Il est à noter que dans mon cas je ne garde qu'une seule key par noeud, c'est à dire que je stocke juste l'information de savoir si ce noeud appartient aux noeuds visités (ou s'il n'y est pas c'est qu'on ne l'a pas encore découvert), et donc pas combien de fois on l'a visité.

Qu'elle est la meilleure stratégie (en terme de temps de recherche) pour comparer si un noeud [i,j] est présent dans la multimap ? Comparer les 2 éléments [i,j] pour chaque paire testée?

Merci