Entry

プログラミング・メモ - ハッシュ関数の性能メモ

2007年09月25日

ちょっと野暮用でシンボルテーブル用のハッシュ関数を作ってみたんですけれど,実際どんな具合に入っているのかよく分かっていないので,実験実験。参考にしたハッシュ関数は,ドラゴン本(下記〈2〉を参照)にそれっぽく書いてあった方法です(今手元に無いんですけど)。

コンパイラ―原理・技法・ツール〈1〉 (Information & Computing)
A. V. エイホ R. セシィ J. D. ウルマン 原田 賢一
サイエンス社 (1990/10)
売り上げランキング: 81180
おすすめ度の平均: 5.0
5 コンパイラ作成者のバイブル
5 AHO本が安心
5 難しいけど、IT技術者を語るなら、読んでおくべき一冊かも。

こちらで紹介されているハッシュ関数は以下のようなもの。

  1. 文字列の1文字目と100に最も近い素数を掛け合わせる。
  2. 文字列の2文字目と200に最も近い素数を掛け合わせる。
  3. 上の要領で素数を大きくしつつ各文字に重み付けしていく。
  4. 全部掛け合わせたら,それぞれを合計する。
  5. 4の値についてテーブルサイズで mod を取る。この値がハッシュ値。

掛け合わせる素数が大きくなると,当然桁あふれすることもあるわけですけど,お構いなしに(あふれた上位桁は捨てて)計算するそうです。なお,この方法は,完全ハッシュを求めるもんじゃなくて,決められた大きさのハッシュテーブルに,なるべく均等にデータを分散させるのが目的になっています(チェイン法で格納するからカブっても問題ない)。

今回は,素数のスタートを2から始めることにして,0x100ごとの素数を用意することにしました。こっちの方が,素数テーブルの大きさの具合がいいもんですから。

そういうわけで,とりあえず,ハッシュ関数とその統計を取るプログラムを作ってみる……。なんだか無用にグルグル回すところが多くて,みっともないんですが。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLESIZE 0x10000
#define BUFSIZE 256

unsigned short PRIME_TABLE[] = {
    0x0002, 0x0101, 0x0209, 0x0301, 0x0407, 0x0503, 0x0607, 0x0709,
    0x0805, 0x0905, 0x0A13, 0x0B03, 0x0C07, 0x0D01, 0x0E09, 0x0F07,
    0x1003, 0x1105, 0x120D, 0x1307, 0x141B, 0x1505, 0x1607, 0x1709,
    0x1807, 0x1915, 0x1A03, 0x1B05, 0x1C09, 0x1D09, 0x1E01, 0x1F01,
    0x2011, 0x210D, 0x2203, 0x2303, 0x2405, 0x2501, 0x2605, 0x2717,
    0x2803, 0x2903, 0x2A01, 0x2B13, 0x2C09, 0x2D07, 0x2E01, 0x2F05,
    0x3001, 0x3103, 0x3209, 0x3307, 0x3401, 0x3509, 0x3605, 0x3701,
    0x3805, 0x3901, 0x3A03, 0x3B03, 0x3C01, 0x3D03, 0x3E05, 0x3F0B,
    0x401B, 0x4109, 0x4205, 0x4307, 0x4409, 0x4505, 0x4601, 0x4705,
    0x4801, 0x4903, 0x4A03, 0x4B07, 0x4C01, 0x4D05, 0x4E05, 0x4F07,
    0x5003, 0x5107, 0x5209, 0x5315, 0x540D, 0x5507, 0x560B, 0x5701,
    0x5803, 0x5903, 0x5A01, 0x5B01, 0x5C05, 0x5D05, 0x5E07, 0x5F09,
    0x6011, 0x6109, 0x6209, 0x6305, 0x6401, 0x650B, 0x6601, 0x6703,
    0x6803, 0x6901, 0x6A07, 0x6B05, 0x6C05, 0x6D0D, 0x6E03, 0x6F0D,
    0x700F, 0x7105, 0x7207, 0x7303, 0x7415, 0x7507, 0x7603, 0x7703,
    0x7807, 0x7901, 0x7A05, 0x7B01, 0x7C07, 0x7D03, 0x7E01, 0x7F13,
    0x8003, 0x8105, 0x8207, 0x830B, 0x8405, 0x8509, 0x8609, 0x8717,
    0x8803, 0x8909, 0x8A0B, 0x8B07, 0x8C0B, 0x8D01, 0x8E01, 0x8F15,
    0x9007, 0x9103, 0x9203, 0x9301, 0x9401, 0x9505, 0x961F, 0x970D,
    0x9805, 0x990D, 0x9A0F, 0x9B17, 0x9C01, 0x9D01, 0x9E0B, 0x9F05,
    0xA001, 0xA105, 0xA207, 0xA301, 0xA40F, 0xA511, 0xA603, 0xA70F,
    0xA805, 0xA907, 0xAA15, 0xAB01, 0xAC09, 0xAD05, 0xAE05, 0xAF09,
    0xB005, 0xB105, 0xB201, 0xB303, 0xB40B, 0xB501, 0xB609, 0xB705,
    0xB807, 0xB903, 0xBA07, 0xBB09, 0xBC03, 0xBD0D, 0xBE07, 0xBF0B,
    0xC005, 0xC101, 0xC203, 0xC301, 0xC401, 0xC509, 0xC613, 0xC707,
    0xC803, 0xC905, 0xCA01, 0xCB03, 0xCC0D, 0xCD09, 0xCE0B, 0xCF07,
    0xD013, 0xD103, 0xD20D, 0xD315, 0xD405, 0xD50B, 0xD603, 0xD709,
    0xD811, 0xD91B, 0xDA05, 0xDB11, 0xDC0D, 0xDD0F, 0xDE0B, 0xDF01,
    0xE003, 0xE101, 0xE203, 0xE311, 0xE401, 0xE507, 0xE609, 0xE705,
    0xE801, 0xE903, 0xEA11, 0xEB01, 0xEC0B, 0xED07, 0xEE09, 0xEF1B,
    0xF001, 0xF107, 0xF209, 0xF305, 0xF403, 0xF503, 0xF605, 0xF709,
    0xF805, 0xF911, 0xFA07, 0xFB0F, 0xFC01, 0xFD0D, 0xFE03, 0xFF07
};

