全部の単語を検索する時間を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