ハッシュサーチのプログラムを作りましょう。前回までに利用したのと同じ整数の配列をハッシュサーチで検索するプログラムを作ってください。Java言語には,ハッシュ関数を利用したHashtableというデータ構造が用意されていますので,それを利用しましょう。前回までと同様,検索実行時間を計測し,リニアサーチやバイナリサーチの場合と比較してください。これまでの検索では「求める整数値が配列の何番目に格納されているか」というように検索しました。今回の問題では,配列の添え字がハッシュテーブルの返値で,配列に格納される整数値がハッシュテーブルの検索のキーとなります。Hashtableクラスを利用しますから,以上のことに注意をしてプログラムを作成してください。ハッシュサーチのプログラムを作りましょう。それでは以下にハッシュサーチのコードを示します。お手元の環境での実行時間を計測してみてください。それにしても,Java言語には便利な道具が数多く用意されていますね。HashSearchプログラムを実行してみると,私の環境では94ミリ秒で検索が終了しました。リニアサーチに比べると,約50倍高速です。バイナリサーチに比べるとずいぶん遅いですね。先だって紹介した,ハッシュ値を計算するコードや,ハッシュを利用したデータ構造にアクセスする,という部分のコードが,バイナリサーチの実際のコードよりもコンピュータにとっては大きな負担になっているのです。データの配列が大きくなれば,ハッシュを利用するメリットがバイナリサーチの場合よりも大きくなるでしょう。少なくとも今回の程度であれば,まだバイナリサーチの方が有利なのですね。(1)の代表的な例で,実際これは高速です。計算量が同じオーダーであっても,どのような演算を1回,あるいは一定回数と数えるかで,実際にコンピュータで実行した場合にかかる時間はずいぶんと違うものなのです。データが極端に少ない場合さて,ここでちょっと実験です。疑り深くなってみましょう。現実はいつも理論通りにはならないものです。条件を変えてプログラムを実行してみましょう。変えて実行してみてください。同様に,BinarySearch.javaとHashSearch.javaの同じ部分も同様に変更して実行し,実行時間を比較してみてください。検索対象となるデータの個数を,10万個から10個に変更してみます。検索対象の個数が極端に少ないと,アルゴリズムによる総検索時間の差はどう変化するのでしょうか。皆さんの実行環境に大きく依存しますので,必ずこうなるとは断言できませんが,実行時間は次のような大小関係になったのではないでしょうか。HashSearch.java私の環境では,上記のように計算量の値の大小とは逆の順になりました。処理対象となるデータの量が少ないと,検索に要する時間よりもJava言語が裏で働いている時間の方が多くなってしまうからです。リニアサーチでは2つの数値が一致するかどうかの比較を行うだけですが,バイナリサーチでは中央値を求める処理と値の比較,ハッシュサーチはハッシュ値の計算をします。データの数が極端に少ないと,データの比較に要する時間に対して,検索を効率よく行おうとするため工夫を凝らした部分のコードの実行時間の割合が大きくなってしまったのです。実際のプログラミングでは,このようなことも意識しておかないと,小さな計算量のアルゴリズムを採用しても,実際の実行時間は長くなってしまった,なんていう見立て違いをしてしまう,という事になる良い例です。(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.ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。