Problème de hashage

Version imprimable

Problème de hashage

Bonjour,

J'ignore si actuellement il faut utiliser "unordered_set" ou "ext/hash_set" avec g++, j'ai essayé les deux et j'ai eu des messages d'erreurs aussi incompréhensible.

J'ai tendance à supposer que le problème est que j'ai mis ou oublier le mot clef "const" à un endroit alors qu'il n'aurait pas fallu (ou qu'il l'aurait fallu), quand j'ai redéfini les opérateur ==, () /* pour le hashage*/ ou =, et j'avoue que si quelqu'un pouvait avoir une idée de ce qui cause le bug, je lui serai très reconnaissant.

Je copie colle le code, mais vu que les messages d'erreurs arrivent sur les headers, je pense qu'il n'y aura pas grand chose à lire.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
 
 
#include <cstdio>
#include <vector>
#include <unordered_set> // ou l'autre ou les deux, au choix
#include <cmath>
using namespace __gnu_cxx;
using namespace std;
 
 
/*On suppose que n<32*/
struct graphe{
  vector<unsigned int> ligne;
 
  graphe(unsigned int n){
    ligne.reserve(n);
    for(unsigned int i=0;i<n;i++){
      ligne[i]=0;
    }
  }
 
  bool arrow(unsigned int lig, unsigned int col){
    return ligne[lig]&(1<<col);
  }
 
  void add_arrow(unsigned int lig, unsigned int col){
    ligne[lig]|=(1<<col);
    ligne[col]|=(1<<lig);
  }
 
  void remove_arrow(unsigned int lig, unsigned int col){
    ligne[lig]^=(1<<col);
    ligne[col]^=(1<<lig);
  }
 
  bool operator==( graphe g ){
    if(g.ligne.size()!=ligne.size())return false;
    for(unsigned int i=0;i<g.ligne.size();i++){
      if(g.ligne[i]!=ligne[i])return false;
    }
    return true;
  }
 
  /*bool operator==(const graphe& g1, const graphe& g2){
    if(g1.ligne.size()!=g2.ligne.size())return false;
    for(unsigned int i=0;i<g1.ligne.size();i++){
      if(g1.ligne[i]!=g2.ligne[i])return false;
    }
    return true;
  }*/
 
  size_t operator()(){
    unsigned int tot=0;
    for(unsigned int i=0;i<ligne.size();i++){
      tot*=17;
      tot+=ligne[i];
    }    
    return tot;
  }
  /*size_t operator ()(const graphe& g1){
    unsigned int tot=0;
    for(unsigned int i=0;i<g1.ligne.size();i++){
      tot*=17;
      tot+=ligne[i];
    }    
    return tot;
  }  */
 
  graphe(vector<unsigned int> chemin){
    graphe(chemin.size());
    for(unsigned int i; i<chemin.size()-1;i++){
      add_arrow(chemin[i],chemin[i+1]);
    }
  }
 
  graphe& operator=( graphe g){
    ligne.reserve(g.ligne.size());
    for(unsigned int i; i<g.ligne.size()-1;i++){
      ligne[i]=g.ligne[i];
    }
  }
 
};
 
/*struct ham{
  graphe g;
  vector<unsigned int> chemin;
 
  ham(graphe gr, vector<unsigned int> c){
    g=gr;
    chemin=c;
  }
 
  bool operator==(ham h){
    h.g==g;
    for(unsigned int i=0;i<chemin.size();i++){
      if(h.chemin[i]!=chemin[i])return false;
    }
    return true;
  }
 
  size_t operator ()(const ham& h) const{
    return g();
  }
  };*/
 
unordered_set<graphe> table;
unsigned int maxi;
 
void swap(vector<unsigned int> Value, unsigned int i, unsigned int j){
  unsigned int tmp=Value[i];
  Value[j]=Value[i];
  Value[i]=tmp;
}
 
