はじめMath! Javaでコンピュータ数学

第76回 計算量の数学 計算量と実際のコード その2

この記事を読むのに必要な時間:およそ 1 分

問題 ハッシュサーチのプログラムを作りましょう。

前回までに利用したのと同じ整数の配列をハッシュサーチで検索するプログラムを作ってください。Java言語には,ハッシュ関数を利用したHashtableというデータ構造が用意されていますので,それを利用しましょう。

前回までと同様,検索実行時間を計測し,リニアサーチやバイナリサーチの場合と比較してください。

これまでの検索では「求める整数値が配列の何番目に格納されているか」というように検索しました。今回の問題では,配列の添え字がハッシュテーブルの返値で,配列に格納される整数値がハッシュテーブルの検索のキーとなります。Hashtableクラスを利用しますから,以上のことに注意をしてプログラムを作成してください。

解説

問題 ハッシュサーチのプログラムを作りましょう。

それでは以下にハッシュサーチのコードを示します。お手元の環境での実行時間を計測してみてください。

それにしても,Java言語には便利な道具が数多く用意されていますね。有り難いことです。

ソースコード:HashSearch.java

01:import java.util.Hashtable;
02:
03:public class HashSearch {
04:
05:  public static int exec(Hashtable vals, int target) {
06:    if (vals.containsKey(target)) {
07:      return (Integer) vals.get(target);
08:    } else {
09:      return -1;
10:    }
11:  }// end of exec
12:
13:  public static void main(String[] args) {
14:    int len = 100000;
15:    int[] data;
16:    data = new int[len];
17:    for(int i=0; i<len; ++i) data[i]=i;
18:    Hashtable <Integer, Integer>hasharray = new Hashtable<Integer, Integer>();
19:    for (int i=0; i<data.length; ++i){
20:      hasharray.put(data[i],i);
21:    }
22:    int result;
23:    int repeat = 10000;
24:    long time;
25:    time = System.currentTimeMillis();
26:    for (int i=0; i<repeat; ++i){
27:      HashSearch.exec(hasharray,3);
28:      HashSearch.exec(hasharray,27);
29:      HashSearch.exec(hasharray,(int)(len/2));
30:      HashSearch.exec(hasharray,(int)(len*2));
31:   }
32:   time = System.currentTimeMillis() - time;
33:   System.out.println(time + "[msec]passed.");
34:  }// end of main
35:
36:
37:  private static void resultPrint(int result){
38:   if (result != -1) {
39:     System.out.println("[ Found ] index key = " + result);
40:   } else {
41:     System.out.println("[Not Found]");
42:   }
43:  }// end of resultPrint
44:
45:}// end of HashSearch

プログラムを実行してみると,私の環境では94ミリ秒で検索が終了しました。リニアサーチに比べると,約50倍高速です。しかし,バイナリサーチに比べるとずいぶん遅いですね。

先だって紹介した,ハッシュ値を計算するコードや,ハッシュを利用したデータ構造にアクセスする,という部分のコードが,バイナリサーチの実際のコードよりもコンピュータにとっては大きな負担になっているのです。もっともっとデータの配列が大きくなれば,ハッシュを利用するメリットがバイナリサーチの場合よりも大きくなるでしょう。少なくとも今回の程度であれば,まだバイナリサーチの方が有利なのですね。

整数の偶奇判定,ある数が偶数か奇数か判定することは,O (1)の代表的な例で,実際これは高速です。計算量が同じオーダーであっても,どのような演算を1回,あるいは一定回数と数えるかで,実際にコンピュータで実行した場合にかかる時間はずいぶんと違うものなのです。

ちょっと実験 データが極端に少ない場合

さて,ここでちょっと実験です。ちょっと疑り深くなってみましょう。現実はいつも理論通りにはならないものです。条件を変えてプログラムを実行してみましょう。

実験
ソースコードLinearSearch.javaの10行目,int len = 100000;int len = 10; に変えて実行してみてください。同様に,BinarySearch.javaとHashSearch.javaの同じ部分も同様に変更して実行し,実行時間を比較してみてください。

検索対象となるデータの個数を,10万個から10個に変更してみます。検索対象の個数が極端に少ないと,アルゴリズムによる総検索時間の差はどう変化するのでしょうか。

ちょっと実験の結果

皆さんの実行環境に大きく依存しますので,必ずこうなるとは断言できませんが,実行時間は次のような大小関係になったのではないでしょうか。

LinearSearch.java < BinarySearch.java < HashSearch.java

私の環境では,上記のように計算量の値の大小とは逆の順になりました。

処理対象となるデータの量が少ないと,検索に要する時間よりもJava言語が裏で働いている時間の方が多くなってしまうからです。リニアサーチでは2つの数値が一致するかどうかの比較を行うだけですが,バイナリサーチでは中央値を求める処理と値の比較,ハッシュサーチはハッシュ値の計算をします。データの数が極端に少ないと,データの比較に要する時間に対して,検索を効率よく行おうとするため工夫を凝らした部分のコードの実行時間の割合が大きくなってしまったのです。

実際のプログラミングでは,このようなことも意識しておかないと,小さな計算量のアルゴリズムを採用しても,実際の実行時間は長くなってしまった,なんていう見立て違いをしてしまう,という事になる良い例です。

今回はここまで

O (1)となるハッシュサーチを紹介しました。また,少し突っ込んで,計算量の値と実際のコードの実行時間の違いについて,少しだけ詳しく見てみました。

次回は,これまでに紹介できなかった計算量になる代表的なケースをコード例とともに紹介します。お楽しみに。

今回のまとめ

  • O (1)のハッシュサーチを紹介し,プログラムを作成・実行しました。
  • O (1)のアルゴリズムが常に最速とは限りません。

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。