「リニアサーチに番兵を付けると」をやってみた
tt4cs氏の
リニアサーチに番兵を付けると - 自明でない日記
という記事が興味深かったので、私も試してみた。
実行環境はjre1.7.0、CPUはインテルi7-2600 3.40GHz。
ソースコードは、tt4cs氏が公開されているものから、以下２点を変更・追加したものを使用した。
- tt4cs氏はサーチを1,000回ずつ繰り返していたが、私は10,000回ずつ繰り返した
- 「while文でなく、for文ならどうよ？」ということで、下記のsearch2()メソッドを追加した。
public static int search2(int[] data, int wanted) {
for (int i = 0; i < data.length; i++) {
if (data[i] == wanted)
return i;
}
return -1;
}
また、nowokay氏の指摘に従い、10回程度、仮実行してからサンプルを採った。
で、実行結果は以下のとおり。
"Index"は、サーチがヒットした要素番号を示している。
（-1は、ヒットしなかったことを示す）
| Index | search0所要時間 | search1所要時間 | search2所要時間 | |
|---|---|---|---|---|
| 1回目 | 299161 | 919 | 923 | 939 |
| 2回目 | -1 | 3042 | 3074 | 3028 |
| 3回目 | 947045 | 2886 | 2902 | 2872 |
| 4回目 | 328021 | 983 | 999 | 999 |
| 5回目 | 133257 | 405 | 406 | 406 |
| 6回目 | 919760 | 2793 | 2824 | 2794 |
| 7回目 | 211555 | 639 | 640 | 656 |
| 8回目 | -1 | 3042 | 3059 | 3043 |
| 9回目 | 111939 | 343 | 347 | 357 |
| 10回目 | -1 | 3093 | 3137 | 3071 |
| 平均 | 1814.5 | 1831.1 | 1816.5 |
私の結果ではsearch0が最も速く、ほぼ同じ記録でsearch2が続き、
search1が最も遅かった。
特に差異が顕著なのはIndexが-1のとき（サーチがヒットしなかったとき）で、
search0,search2とsearch1とで最大40msecの差が出た。
これはおそらく、IndexOutOfBoundsExceptionのインスタンス生成に
時間がかかったためと思われる。
というわけで、私の結果からは、
- while文とfor文の間に、実効性の差はほとんどない
- IndexOutOfBoundsExceptionを番兵に使用するリニアサーチは、かえって遅くなる可能性がある
ということが言えるかと思う。