unsigned short
hash(const char *symbol)
{
    size_t i;
    size_t cnt;
    size_t len = strlen(symbol);
    unsigned long cal = 0;

    for (i = 0, cnt = 0; i < len; i++, cnt++) {
        cal += symbol[i] * PRIME_TABLE[cnt];
        if (cnt + 1 == (sizeof(PRIME_TABLE) / sizeof(short))) {
            cnt = 0;
        }
    }

    return (short)(cal % (long)(TABLESIZE));
}

int
main(int argc, char *argv[])
{
    int i;
    int max;
    unsigned char buf[BUFSIZE];
    unsigned short table[TABLESIZE];
    unsigned short *hist;
    unsigned short hash_key;
    double average;

    bzero(buf, sizeof(char) * BUFSIZE);
    bzero(table, sizeof(short) * TABLESIZE);

    while (fgets(buf, BUFSIZE, stdin) != NULL) {
        hash_key = hash(buf);
        table[hash_key] += 1;
    }
    max = 0;
    for (i = 0; i < TABLESIZE; i++) {
        max = (table[i] > max) ? table[i] : max;
    }

    if ((hist = (unsigned short *)malloc(sizeof(short) * (max + 1))) == NULL) {
        fprintf(stderr, "memory allocation error.\n");
        exit(-1);
    }

    bzero(hist, sizeof(unsigned short) * (max + 1));
    for (i = 0; i < TABLESIZE; i++) {
        *(hist + table[i]) += 1;
    }

    average = 0;
    for (i = 0; i < max + 1; i++) {
        printf("%d\t: %d (%lg %%)\n",
               i,
               *(hist + i),
               (double) *(hist + i) / TABLESIZE * 100);
        average += i * (double) *(hist + i) / TABLESIZE;
    }
    printf("MAX  : %d\n", max);
    printf("AVE  : %lg\n", average);

    free(hist);

    return 0;
}

今回は,ハッシュテーブルの大きさを 0x10000 としてみました。ハッシュテーブルは,もちろん大きい方が重複も少なくなる可能性があります。160bit あれば SHA1 のハッシュ値をそのまま使えますしね。けど,ここでは現実的に考えて,16bitくらいあれば十分じゃないかなー……と,適当に決めました。

一方,使ったサンプルは SKK-JISYO.L の見出し語にしました。日本語が入ってるんですけど,重複しないシンボルのサンプルがあればいいので,これはこれでオッケーとします。以下のように加工して,1行に1つのシンボルが現れるファイルを作ります。

aian:~ % awk '$1 ~ /^[^;#>]/ { print $1 }' < SKK-JISYO.L > dict.txt