void getNext(vector<unsigned int> Value){
  unsigned int N=Value.size();
  unsigned int i = N - 1;
  while (Value[i-1] >= Value[i]) i = i-1;
  unsigned int j = N;
  while (Value[j-1] <= Value[i-1]) j = j-1;
// swap values at positions (i-1) and (j-1)
  swap(Value,i-1, j-1);    
  i++; j = N;
  while (i < j)
  {
    swap(Value, i-1, j-1);
    i++;
    j--;
  }
}
 
pair<unsigned int,unsigned int>  N_vers_N2(unsigned int u) {
  unsigned int y=sqrt(2*u);
  if(y*(y+1)/2>u) 
    y--;
  unsigned int x =u-(y*(y+1))/2 -1;
  pair<unsigned int,unsigned int> p(x,y);
  return p;
}
 
void cree(graphe g,unsigned int ar){
  if(ar==maxi){
   table.insert(g);
  }
  pair<unsigned int,unsigned int> p=N_vers_N2(ar);
  unsigned int x=p.first, y=p.second;
  cree(g,ar+1);
  if(!g.arrow(x,y)){
    graphe g2=g;
    g2.add_arrow(x,y);
    cree(g2,ar+1);
  }
}
 
int main(){
  unsigned int n=3,fact=1;
  maxi=n*(n+1)/2;
  for(unsigned int i=2;i<=n;i++)fact*=i;
  vector<unsigned int> permut(n);
  for(unsigned int i=0;i<n;i++){
    permut[i]=i;
  }
  for(unsigned int i=0;i<fact;i++){
    getNext(permut);
    graphe g(permut);
  }
  printf("size=%i\n",table.size());
  return 0;
}

Et je vous met aussi le message d'erreur:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
 
-*- mode: compilation; default-directory: "~/hamilton/Console/" -*-
Compilation started at Sun Jan 10 01:17:41
 
g++ Ham2.cpp -W -o ham2 -std=c++0x -Wno-deprecated
In file included from /usr/include/c++/4.4/unordered_set:47,
                 from Ham2.cpp:3:
