分12物事はシンプルであればあるほど記憶しやすく,組み合わせて何事かを処理するのも容易になります。アルゴリズムもシンプルであればあるほど優れていると言えます。物事をシンプルにする,とひとことで言っても,いくつかの処理のステップをまとめて1つの名前を付けること,つまり,抽象化によってシンプルにした場合には注意が必要です。抽象化してシンプルになった名前の裏では,汗水たらしててんてこ舞いして働いている人がいるかもしれませんから。営業担当者が「簡単です!うちに任してください!」といって取ってきた仕事を,製造現場の労働者が泣きの涙で作って出荷している・・・という笑えない状況と,どこか似ているような似ていないような。いえ,決して営業さんは悪くないんですよ。計算量:ハッシュサーチの場合O(1)バイナリサーチは十分高速な検索アルゴリズムです。これ以上早いアルゴリズムがあるのでしょうか。結論から書くと,バイナリサーチが最速かつ適切でしょう。あらゆる場合に適切かというと,そうでもありません。一般に検索のキーは整数ではなく文字列です。住所録,商品データベースなどです。ある商品の検索を行う場合に,商品名が分かっても,商品番号が分からないのが普通です。名前を覚えずに番号で覚える奇特な人はそういません。した場合には,次のハッシュサーチが有望です。ハッシュサーチ(※1)とは,ものすごく強引に例えれば,教室の中で先生が生徒の名前を呼んで出席を取るような検索の方法です。名前を呼んだ生徒が出席していれば本人が返事をします。欠席ならば返事がありません。生徒の席が決まっていますから,そこに生徒がいるか見れば検索は一発で終了します。ハッシュサーチの計算量はO(1)です。(1)もう少し具体的に解説しましょう。ハッシュとは,ある大きさを持ったデータA(生徒)を,コンパクトな数値B(席)に対応させる操作のことです。このようなハッシュの仕組みを用いて,「⁠検索を高速に行う」「⁠データが改変されていないかを確認する」といった用途に用いられています。素早く出欠を確認し,代返が出来ないようにする仕組み,と言ったところでしょうか。ハッシュを行う関数をハッシュ関数といいます。Java言語では,このハッシュを利用したデータ構造(Hashtableクラス)を用意しています。プログラマはハッシュ関数のコードを書かなくとも,便利なデータ構造を利用することが出来ます。searchハッシュ関数のコード例WikiPediaには次のようなハッシュ関数のコードが掲載されています。この関数の計算量はどれだけでしょうか?考えてみてください。答えは脚注に示しますので,一度考えてみてからご覧下さい(※2⁠)⁠。1987;7:}この関数がどのように動作するのか見てみましょう。関数の引数の文字型の配列sには"a\0"と格納されているとします。(1)h=0(2)*sは配列の先頭要素の値を表します。(3)aのアスキーコードはx61H(97)(※3)ですから,4行目の式の計算により,h=0*137+97=97となります。(4)s++により,*s='\0'なのでループ終了。%は剰余演算の記号(※4)です。文字列"a\0"のハッシュ値は97となりました。文字列変数sに"ab\0"と格納されていたとします。(1)h=0(2)*sは配列の先頭要素の値を表します。(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'なのでループ終了。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)というのも,プログラミング言語といえども人の作ったモノですから,間違いがあったり,効率の悪いアルゴリズムが使われているかもしれないからです。それに気がついて,嫌だなぁ,と感じられるところまで登っていきたいですね。(1)のアルゴリズムは常に最速か?誤解を避けるために,ここで一度まとめておきます。(1)というアルゴリズムは,「⁠一度しか計算手順を必要としないアルゴリズム」とは限りません。「⁠どんなに入力量が大きくても,およそ一定の計算手順で終了するアルゴリズム」のことです。ハッシュを用いたデータ構造にアクセスするためには,キーを与えてハッシュ値を得れば,求める値が一発で得られます。マクロに見れば,計算手順は「ハッシュ値の計算をする」の1つだけのようです。先にハッシュ関数のアルゴリズムで見たように,「⁠ハッシュ値を計算する」という計算手順が何がしかの計算量を持っています。ハッシュ関数を用いた検索はO(n)でしょうか?ハッシュのキーは,たいていの場合で,ごく小さな文字列変数に格納されます。その長さは,取り扱うデータ量に比較すればとても短いはずです。文字列変数は固定長です。文字列長には最大値があります。すると,ハッシュ関数の計算実行量は,平均すればある定数,キーを格納する文字列の最大サイズ程度です。(1)であると言えるのです。(1)のアルゴリズムは,計算手順が常に1つだけだ,ということではありません。プログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。2019」を開催しました。DAY1・DAY2の様子を注目セッションとともにお伝えします。LINEのエンジニア3名がイベントに先駆けて見どころを紹介します。コードの安全性・安定性を高める開発サイクル~テスト管理の効率を上げ,脆弱性診断を自動で行う~本連載では,連載「業務を改善する情報共有の仕掛け」を受けつつ,安全性・安定性を加えた開発サイクルについて考えていきます。若者世代から圧倒的な人気を誇るライブ配信&動画投稿コミュニティアプリ「MixChannel」(ミクチャ)の裏側(レコメンドシステムやサーバサイド開発など)について解説していきます。その他の連載CSS3アニメーションでつくるインターフェイス表現CSS3によるアニメーション表現を紹介していきます。その中でも,幅広い読者に応用してもらえるだろうインターフェイスを主なお題とします。MySQL道普請便り本連載では,MySQLを使ったアプリ開発・運用に関するノウハウをご紹介していきます。RecipeUbuntuの強力なデスクトップ機能を活用するための,いろいろなレシピをお届けします。JavaScriptセキュリティの基礎知識JavaScriptに関するセキュリティ上の問題はどこで発生し,どうすれば防ぐことができるのか?について解説していきます。〜システムをきちんと運用するための基礎知識システムは「作って終わり」ではなく,運用の中でさまざまな問題が発生します。問題の発生に備えて事前にどのような対応をしておくべきなのか,問題発生時に何をしなければならないのか,ポイントを解説していきます。きたみりゅうじの聞かせて珍プレーソフトウェア開発の現場で体験したトホホな失敗,思わずうなる珍プレーをきたみりゅうじ氏が四コママンガで紹介。Linuxのメンテナンスの傍ら,Linuxやオープンソースソフトと日々を過ごす著者が,その魅力とつきあい方を,エッセイ風味でお届けします。PRESS特別編集部員,さわやか笑顔のスーパーハカーはまちちゃんとネット大好き14歳わかばちゃんが,毎号,読者の皆さんから寄せられたおたよりを紹介します。皆さんの日頃の悩みにも答えちゃいますよ。]メールでのお知らせメールで次の案内をお送りしております。メールの配信を希望する方は,利用したい項目をチェックしてメールアドレスを入力し,[登録]ボタンをクリックしてください。UPDATES[ほぼ週間に1回]新刊メールマガジン[ほぼ週間に1回]電脳会議の各号案内[ほぼ1ヵ月半に1回]※変更する場合や停止する場合は,登録情報変更ページをご覧ください。※登録いただいたメールアドレスには,そのお知らせ以外,配信いたしません。Ltd.ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。