Q&A
ベストアンサー
ご回答、ありがとうございます。
なるほど、なるべく衝突を避けるようm(スロット数)を大きくしていたのですが、大きい出力だとそれでは不十分そうですね。
衝突が起きるときにどうするかをもう少し考えてみます。
ハッシュテーブルを用いて英和辞典を作成するプログラムをCで書いています。
コードは以下の通りです。
C
1#include <stdio.h> 2#include <string.h> 3#include <stdlib.h> 4#include <math.h> 5 6#define NEW(p, n){p = malloc((n)*sizeof(p[0]));} 7 8typedef char* String; 9//後々使いやすくするため、ここでStringタイプを定義しちゃいます 10 11//英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア) 12typedef struct slobj_{ 13 struct slobj_* next; 14 String key; 15 String jpn; 16}* slobj; 17 18//連結リスト 19typedef struct{ 20 slobj head; 21 slobj tail; 22}* slist; 23 24typedef struct{ 25 int n; //ハッシュに格納されている要素数 26 int m; //ハッシュ表のサイズ 27 slist* T; //リストの配列 28} hash; 29 30//ハッシュ関数 31int hfunc(hash H, String key){ 32 int h=0, i=0; 33 while (key[i] != 0){ 34 h = h*101+key[i]; //ハッシュ値を計算 35 i++; 36 } 37 return abs(h) % H.m; //非負の値にして、表のサイズで割った余り 38} 39 40//文字列の長さを求める 41int string_len(String str){ 42 int len=0; 43 while(str[len]!=0){ 44 len++; 45 } 46 return len; 47} 48 49//文字列を標準入力から読む 50String string_input(void){ 51 int i, len; 52 char buf[1000]; 53 String str; 54 scanf("%999s", buf); 55 56 len = string_len(buf); 57 58 NEW(str, len+1); 59 for(i=0; i<len; i++){ 60 str[i]=buf[i]; 61 } 62 str[len] = 0; 63 return str; 64} 65 66//文字列が同じかどうかを判定する関数 67int string_compare(String p, String q){ 68 int c1, c2; 69 int i=0; 70 while(1){ 71 c1=p[i]; c2=q[i]; 72 if(c1<c2) return -1; 73 if(c1>c2) return 1; 74 if(c1==0) break; 75 i++; 76 } 77 return 0; 78} 79 80//新しい連結リストを作成 81slist slist_new(void){ 82 slist L; 83 NEW(L, 1); 84 L -> head = NULL; 85 L -> tail = NULL; 86 return L; 87} 88//新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア) 89slobj slobj_new(String x, String y){ 90 slobj p; 91 NEW(p, 1); 92 p -> key = x; 93 p -> jpn = y; 94 p -> next = NULL; 95 return p; 96} 97 98//連結リストの先頭に挿入 99void slist_insert_head(slist L, slobj p){ 100 p -> next = L -> head; 101 L -> head = p; 102} 103 104//連結リストの末尾に挿入 105void slist_insert_tail(slist L, slobj p){ 106 if(L -> head == NULL){ 107 L -> tail = p; 108 L -> head = p; 109 } 110 else if(L -> head == L -> tail){ 111 L -> tail = p; 112 L -> head -> next = p; 113 } 114 else{ 115 L -> tail -> next = p; 116 L -> tail = p; 117 } 118} 119 120//連結リストをプリント 121void slist_print(slist L) 122{ 123 slobj p; 124 p = L->head; 125 while (p != NULL){ 126 if(string_compare(p->jpn, "NO")==0){ 127 printf("%s\n", p->jpn); 128 } 129 else{ 130 printf("%s %s\n", p -> key, p -> jpn); 131 } 132 p = p-> next; 133 } 134} 135 136//表のサイズがmのハッシュ表を作る 137hash hash_new(int m){ 138 hash H; 139 int i; 140 NEW(H.T, m); 141 H.m = m; 142 for(i=0; i<= m-1; i++){ 143 H.T[i]=slist_new(); 144 } 145 return H; 146} 147 148//キーがkeyである要素を返す 149slobj hash_search(hash H, String key){ 150 int h=hfunc(H, key); 151 return H.T[h]->head; 152} 153 154void hash_insert(hash H, slobj obj){ 155 int h=hfunc(H, obj->key); 156 slist_insert_tail(H.T[h], obj); 157} 158 159void slist_free(slist L){ 160 slobj p, q, r; 161 p = L->head; 162 q = p->next; 163 while (q != NULL){ 164 r = q; 165 q = q-> next; 166 free(p); 167 p = r; 168 } 169 free(p); 170 free(L); 171} 172 173void hash_free(hash H){ 174 int i; 175 for(i = 0; i <= H.m-1; i++){ 176 if(H.T[i] -> head != NULL){ 177 slist_free(H.T[i]); 178 } 179 } 180 free(H.T); 181} 182 183int main(){ 184 int i, j, k, n; 185 String eng, jpn, s; 186 double v; 187 slobj p, r; 188 hash H; 189 slist L=slist_new(); //ここに出力する実数を格納していく 190 int m=81239; //数千から数万程度の素数がいいらしい 191 //ここから英和辞典を作成します。 192 scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数 193 H=hash_new(m); 194 H.n = n; 195 //英語日本語ペアを順次入れていく 196 for(i=1; i<=n; i++){ 197 eng=string_input(); 198 jpn=string_input(); 199 p=slobj_new(eng, jpn); 200 hash_insert(H, p); 201 } 202 //ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します 203 scanf("%d", &k);//以後の問い合わせの数 204 for(j=1; j<=k; j++){ 205 s=string_input(); 206 r=hash_search(H, s); 207 if(r==NULL){ 208 r=slobj_new(NULL, "NO"); 209 } 210 slist_insert_tail(L, r); 211 } 212 slist_print(L); 213 slist_free(L); 214 hash_free(H); 215 return 0; 216}
こちらのコードだと、例えば
4 coffee コーヒー milk 牛乳 water 水 milkcoffee ミルクコーヒー 5 mizu milk coffe milkcoffee sake
のような比較的小さめなインプットだと正しい結果が出るのですが、それに対して
1021 hq め meayl かヨはみカヘ cvscxggb まねとそカらほ fnf ンホろトこ jprep うかフハホ vy ンてうすぬのて cqpev ム ffmznim テヲちりロちコ (中略) 992 jdysejw hit gqlakd xxy dburfwkbk xwpw aucltz (中略)
のような長いインプットだと、間違ったkeyに対応する見出しが何個か出力されてしまい、正しく動作しないようです。
自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、mの値を数万程度ではなく数百万程度の素数に変えるなどをしてみました。しかし、mにどのような値を入れてもうまくいきません。
どこを改良するべきか、アドバイスいただけるでしょうか。宜しくお願いします。
編集：
衝突が起きる場合を想定して書き直しましたが、今度は同じスロットの要素を出力するときにおかしくなります。
C
1#include <stdio.h> 2#include <string.h> 3#include <stdlib.h> 4#include <math.h> 5 6#define NEW(p, n){p = malloc((n)*sizeof(p[0]));} 7 8typedef char* String; 9//後々使いやすくするため、ここでStringタイプを定義しちゃいます 10 11//英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア) 12typedef struct slobj_{ 13 struct slobj_* next; 14 String key; 15 String jpn; 16}* slobj; 17 18//連結リスト 19typedef struct{ 20 slobj head; 21 slobj tail; 22}* slist; 23 24typedef struct{ 25 int n; //ハッシュに格納されている要素数 26 int m; //ハッシュ表のサイズ 27 slist* T; //リストの配列 28} hash; 29 30ハッシュ関数 31int hfunc(hash H, String key){ 32 int h=0, i=0; 33 while (key[i] != 0){ 34 h = h*3659+key[i]; //ハッシュ値を計算 35 i++; 36 } 37 return abs(h) % H.m; //非負の値にして、表のサイズで割った余り 38 //return 1; //ハッシュ関数が全て同じ値を出す場合で実験してみました。 39} 40 41//文字列の長さを求める 42int string_len(String str){ 43 int len=0; 44 while(str[len]!=0){ 45 len++; 46 } 47 return len; 48} 49 50//文字列を標準入力から読む 51String string_input(void){ 52 int i, len; 53 char buf[1000]; 54 String str; 55 scanf("%999s", buf); 56 57 len = string_len(buf); 58 59 NEW(str, len+1); 60 for(i=0; i<len; i++){ 61 str[i]=buf[i]; 62 } 63 str[len] = 0; 64 return str; 65} 66 67//文字列が同じかどうかを判定する関数 68int string_compare(String p, String q){ 69 int c1, c2; 70 int i=0; 71 while(1){ 72 c1=p[i]; c2=q[i]; 73 if(c1<c2) return -1; 74 if(c1>c2) return 1; 75 if(c1==0) break; 76 i++; 77 } 78 return 0; 79} 80 81//新しい連結リストを作成 82slist slist_new(void){ 83 slist L; 84 NEW(L, 1); 85 L -> head = NULL; 86 L -> tail = NULL; 87 return L; 88} 89 90//新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア) 91slobj slobj_new(String x, String y){ 92 slobj p; 93 NEW(p, 1); 94 p -> key = x; 95 p -> jpn = y; 96 p -> next = NULL; 97 return p; 98} 99 100//連結リストの先頭に挿入 101void slist_insert_head(slist L, slobj p){ 102 p -> next = L -> head; 103 L -> head = p; 104} 105 106//連結リストの末尾に挿入 107void slist_insert_tail(slist L, slobj p){ 108 if(L -> head == NULL){ 109 L -> tail = p; 110 L -> head = p; 111 } 112 else if(L -> head == L -> tail){ 113 L -> tail = p; 114 L -> head -> next = p; 115 } 116 else{ 117 L -> tail -> next = p; 118 L -> tail = p; 119 } 120} 121 122//連結リストをプリント 123void slist_print(slist L) 124{ 125 slobj p; 126 p = L->head; 127 while (p != NULL){ 128 if(string_compare(p->jpn, "NO")==0){ 129 printf("%s\n", p->jpn); 130 } 131 else{ 132 printf("%s %s\n", p -> key, p -> jpn); 133 } 134 p = p-> next; 135 } 136} 137 138//表のサイズがmのハッシュ表を作る 139hash hash_new(int m){ 140 hash H; 141 int i; 142 NEW(H.T, m); 143 H.m = m; 144 for(i=0; i<= m-1; i++){ 145 H.T[i]=slist_new(); 146 } 147 return H; 148} 149 150//キーがkeyである要素を返す 151slobj hash_search(hash H, String key){ 152 slobj p; 153 int h=hfunc(H, key); 154 p = H.T[h]->head; 155 while(p!=NULL){ 156 if(string_compare(p->key, key)==0){ //keyと一致するような要素を同じスロットにあるリストから探索していきます 157 return p; 158 } 159 p = p->next; 160 } 161 return p; 162} 163 164//ハッシュに入力する関数。同じスロットにハッシュされたすべての要素が連結リストに格納されるようにします。 165void hash_insert(hash H, slobj obj){ 166 int h=hfunc(H, obj->key); 167 slist_insert_head(H.T[h], obj); 168} 169 170void slist_free(slist L){ 171 slobj p, q, r; 172 p = L->head; 173 q = p->next; 174 while (q != NULL){ 175 r = q; 176 q = q-> next; 177 free(p); 178 p = r; 179 } 180 free(p); 181 free(L); 182} 183 184void hash_free(hash H){ 185 int i; 186 for(i = 0; i <= H.m-1; i++){ 187 if(H.T[i] -> head != NULL){ 188 slist_free(H.T[i]); 189 } 190 } 191 free(H.T); 192} 193 194int main(){ 195 int i, j, k, n; 196 String eng, jpn, s; 197 double v; 198 slobj p, r; 199 hash H; 200 slist L=slist_new(); //ここに出力する実数を格納していく 201 int m=81239; //数千から数万程度の素数がいいらしい 202//ここから英和辞典を作成します。 203 scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数 204 H=hash_new(m); 205 H.n = n; 206//英語日本語ペアを順次入れていく 207 for(i=1; i<=n; i++){ 208 eng=string_input(); 209 jpn=string_input(); 210 p=slobj_new(eng, jpn); 211 hash_insert(H, p); 212 } 213//ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します 214 scanf("%d", &k);//以後の問い合わせの数 215 for(j=1; j<=k; j++){ 216 s=string_input(); 217 r=hash_search(H, s); 218 if(r==NULL){ 219 r=slobj_new(NULL, "NO"); 220 } 221 slist_insert_tail(L, r); 222 } 223 slist_print(L); 224 //slist_free(L); 225 //hash_free(H); 226 return 0; 227}
例えば、ハッシュ関数が常に1を出力するよう変更し、
3 coffee コーヒー milk 牛乳 water 水 2 milk coffee
という入力にした場合、
milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー ・ ・ ・
が延々と続いてしまうのです！！！！！
編集2:
ごめんなさい、よく考えたらr=hash_search(H, s);→slist_insert_tail(L, r);のときは次のリストの要素を指すポインタもそのままコピーされるのですから、そりゃ無限ループになりますよね、、、
もう少し考えます
回答2件
0
if(r==NULL){ r=slobj_new(NULL, "NO"); } else{ r=slobj_new(r -> key, r -> jpn); } slist_insert_tail(L, r);
に変えたらうまくいきました。
asmさん、ありがとうございます。
投稿2020/05/18 02:22
総合スコア17
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。