/usr/include/c++/4.4/bits/stl_function.h: In member function ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = graphe]’:
/usr/include/c++/4.4/tr1_impl/hashtable_policy.h:769:   instantiated from ‘bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, size_t, std::__detail::_Hash_node<_Value, false>*) const [with _Key = graphe, _Value = graphe, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing]’
/usr/include/c++/4.4/tr1_impl/hashtable:918:   instantiated from ‘std::__detail::_Hash_node<_Value, __cache_hash_code>* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::__detail::_Hash_node<_Value, __cache_hash_code>*, const _Key&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
/usr/include/c++/4.4/tr1_impl/hashtable:983:   instantiated from ‘std::pair<typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator, bool> std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_insert(const _Value&, std::true_type) [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
/usr/include/c++/4.4/tr1_impl/hashtable:420:   instantiated from ‘typename __gnu_cxx::__conditional_type<__unique_keys, std::pair<std::__detail::_Hashtable_iterator<_Value, __constant_iterators, __cache_hash_code>, bool>, std::__detail::_Hashtable_iterator<_Value, __constant_iterators, __cache_hash_code> >::__type std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::insert(const _Value&) [with _Key = graphe, _Value = graphe, _Allocator = std::allocator<graphe>, _ExtractKey = std::_Identity<graphe>, _Equal = std::equal_to<graphe>, _H1 = std::hash<graphe>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = true, bool __unique_keys = true]’
Ham2.cpp:142:   instantiated from here
/usr/include/c++/4.4/bits/stl_function.h:203: error: passing ‘const graphe’ as ‘this’ argument of ‘bool graphe::operator==(graphe)’ discards qualifiers
 
Compilation exited abnormally with code 1 at Sun Jan 10 01:17:41

PS: je suis bien conscient que le temps de calcul de mon algorithme est en O(n!*2^(n^2)) donc si quelqu'un cherche à comprendre ce que fait le code, il n'est pas la peine de me signaler qu'il est mauvais.

Citation:

Envoyé par Arthur Rainbow

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
  bool operator==( graphe g ){
    if(g.ligne.size()!=ligne.size())return false;
    for(unsigned int i=0;i<g.ligne.size();i++){
      if(g.ligne[i]!=ligne[i])return false;
    }
    return true;
  }
 
  /*bool operator==(const graphe& g1, const graphe& g2){
    if(g1.ligne.size()!=g2.ligne.size())return false;
    for(unsigned int i=0;i<g1.ligne.size();i++){
      if(g1.ligne[i]!=g2.ligne[i])return false;
    }
    return true;
  }*/

Ton opérateur == indique qu'il va modifier l'objet courant (this). Essaye :

Code:

1
2
3
4
5
6
7
  bool operator==( graphe g ) const {
    if(g.ligne.size()!=ligne.size())return false;
    for(unsigned int i=0;i<g.ligne.size();i++){
      if(g.ligne[i]!=ligne[i])return false;
    }
    return true;
  }

En outre, pourquoi passer l'argument par copie ? Et pourquoi avoir commenté le code en dessous qui me semblait meilleur (passage par référence constante) ?

Si je met deux arguments à == il me dit que cet opérateur n'en attend qu'un. J'en ai donc mis qu'un.

J'ai préféré laisser l'autre en commentaire si jamais je me rendais compte que ça vallait mieux de l'y laisser.

J'ai rajouté ton const, entre la parenthèse et l'accolade fermante (peut tu confirmer qu'il n'y a pas d'autre différence?)

Et maintenant j'ai le message encore moins compréhensible

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
-*- mode: compilation; default-directory: "~/hamilton/Console/" -*-
Compilation started at Sun Jan 10 01:33:55
 
g++ Ham2.cpp -W -o ham2 -std=c++0x -Wno-deprecated
/tmp/ccwBPsFK.o: In function `std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(graphe const&) const':
Ham2.cpp:(.text._ZNKSt8__detail15_Hash_code_baseI6grapheS1_St9_IdentityIS1_ESt8equal_toIS1_ESt4hashIS1_ENS_18_Mod_range_hashingENS_20_Default_ranged_hashELb0EE12_M_hash_codeERKS1_[std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(graphe const&) const]+0x2b): undefined reference to `std::hash<graphe>::operator()(graphe) const'
/tmp/ccwBPsFK.o: In function `std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node<graphe, false> const*, unsigned int) const':
Ham2.cpp:(.text._ZNKSt8__detail15_Hash_code_baseI6grapheS1_St9_IdentityIS1_ESt8equal_toIS1_ESt4hashIS1_ENS_18_Mod_range_hashingENS_20_Default_ranged_hashELb0EE15_M_bucket_indexEPKNS_10_Hash_nodeIS1_Lb0EEEj[std::__detail::_Hash_code_base<graphe, graphe, std::_Identity<graphe>, std::equal_to<graphe>, std::hash<graphe>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node<graphe, false> const*, unsigned int) const]+0x3a): undefined reference to `std::hash<graphe>::operator()(graphe) const'
collect2: ld returned 1 exit status
 
Compilation exited abnormally with code 1 at Sun Jan 10 01:33:56

et ceci même si je rajoute "const" à l'argument dans la parenthèse.

10/01/2010, 02h08
JolyLoic

Citation:

Envoyé par Arthur Rainbow

Si je met deux arguments à == il me dit que cet opérateur n'en attend qu'un. J'en ai donc mis qu'un.

Euh, oui, dans ce cas, il faut en faire une fonction libre. Regarde http://cpp.developpez.com/faq/cpp/?p...embre_ou_libre

Citation:

Envoyé par Arthur Rainbow

Et maintenant j'ai le message encore moins compréhensible

C'est mieux comme erreur. Il indique qu'il a réussi à compiler, qu'il a juste du mal à linker, on a progressé d'une étape.
Il ne trouve pas la définition de std::hash<graphe>::operator()(graphe) const... Et moi non plus. En fait, tu as défini un operateur() sur ton type, il s'attendait à trouver un opérateur() sur le type std::hash<ton type ici>. Donc soit tu spécialise le template std::hash pour ton type en particulier, soit tu indique à ta unordered_map un second argument qui est une fonction de hashage.

Citation:

Envoyé par JolyLoic

Donc soit tu spécialise le template std::hash pour ton type en particulier

J'avais cru que ça voulait dire définir une fonction
size_t std::hash<graphe>::operator()(const graphe g)
J'ai donc copier ma fonction operator() en dehors de ma structure, mais ça bug toujours.

Code:

error: too few template-parameter-lists

Qu'est-ce ce que je peux donner en plus comme paramètre à hash ?

Citation:

Envoyé par JolyLoic

, soit tu indique à ta unordered_map un second argument qui est une fonction de hashage.

Visiblement, il refuse une fonction comme deuxième argument (même précédé par & pour déréférencer)
Code:

1 2 3 error: type/value mismatch at argument 2 in template parameter list for ‘template<class _Value, class _Hash, class _Pred, class _Alloc> class std::unordered_set’ Ham2.cpp:115: error: expected a type, got ‘hash_graphe’
En tout cas merci beaucoup pour ton aide, vu que, comme tu le remarques surement, je n'ai pas trop l'habitude du C++ pour programmer(Ni pour quoi que ce soit d'autre d'ailleurs.)

Salut,
Comme l'a dit Loïc, j'ai repris ton code et j'ai rendu l'opérateur == const (l'opérateur, pas l'argument ! ) et cette partie ne génère plus d'erreur :
Code:

1 2 3 4 5 6 7 bool operator==( graphe const & g ) const{ if(g.ligne.size()!=ligne.size())return false; for(unsigned int i=0;i<g.ligne.size();i++){ if(g.ligne[i]!=ligne[i])return false; } return true; }
D'autre part, pour l'opérateur(), il doit lui aussi être const et spécialisé dans le namespace std :
Code:

1 2 3 4 5 6 7 8 9 namespace std{ template<> inline size_t hash<graphe>::operator()(graphe g) const { return g(); } }
Ne pas oublier de rendre ton operateur() de graph const aussi !
Code:

1 2 3 4 5 6 7 8 size_t operator()()const{ unsigned int tot=0; for(unsigned int i=0;i<ligne.size();i++){ tot*=17; tot+=ligne[i]; } return tot; }

10/01/2010, 13h24
JolyLoic
Citation:
Envoyé par 3DArchi

D'autre part, pour l'opérateur(), il doit lui aussi être const et spécialisé dans le namespace std :

Code:

1 2 3 4 5 6 7 8 9 namespace std{ template<> inline size_t hash<graphe>::operator()(graphe g) const { return g(); } }
Avec probablement un passage du graphe par référence constante, là aussi.

Autrement, si ça semble trop compliqué, ne pas oublier que std::map existe aussi, et ne demande pas de fonction de hashage, juste un opérateur <...
10/01/2010, 17h53
Arthur Rainbow

Merci énormément, ça compile enfin !

Par curiosité, il n'y a pas moyen de passer le graphe par référence (graphe& g) plutôt que le copier ?

Il ne me reste plus qu'à débugger, pour le moment, visiblement, je calcule 0 en temps constant, ce qui aurait été faisable avec un code plus simple.

Ce qui m'inquiète le plus c'est que je ne comprend pas ce que fait le namespace ici.

Je suis au courant de l'existance des map, mais à priori je n'ai aucune comparaison qui peuvent se faire rapidement, ça prend un temps n^2 rien que pour vérifier l'égalité. Et comme je pense avoir une table avec 2^(n^2), même sur un abr équilibré, je me retrouverai encore avec une profondeur de n^2 ce qui est assez mauvais.
11/01/2010, 12h54
3DArchi

Salut,

Citation:

Envoyé par Arthur Rainbow

Merci énormément, ça compile enfin !

Par curiosité, il n'y a pas moyen de passer le graphe par référence (graphe& g) plutôt que le copier ?

Si. C'est ce que propose Loic : le passage par référence constante (graphe const &)

Citation:

Envoyé par Arthur Rainbow

Ce qui m'inquiète le plus c'est que je ne comprend pas ce que fait le namespace ici.

La spécialisation doit se faire dans l'espace de nom std. D'où le namespace std.