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

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

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

物事はシンプルであればあるほど記憶しやすく,組み合わせて何事かを処理するのも容易になります。アルゴリズムもシンプルであればあるほど優れていると言えます。ただ,物事をシンプルにする,とひとことで言っても,いくつかの処理のステップをまとめて1つの名前を付けること,つまり,抽象化によってシンプルにした場合には注意が必要です。抽象化してシンプルになった名前の裏では,汗水たらしててんてこ舞いして働いている人がいるかもしれませんから。営業担当者が「簡単です!うちに任してください!」といって取ってきた仕事を,製造現場の労働者が泣きの涙で作って出荷している・という笑えない状況と,どこか似ているような似ていないような。いえ,決して営業さんは悪くないんですよ。悪くないんですけど。

図76.1 笑顔の営業,涙の現場

図76.1 笑顔の営業,涙の現場

計算量:ハッシュサーチの場合O(1)

バイナリサーチは十分高速な検索アルゴリズムです。これ以上早いアルゴリズムがあるのでしょうか。結論から書くと,バイナリサーチが最速かつ適切でしょう。ただし,あらゆる場合に適切かというと,そうでもありません。

一般に検索のキーは整数ではなく文字列です。例えば住所録,商品データベースなどです。ある商品の検索を行う場合に,商品名が分かっても,商品番号が分からないのが普通です。名前を覚えずに番号で覚える奇特な人はそういません。そうした場合には,次のハッシュサーチが有望です。

ハッシュサーチ※1とは,ものすごく強引に例えれば,教室の中で先生が生徒の名前を呼んで出席を取るような検索の方法です。名前を呼んだ生徒が出席していれば本人が返事をします。欠席ならば返事がありません。更に生徒の席が決まっていますから,そこに生徒がいるか見れば検索は一発で終了します。

ハッシュサーチの計算量はO(1)です。

ハッシュサーチの計算量

O (1)

もう少し具体的に解説しましょう。

ハッシュとは,ある大きさを持ったデータA(生徒)を,コンパクトな数値B(席)に対応させる操作のことです。このようなハッシュの仕組みを用いて,⁠検索を高速に行う」⁠データが改変されていないかを確認する」といった用途に用いられています。素早く出欠を確認し,代返が出来ないようにする仕組み,と言ったところでしょうか。

ハッシュを行う関数をハッシュ関数といいます。Java言語では,このハッシュを利用したデータ構造Hashtableクラス)を用意しています。プログラマはハッシュ関数のコードを書かなくとも,便利なデータ構造を利用することが出来ます。

※1)
hash search

ハッシュ関数のコード例

WikiPediaには次のようなハッシュ関数のコードが掲載されています。この関数の計算量はどれだけでしょうか?考えてみてください。答えは脚注に示しますので,一度考えてみてからご覧下さい※2)⁠

Wikipediaに掲載されているハッシュ関数の例

1:unsigned int hash(char *s) {
2:    unsigned int h = 0;
3:    for (;*s != '\0'; s++) {
4:        h = h * 137 + *s;
5:    }
6:    return h % 1987;
7:}

この関数がどのように動作するのか見てみましょう。

関数の引数の文字型の配列sには"a\0"と格納されているとします。

  • (1)h=0
  • (2)*sは配列の先頭要素の値を表します。いまは'a'です。
  • (3)aのアスキーコードはx61H(97)※3ですから,4行目の式の計算により,h=0*137+97=97となります。
  • (4)s++により,*s='\0'なのでループ終了。
  • (5)97 % 1987 = 97 。 %は剰余演算の記号※4です。

文字列"a\0"のハッシュ値は97となりました。

