連載
» 2007年10月18日 00時00分 公開

ソート処理時間、選ぶアルゴリズムでこんな差が!いまから始めるアルゴリズム(2)(2/2 ページ)

[鹿野恵祐,@IT]
前のページへ 1|2       

検索のアルゴリズム

 検索のアルゴリズムについても考えてみたいと思います。文章の中にある文字列が存在するかどうかを調べるには、どうしたらよいでしょうか。

 今回は例として、「TORINOKARAAGEBENTOUHAKAMIYACHOUDEURARETEIRU」(「鶏の空揚げ弁当は神谷町で売られている」。深い意味はありません)から検索対象文字列「KAMI」を探してみたいと思います。

力業での検索

 検索文字列と検索対象の文字列のそれぞれを、1文字ずつ比較する方法です。

 まず、検索文字列(「TORINOKARAAGEBENTOU……」)の1文字目と検索対象文字列(「KAMI」)の1文字目が同じ文字かどうか調べます。

 違う文字であれば検索文字列を1文字ずらし、検索文字列の2文字目と検索対象の1文字目が同じ文字かどうか調べます。

 同じ文字であれば、検索文字列の2文字目と検索対象の2文字目が同じ文字かどうかを判定します。このとき違う文字であれば、検索文字列を1文字ずらしてまた比較し、同じ文字であれば今度は検索文字列の3文字目と検索対象の3文字目が同じ文字かどうかを判定します。

 このように1文字ずつずらしながら比較を行います。検索対象文字列の最後の文字までが検索文字列中の文字と一致すれば、検索対象が見つかったということになります。

検索の手順 文字列の状態
検索文字列の1文字目「T」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
KAMI
「T」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
  KAMI
検索文字列の2文字目「O」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
  KAMI
「O」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
    KAMI
……繰り返す……
検索文字列の7文字目「K」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
           KAMI
一致するので検索文字列の8文字目「A」と
検索対象文字列の2文字目「A」を比較
TORINOKARAAGE……
           KAMI
一致するので検索文字列の9文字目「R」と
検索対象文字列の3文字目「M」を比較
TORINOKARAAGE……
           KAMI
「R」と「M」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
              KAMI
検索文字列の8文字目「A」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
              KAMI
「A」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
                KAMI
検索文字列の9文字目「R」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
                KAMI
「R」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
                  KAMI
検索文字列の10文字目「A」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
                  KAMI
「A」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
                    KAMI
検索文字列の11文字目「A」と
検索対象文字列の1文字目「K」を比較
TORINOKARAAGE……
                    KAMI
「A」と「K」は一致しないので検索文字列を1文字ずらす TORINOKARAAGE……
                      KAMI
 ……繰り返す……
検索文字列の22文字目「K」と
検索対象文字列の1文字目「K」を比較
……HAKAMIYACHOU……
           KAMI
一致するので検索文字列の23文字目「A」と
検索対象文字列の2文字目「A」を比較
……HAKAMIYACHOU……
           KAMI
一致するので検索文字列の24文字目「M」と
検索対象文字列の3文字目「M」を比較
……HAKAMIYACHOU……
           KAMI
一致するので検索文字列の25文字目「I」と
検索対象文字列の4文字目「I」を比較
……HAKAMIYACHOU……
           KAMI
検索対象文字列のすべての文字が一致。検索完了 ……HAKAMIYACHOU……
           KAMI

Knuth Morris Pratt法

 上記の方法では、検索文字列の9文字目と検索対象文字列の3文字目が一致しなかったとき、検索文字列は1文字しかずれず、次に検索文字列の8文字目と検索対象文字列の1文字目を比較します。これはこの文字列の検索の場合、明らかに無駄な処理です。

 そこで、文字が部分的に一致した後に不一致が起こった場合、複数文字ずらすことによって処理を減らし、高速化をさせるという方法もあります。そのうちの1つがKnuth Morris Pratt法です。

 この方法は、理論的に力業での検索よりも速く検索できるはずですが、そうなるのは当然ながら、文字の部分的な一致が起こった場合のみです。部分的な一致が起こらない場合は、実行速度に劇的な変化が見られない可能性があります。特に、比較的文字の種類が多い日本語の文字列を検索する場合は、1文字当たりの出現頻度が小さく、部分的な一致が起こる確率が低いため、なおさらそう感じるかもしれません。

 検索のアルゴリズムには、このほかにもBoyer-Moore法や、それを改良したものなどがあります。また違ったアプローチで高速に検索しようとする手法なので、興味があればぜひ調べてみてください。

 「高速な検索機能を実現!」とうたっているアプリケーションなどは、何らかのアルゴリズムに改良を加えて効率的な処理を行っているのかもしれません。

目的に合ったアルゴリズムを

 今回は、並べ替えと検索のアルゴリズムを取り上げました。記事中盤でグラフを交えて紹介したように、アルゴリズムの違いによって処理時間が大きく異なる可能性があることを覚えておいてください。今回のバブルソートとマージソートの例では、10万件のデータの処理で1000倍以上の差が出ています。これだけの差をハードウェアで吸収しようと思っても、実現はなかなか難しいでしょう。

 繰り返しになりますが、処理時間を短縮するためには、それに適したアルゴリズムを選択することが重要になってきます。ただし、アルゴリズムによってはプログラムのステップ数が増えて保守が大変になったり、使用するメモリ量が増大してほかの処理に悪影響を及ぼしたりすることもありますので、ご注意ください。処理するデータの量、保守のしやすさなどいろいろな要素を検討し、目的に合ったアルゴリズムを選びましょう。

 プログラミング言語でもともと用意されている仕組みを利用する場合にも、どういう手法に基づいて処理を行っているかを知ることで、目的に向いているか向いていないかが分かります。場合によっては、自分で実装した方がよいということもあるはずです。

 ここで、私が過去に経験したトラブルを1つ紹介したいと思います。

 以前私が保守を担当していたあるポータルサイトには、ユーザーのログイン後、各ユーザーの権限に従ってお知らせを表示する機能がありました。サーバのハードウェアが老朽化し、表示するお知らせを管理するソフトウェアも新バージョンが提供されていたので、システムを移行することになりました。

 古いサーバマシンから新しいマシンにデータを取り込み、ソフトウェアも古いバージョンから新しいバージョンに移行してテストをしてみると、ログインしてからお知らせが表示されるまでに異様に時間がかかるのです。それまでは5秒ほどで表示されていたのに、2分以上待たされる場合すらありました。最新のCPUを積んだサーバに切り替えたことで、実性能で5倍ほどの処理速度が見込めるはずだったのに、実際は25倍以上も遅くなっていたのです。

 「こんなはずはない」とプログラムを調べてみたところ、なんとお知らせの表示の順番を決定するIDが文字列型になっており、それを読み込んで整数型へ変換してから並べ替えをしていたのでした。また、ユーザーによっては複数の部署の情報が表示されるのですが、1つの部署の情報を取得後並べ替え、ほかの部署の情報を取得後並べ替え、最後に全体を並べ替え……という、何とも非効率的過ぎる方法を取っていたのです。

 これらを修正した後は期待どおりの性能が出るようになり、胸をなで下ろしました。こんな恐ろしい例もありますので、皆さんもご注意ください。

筆者紹介

鹿野恵祐

1978年夏、東京生まれ。東京電機大学理工学部経営工学科卒業後、システムインテグレータにてシステム設計・構築を担当。「長期にわたって使えるシステム」を模索する日々。最近は、コンピュータ以外にも視野を広げようといろいろチャレンジ中。西武ライオンズファン歴24年。好物は鶏の空揚げ。



前のページへ 1|2       

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。