現在のところ dict.txt には,173167個のエントリがありました。16進数で表現すると0x2A46F個なので,16bitのハッシュテーブルには収まりません。0xFFFFのハッシュテーブルには平均して,2.6423187個の重複があるはずです。ということは,ハッシュテーブルのそれぞれのバケットに,2個か3個くらいの重複でまんべんなく収まっているのが理想,ということになります。

で,上記プログラムの実行結果。

aian:~ % ./hash < dict.txt 
0       : 4927 (7.51801 %)
1       : 12436 (18.9758 %)
2       : 16041 (24.4766 %)
3       : 14179 (21.6354 %)
4       : 9328 (14.2334 %)
5       : 4964 (7.57446 %)
6       : 2282 (3.48206 %)
7       : 913 (1.39313 %)
8       : 345 (0.526428 %)
9       : 86 (0.131226 %)
10      : 26 (0.0396729 %)
11      : 7 (0.0106812 %)
12      : 0 (0 %)
13      : 2 (0.00305176 %)
MAX  : 13
AVE  : 2.64232

読み方は,一番左がカブっている個数(重複度)で,コロンで分けたその隣りが,同じ重複度のバケット数を表しています(括弧の数(%)はハッシュテーブル全体に占める割合)。例えば,重複度1の行でみると,1つだけデータが入っているバケットが全部で12436個あって,それはハッシュテーブル全体の18.9758%に当たる,と読みます。MAX の行は,最も重複しているバケットで,AVE は重複度の平均(期待値)。

期待値の結果を見ると,2.64232となっています。先程計算したハッシュテーブルに対する重複度の平均は,2.6423187でしたから,かなりいい成績。てか,こういうもんなのか?こういうもんですね。

あとは分散(「まんべんなく」の部分)との関係が問題になるんでしょうか。よく使うシンボルが,MAX である13のバケットに入っちゃってたら,せっかく期待値が2.6前後でも,そのプログラムにおける平均の探索回数は大きくなってしまいます。また,ハンガリアン記法のように,シンボルの命名規則がかなり縛られている場合は,偏りが出るかもしれません。ここでの例では最大 O(13) の探索ということになっているけれど,これがイケてるのかどうか……どんなもんなんでしょ(←まだあまり分かってない)。

ちなみに,重み付けを行わないで単純に文字列の各文字を足し合わせて,テーブルサイズで mod を取った場合は,以下のようになりました。