では,文字列変数sに"ab\0"と格納されていたとします。

  • (1)h=0
  • (2)*sは配列の先頭要素の値を表します。いまは'a'です。
  • (3)aのアスキーコードはx61H(97)ですから,4行目の式の計算により,h=0*137+97=97となります。
  • (4)s++で,*s='b'となり,'b'のアスキーコードはx62H(98)ですから,4行目の式の計算により,h=97*137+98=13387となります。
  • (5)s++により,*s='\0'なのでループ終了。
  • (6)13387 % 1987 = 1465

こうして,文字列"ab\0"のハッシュ値は1465となりました。

こうして計算できたハッシュ値はどのように利用されるのでしょうか。最もシンプルな場合ならば,こうです。

  • (1)1987個の文字列変数を要素として持つ配列hasharrayを用意します。初期値は全てNULLをセットしておきます。
  • (2)データ"a\0"は,ハッシュ関数値の値を利用して,hasharray[97]に格納します。"ab\0"はhasharray[1465]に格納します。
  • (3)このhasharrayに対してデータの検索を行う場合,次のように行います。
    • データ"a\0"は格納されているか?という指示に対し,ハッシュ関数を計算し,hasharray[97]をチェックするとNULLではありませんでした。ですから,受けた指示への回答として,⁠ありますよ」と返答するのです。
    • "cd\0"は格納されているか?という指示に対しては,ハッシュ関数の計算と配列のチェックを行った後にNULLを得ますから,⁠ありません」と返答します。

これがハッシュ関数をデータ構造に利用した例です。

このコードは決して実用的ではありませんし,このコードこそが唯一のハッシュ関数のアルゴリズムではありません。ハッシュ関数の概略をよく示していますが,ハッシュ関数の実装のほんの一例です。

実用的には,用意したメモリスペース内に,格納するデータをまんべんなく配置出来るような工夫をしっかり実装する必要があります。同じところに違うデータを格納できませんから,重複を回避する工夫も必要です。

今回はハッシュのおおよその理屈と仕組みを知ってもらえば十分ですから,この程度の解説で止めます。おおよその理屈を理解した上で,Java言語に標準で用意されているデータ構造を有り難く利用させてもらうのが,たいていは一番です※5)⁠

※2)
キーとなる文字列の長さをnとしてO(n)です。
※3)
16進数で61,10進数で97という意味です。以下,同様に表記します。
※4)
Java言語もC言語と同じです。連載第3回を参照下さい。
※5)
というのも,プログラミング言語といえども人の作ったモノですから,間違いがあったり,効率の悪いアルゴリズムが使われているかもしれないからです。それに気がついて,嫌だなぁ,と感じられるところまで登っていきたいですね。

O (1)のアルゴリズムは常に最速か?

誤解を避けるために,ここで一度まとめておきます。

O (1)というアルゴリズムは,⁠一度しか計算手順を必要としないアルゴリズム」とは限りません。⁠どんなに入力量が大きくても,およそ一定の計算手順で終了するアルゴリズム」のことです。ハッシュを用いたデータ構造にアクセスするためには,キーを与えてハッシュ値を得れば,求める値が一発で得られます。マクロに見れば,計算手順は「ハッシュ値の計算をする」の1つだけのようです。しかし,先にハッシュ関数のアルゴリズムで見たように,⁠ハッシュ値を計算する」という計算手順が何がしかの計算量を持っています。今回紹介したハッシュ関数の計算量はO (n)でした。では,ハッシュ関数を用いた検索はO(n)でしょうか?

ハッシュのキーは,たいていの場合で,ごく小さな文字列変数に格納されます。その長さは,取り扱うデータ量に比較すればとても短いはずです。たいていは文字列変数は固定長です。つまり,文字列長には最大値があります。すると,ハッシュ関数の計算実行量は,平均すればある定数,キーを格納する文字列の最大サイズ程度です。ですから計算量が一定,O (1)であると言えるのです。

オーダー記法は,あくまでオーダーであって,O (1)のアルゴリズムは,計算手順が常に1つだけだ,ということではありません。

著者プロフィール

平田敦(ひらたあつし)

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

コメント

コメントの記入