全部の単語を検索する時間を1セットとして、100セットにかかる時間を平均で出します。実行セット回数10000回というのは100セットを100回計測したということです。全体の回数を増やし、さらに時間がかかる最初の100セットを余分にやらせて、その時間を計測から除いています。
ほぼ一定の所要時間が測れています。
| 単純前方探索 整列済辞書 |
二分法探索 整列済辞書 |
HashMapで探索 整列済辞書 |
HashMapで探索 非整列辞書 |
|||||
|---|---|---|---|---|---|---|---|---|
| 実行セット回数 | 全時間 | 平均(100) | 全時間 | 平均(100) | 全時間 | 平均(100) | 全時間 | 平均(100) |
| 1000 | 22028 | 2203 | 749 | 74.9 | 105 | 10.5 | 103 | 10.3 |
| 10000 | 220528 | 2205 | 7409 | 74.1 | 1025 | 10.3 | 1033 | 10.3 |
| 100000 | 2082642 | 2083 | 73962 | 74.0 | 10200 | 10.2 | 10025 | 10.0 |
| 1000000 | 729924 | 73.0 | 96156 | 9.6 | 96894 | 9.7 | ||
| 10000000 | 970677 | 9.7 | 958644 | 9.6 | ||||
使用したプログラムのソース。繰り返しのセット回数を変えるには、mainのint made=1000;の数値を変えてコンパイルする必要があります。
| JitenSet100m04.java | 単純前方探索 | ejdic2k2.txtを使って単純前方探索します |
| JitenSet100m05.java | 二分法探索 | ejdic2k2.txtを使って二分法探索します |
| JitenSet100m06.java | HashMapで探索 | ejdic2k2.txtを使ってHashMapで探索します |
| JitenSet100m07.java | HashMapで探索 | ejdic2k2nosort.txtを使ってHashMapで探索します |
| ejdic2k2.txt | 2002件の辞書データ(英単語でソート済) | プログラムと同じ場所に置くこと。 |
| ejdic2k2notsort.txt | 2002件の辞書データ(ソートしていない) | プログラムと同じ場所に置くこと。 |
上記プログラムの一部mainメソッドの繰り返しの部分のみです。(他はほぼ同等)
int made=1000; //全部の単語を検索して1kaiとしmadeの回数繰り返す
int itv1=100; //ラップタイムをとるセット回数
int itv2=1000; //ラップタイムの表示を改行するセット回数
int kai=-itv1; //最初の1セットを計測に入れないようにするため
long time0 = System.currentTimeMillis();
long timep = time0;
long timei;
while( made>kai){
for( String word : wordslist ){
//辞書を検索するのはそれぞれのアルゴリズムで解くスタティックメソッド
String imi = wordSearch(words,imis,ct,word);
//動作の確認はできているので意味は表示しない。
}
kai++;
if (kai==1) time0 = System.currentTimeMillis();
if (kai%(itv1)==0){
timei=System.currentTimeMillis();
System.out.print((timei-timep)+" ");
timep = timei;
}
if (kai%(itv2)==0) System.out.printf("\n%8d:",kai);
}
long time1 = System.currentTimeMillis();
System.out.println( (time1-time0) + "msec" );
ラップタイムを表示させています。さすがに100000を超えるとスクロールしますが、これによる速度低下はないようです。
これを記録したものが下図。1セット目は計測から外しているもの。2セット目も多少値が大きいことがありますが、平均にはさほど影響がないものです。ただ、途中明らかに速くなる境界が存在します。システムで最適化されるなど、条件が変わるのかもしれません。
| 実行セット回数 | 単純前方探索 整列済辞書 |
二分法探索 整列済辞書 |
HashMapで探索 整列済辞書 |
HashMapで探索 非整列辞書 |
|---|---|---|---|---|
| 1000 | 2223,2216,2205... | 86,89,75,75... | 26,23,12,10,10.. | 26,23,10,10,10.. |
| 10000 | 2222,2206,2204... | 92,75,75... | 25,10,10.. | 27,11,10.. |
| 100000 | 2220,2201,2199...1744 | 89,76,75... | 24,12,10.. | 23,10,11... |
| 1000000 | 2222,2204,... | 88,88,76,75,75..73 | 28,11,11... | 22,11,10... |
| 10000000 | 26,30,11,10,11,10...10 9 10 | 28,11,10... |
2199 2202 2203 2197 2198 2197 2203 2197 2201 2203
2193 2197 2195 2199 2200 2197 2199 2203 2203 2200
2203 2197 2198 2205 2199 2202 2202 2201 2200 2199
2195 2198 2194 2198 2200 2199 2200 2194 2202 2194
2199 2198 2196 2000 1743 1741 1741 1742 1742 1743
1741 1747 1740 1742 1743 1742 1742 1742 1741 1741
1743 1742 1743 1741 1743 1744 1743 1743 1743 1742
1742 1742 1742 1743 1743 1741 1743 1742 1743 17
2221
0:2309 2202 2202 2198 2201 2202 2202 2202 2203 2207
1000:2204 2213 2207 2211 2216 2213 2208 2207 2213 2213
2000:2202 2181 2174 2178 2203 2202 2203 2203 2202 2203
3000:2203 2202 2202 2201 2202 2202 2202 2201 2202 2202
4000:2203 2203 2202 2202 2216 2204 2202 2202 2202 2202
57000:2180 2199 2199 2190 2189 2177 2180 2199 2196 2198
58000:2189 2204 2202 2201 2201 2202 2201 2203 2202 2202
59000:2203 2201 2201 2201 2201 2201 2201 2201 2201 2201
60000:2202 2202 2202 2201 2202 2201 2202 2202 2202 2196
61000:2192 2187 2187 2193 2183 2183 2189 2180 2186 2194
62000:2179 2183 2201 2186 2190 2189 2184 2183 2187 2195
63000:2186 2202 2187 2191 2190 2185 2206 2202 2202 2202
64000:2202 2201 2202 2202 2202 2202 2201 2202 2202 2202
65000:2201 2202 2201 2202 2201 2202 2202 2201 1977 1740
66000:1741 1741 1740 1740 1746 1740 1741 1740 1740 1741
67000:1740 1740 1740 1740 1740 1746 1743 1740 1740 1740
68000:1741 1740 1740 1740 1741 1740 1740 1740 1741 1741
69000:1740 1741 1740 1740 1741 1740 1740 1741 1740 1741
70000:1740 1741 1740 1740 1740 1740 1740 1741 1741 1740
2223
0:2224 2198 2198 2198 2199 2202 2198 2198 2204 2199
1000:2198 2198 2200 2202 2197 2198 2198 2198 2199 2198
2000:2198 2199 2198 2199 2198 2199 2199 2198 2199 2198
3000:2198 2198 2199 2199 2198 2198 2199 2198 2198 2197
63000:2198 2199 2199 2199 2198 2198 2199 2198 2198 2198
64000:2199 2198 2199 2201 2198 2198 2198 2198 2198 2199
65000:2198 2198 2198 2198 2199 2198 2198 2198 1986 1740
66000:1740 1740 1740 1739 1740 1739 1740 1739 1740 1739
67000:1740 1739 1740 1746 1739 1740 1739 1739 1739 1739
68000:1741 1740 1739 1740 1740 1739 1740 1739 1740 1741
69000:1740 1739 1740 1740 1739 1740 1740 1743 1741 1740
70000:1740 1740 1739 1740 1739 1740 1739 1740 1741 1740
71000:1739 1739 1740 1739 1739 1740 1739 1740 1739 1740
72000:1740 1739 1740 1740 1740 1739 1740 1741 1741 1740
97000:1743 1761 1740 1740 1740 1740 1739 1740 1739 1740
98000:1740 1740 1740 1740 1739 1740 1739 1739 1739 1740
99000:1739 1739 1740 1739 1739 1739 1739 1739 1739 1739
100000:2041996msec
z3c1d@star00:~/java$
z3c1d@star00:~/java$ java JitenSet100m05
2002
2002
88
0:88 76 75 75 75 75 75 75 75 75
1000:76 75 75 74 75 75 75 74 74 75
2000:74 75 74 75 74 75 74 75 74 75
3000:74 75 74 74 75 75 74 75 74 75
4000:74 74 75 75 74 75 75 74 75 75
54000:74 74 75 74 74 75 74 75 74 74
55000:75 74 75 74 74 75 75 74 75 75
56000:74 75 74 75 74 74 75 74 74 75
57000:74 75 75 74 75 75 74 75 75 75
58000:74 75 75 74 75 74 75 75 74 75
59000:75 74 75 75 74 75 75 74 75 74
60000:75 75 74 75 75 74 75 75 75 75
61000:75 75 75 75 75 74 75 74 75 75
62000:74 76 75 74 75 74 75 75 74 75
63000:75 75 74 75 75 74 75 74 75 75
64000:75 75 75 75 75 75 74 75 75 74
65000:74 75 74 75 75 74 74 74 87 73
66000:73 73 73 72 73 73 73 72 73 73
67000:73 73 72 73 73 73 73 72 73 73
991000:73 73 72 73 73 73 73 72 73 73
992000:73 72 73 73 73 73 73 72 73 73
993000:73 73 72 73 73 73 72 73 73 73
994000:73 72 73 73 73 73 72 73 73 73
995000:73 72 73 73 73 72 73 73 73 72
996000:73 73 73 73 73 72 73 73 73 72
997000:74 73 73 73 73 73 73 73 73 73
998000:73 73 74 73 73 73 73 73 73 73
999000:73 73 73 73 74 73 73 73 73 73
1000000:729924msec
z3c1d@star00:~/java$ java JitenSet100m06
2002
2002
26
0:30 11 10 11 10 10 11 10 11 10
1000:11 10 10 11 11 10 10 11 10 10
2000:11 10 11 10 10 11 10 10 11 10
3000:10 11 10 10 10 11 10 10 11 10
4000:10 11 10 10 10 11 10 10 11 10
5000:10 11 10 10 10 11 10 10 11 10
58000:10 11 10 11 10 10 11 10 10 11
59000:10 10 11 10 10 11 10 10 11 10
60000:11 10 10 11 10 10 11 10 10 11
61000:10 10 11 10 10 10 11 10 10 11
62000:10 10 11 10 10 11 10 10 11 10
63000:10 11 10 10 11 10 10 11 10 14
64000:10 10 10 9 10 9 10 10 9 10
65000:10 9 10 9 10 10 9 10 10 9
66000:10 9 10 9 10 10 9 10 9 10
67000:10 9 10 10 9 10 9 10 10 9
68000:10 10 9 10 9 10 9 10 10 9
69000:10 9 10 10 9 10 9 10 10 9
70000:10 9 10 10 9 10 9 10 9 10
71000:10 9 10 10 9 10 9 10 10 9
9993000:10 9 10 10 10 9 10 10 9 10
9994000:10 9 10 10 10 9 10 10 10 9
9995000:10 10 10 9 10 10 10 9 10 10
9996000:9 10 10 10 9 10 10 9 10 10
9997000:10 9 10 10 10 9 10 10 10 9
9998000:10 10 9 10 10 9 10 10 10 9
9999000:10 10 9 10 10 10 9 10 10 10
10000000:970677msec