0	: 61704 (94.1528 %)
1	: 543 (0.828552 %)
2	: 284 (0.43335 %)
3	: 189 (0.288391 %)
4	: 139 (0.212097 %)
5	: 112 (0.170898 %)
6	: 83 (0.126648 %)
7	: 90 (0.137329 %)
8	: 89 (0.135803 %)
9	: 70 (0.106812 %)
10	: 53 (0.0808716 %)
11	: 60 (0.0915527 %)
12	: 53 (0.0808716 %)
13	: 42 (0.0640869 %)
14	: 37 (0.0564575 %)
15	: 37 (0.0564575 %)
16	: 37 (0.0564575 %)
17	: 31 (0.0473022 %)
18	: 24 (0.0366211 %)
19	: 28 (0.0427246 %)
20	: 29 (0.0442505 %)
21	: 24 (0.0366211 %)
22	: 38 (0.0579834 %)
23	: 28 (0.0427246 %)
24	: 10 (0.0152588 %)
25	: 18 (0.0274658 %)
26	: 18 (0.0274658 %)
27	: 20 (0.0305176 %)
28	: 25 (0.038147 %)
29	: 23 (0.0350952 %)
30	: 22 (0.0335693 %)
31	: 16 (0.0244141 %)
32	: 19 (0.0289917 %)
33	: 18 (0.0274658 %)
34	: 15 (0.0228882 %)
35	: 27 (0.0411987 %)
36	: 13 (0.0198364 %)
37	: 14 (0.0213623 %)
38	: 22 (0.0335693 %)
39	: 17 (0.0259399 %)
40	: 16 (0.0244141 %)
41	: 22 (0.0335693 %)
42	: 17 (0.0259399 %)
43	: 21 (0.0320435 %)
44	: 16 (0.0244141 %)
45	: 17 (0.0259399 %)
46	: 11 (0.0167847 %)
47	: 8 (0.012207 %)
48	: 16 (0.0244141 %)
49	: 7 (0.0106812 %)
50	: 17 (0.0259399 %)
51	: 16 (0.0244141 %)
52	: 14 (0.0213623 %)
53	: 15 (0.0228882 %)
54	: 15 (0.0228882 %)
55	: 12 (0.0183105 %)
56	: 10 (0.0152588 %)
57	: 12 (0.0183105 %)
58	: 8 (0.012207 %)
59	: 16 (0.0244141 %)
60	: 16 (0.0244141 %)
61	: 14 (0.0213623 %)
62	: 12 (0.0183105 %)
63	: 14 (0.0213623 %)
64	: 12 (0.0183105 %)
65	: 11 (0.0167847 %)
66	: 12 (0.0183105 %)
67	: 7 (0.0106812 %)
68	: 14 (0.0213623 %)
69	: 11 (0.0167847 %)
70	: 5 (0.00762939 %)
71	: 11 (0.0167847 %)
72	: 14 (0.0213623 %)
73	: 11 (0.0167847 %)
74	: 12 (0.0183105 %)
75	: 11 (0.0167847 %)
76	: 8 (0.012207 %)
77	: 15 (0.0228882 %)
78	: 8 (0.012207 %)
79	: 16 (0.0244141 %)
80	: 12 (0.0183105 %)
81	: 10 (0.0152588 %)
82	: 15 (0.0228882 %)
83	: 13 (0.0198364 %)
84	: 6 (0.00915527 %)
85	: 5 (0.00762939 %)
86	: 6 (0.00915527 %)
87	: 5 (0.00762939 %)
88	: 4 (0.00610352 %)
89	: 8 (0.012207 %)
90	: 13 (0.0198364 %)
91	: 9 (0.0137329 %)
92	: 8 (0.012207 %)
93	: 9 (0.0137329 %)
94	: 9 (0.0137329 %)
95	: 7 (0.0106812 %)
96	: 9 (0.0137329 %)
97	: 7 (0.0106812 %)
98	: 8 (0.012207 %)
99	: 7 (0.0106812 %)
100	: 6 (0.00915527 %)
101	: 5 (0.00762939 %)
102	: 6 (0.00915527 %)
103	: 9 (0.0137329 %)
104	: 7 (0.0106812 %)
105	: 15 (0.0228882 %)
106	: 6 (0.00915527 %)
107	: 6 (0.00915527 %)
108	: 2 (0.00305176 %)
109	: 9 (0.0137329 %)
110	: 15 (0.0228882 %)
111	: 7 (0.0106812 %)
112	: 7 (0.0106812 %)
113	: 10 (0.0152588 %)
114	: 12 (0.0183105 %)
115	: 5 (0.00762939 %)
116	: 16 (0.0244141 %)
117	: 10 (0.0152588 %)
118	: 11 (0.0167847 %)
119	: 9 (0.0137329 %)
120	: 10 (0.0152588 %)
121	: 16 (0.0244141 %)
122	: 6 (0.00915527 %)
123	: 13 (0.0198364 %)
124	: 8 (0.012207 %)
125	: 11 (0.0167847 %)
126	: 7 (0.0106812 %)
127	: 12 (0.0183105 %)
128	: 15 (0.0228882 %)
129	: 15 (0.0228882 %)
130	: 7 (0.0106812 %)
131	: 12 (0.0183105 %)
132	: 9 (0.0137329 %)
133	: 11 (0.0167847 %)
134	: 11 (0.0167847 %)
135	: 9 (0.0137329 %)
136	: 11 (0.0167847 %)
137	: 14 (0.0213623 %)
138	: 9 (0.0137329 %)
139	: 15 (0.0228882 %)
140	: 5 (0.00762939 %)
141	: 8 (0.012207 %)
142	: 9 (0.0137329 %)
143	: 9 (0.0137329 %)
144	: 13 (0.0198364 %)
145	: 7 (0.0106812 %)
146	: 7 (0.0106812 %)
147	: 6 (0.00915527 %)
148	: 10 (0.0152588 %)
149	: 4 (0.00610352 %)
150	: 10 (0.0152588 %)
151	: 8 (0.012207 %)
152	: 8 (0.012207 %)
153	: 10 (0.0152588 %)
154	: 8 (0.012207 %)
155	: 11 (0.0167847 %)
156	: 8 (0.012207 %)
157	: 8 (0.012207 %)
158	: 5 (0.00762939 %)
159	: 8 (0.012207 %)
160	: 6 (0.00915527 %)
161	: 6 (0.00915527 %)
162	: 4 (0.00610352 %)
163	: 5 (0.00762939 %)
164	: 6 (0.00915527 %)
165	: 7 (0.0106812 %)
166	: 3 (0.00457764 %)
167	: 2 (0.00305176 %)
168	: 2 (0.00305176 %)
169	: 4 (0.00610352 %)
170	: 1 (0.00152588 %)
171	: 5 (0.00762939 %)
172	: 2 (0.00305176 %)
173	: 1 (0.00152588 %)
174	: 3 (0.00457764 %)
175	: 3 (0.00457764 %)
176	: 2 (0.00305176 %)
177	: 2 (0.00305176 %)
178	: 4 (0.00610352 %)
179	: 3 (0.00457764 %)
180	: 2 (0.00305176 %)
181	: 3 (0.00457764 %)
182	: 1 (0.00152588 %)
183	: 4 (0.00610352 %)
184	: 1 (0.00152588 %)
185	: 1 (0.00152588 %)
186	: 5 (0.00762939 %)
187	: 3 (0.00457764 %)
188	: 1 (0.00152588 %)
189	: 1 (0.00152588 %)
190	: 0 (0 %)
191	: 0 (0 %)
192	: 0 (0 %)
193	: 1 (0.00152588 %)
194	: 0 (0 %)
195	: 0 (0 %)
196	: 0 (0 %)
197	: 0 (0 %)
198	: 0 (0 %)
199	: 0 (0 %)
200	: 0 (0 %)
201	: 0 (0 %)
202	: 2 (0.00305176 %)
203	: 0 (0 %)
204	: 0 (0 %)
205	: 1 (0.00152588 %)
206	: 1 (0.00152588 %)
207	: 4 (0.00610352 %)
208	: 1 (0.00152588 %)
209	: 2 (0.00305176 %)
210	: 1 (0.00152588 %)
211	: 1 (0.00152588 %)
212	: 3 (0.00457764 %)
213	: 1 (0.00152588 %)
214	: 4 (0.00610352 %)
215	: 0 (0 %)
216	: 2 (0.00305176 %)
217	: 1 (0.00152588 %)
218	: 2 (0.00305176 %)
219	: 1 (0.00152588 %)
220	: 1 (0.00152588 %)
221	: 3 (0.00457764 %)
222	: 2 (0.00305176 %)
223	: 4 (0.00610352 %)
224	: 2 (0.00305176 %)
225	: 2 (0.00305176 %)
226	: 1 (0.00152588 %)
227	: 0 (0 %)
228	: 1 (0.00152588 %)
229	: 0 (0 %)
230	: 2 (0.00305176 %)
231	: 0 (0 %)
232	: 2 (0.00305176 %)
233	: 2 (0.00305176 %)
234	: 0 (0 %)
235	: 2 (0.00305176 %)
236	: 2 (0.00305176 %)
237	: 0 (0 %)
238	: 0 (0 %)
239	: 1 (0.00152588 %)
240	: 1 (0.00152588 %)
241	: 1 (0.00152588 %)
242	: 0 (0 %)
243	: 1 (0.00152588 %)
244	: 2 (0.00305176 %)
245	: 1 (0.00152588 %)
246	: 3 (0.00457764 %)
247	: 3 (0.00457764 %)
248	: 0 (0 %)
249	: 2 (0.00305176 %)
250	: 1 (0.00152588 %)
251	: 1 (0.00152588 %)
252	: 0 (0 %)
253	: 0 (0 %)
254	: 2 (0.00305176 %)
255	: 0 (0 %)
256	: 0 (0 %)
257	: 1 (0.00152588 %)
258	: 1 (0.00152588 %)
259	: 0 (0 %)
260	: 0 (0 %)
261	: 1 (0.00152588 %)
MAX  : 261
AVE  : 2.64232

期待値は同じだけれど(あたりまえですね),分散がえらいことに……。てか,使われないバケットが多すぎる。単純に mod を取るよりは,素数テーブルを使った方が良い成績になるようです。最大 O(261) の可能性があるハッシュを使うようだったら,二分探索木を検討するのもいいのかも。

そういえば,ドラゴン本では,素数に0x0002を使わなかったけれども,これは文字コードと素数が重複しないように値を取ったのかもしれません(少しカブるんですけど)。そうだとすると,7bit JIS 以外の日本語をシンボルに使う場合は,100から始めても成績が悪くなりそうな予感。ほんの少しのことなんでしょうけど。

ちょっと面白いので,もう少し実験実験。(続くかも)

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN