こうしろうは,4月21日の基本情報技術者試験に向けた勉強を分厚い参考書と問題集で続けている。数値表現の章を終え,現在はアルゴリズムについて学んでいる。その勉強の様子を見て思った。「こいつ,本を読むスピードが遅い!」
私は,割と本を読むのが速い方である。というか,仕事に関係する本はサッーと流して読んで,どこに何が書いてあるかだけを覚えておいて,理解できなかったことは,後から読み返すようにしている。読書としては,面白くもなんともない方法であるが,同時に数冊の本を読むのには便利である。この読み方が癖になってしまって最近,気に入っている重松 清さんの短編集などをコンピュータ関係の本を読むのと同じ方法で読んでしまって,『ビタミンF』やら『リビング』,『日曜日の夕刊』などのストーリーがごっちゃになって困っている。
こうしろうは遅い。1ページを舐めるように読んでいて,1時間近い時間を掛けることもある。4月21日までに読み終えなくてはならない量を考えると「サッーと流して読め」と言いたくなるのであるが,これがこの人のスタイルなんだと,喉元まで上がってくる言葉を飲み込んでいる。基本情報技術者『標準教科書』のアルゴリズムの章は10数ページあり,もう1週間近い日数をかけ読んでいる。
さて,アルゴリズムとは何か。
データがある。別にデジタルで表現されたコンピュータ向けのデータでなくても構わないのであるが,あるデータの固まりがあって,何らかの処理をしなくてはならない時に,これをどうやったら正確かつ効率的に処理できるかを考え,考え出された手法をアルゴリズムという。
例として文字列処理のアルゴリズムを紹介しよう。「こんにちはのなかりかちゃん。わたしはほのぼのとしたほのかです。」という文書がデータファイルとして保存されているとする。他にも内容の違う文書がたくさん保存されている。それらの中から「ほのか」という文字列が含まれている文書を探さなくてはいけない。どうやって被探索文字列(こんにちはのなかりかちゃん…)のなかに探索文字列(ほのか)が含まれているかを正確かつ効率的に調べるにはアルゴリズムが必要になる。
単純探索法
法と名前を付ける必要があるんかいと言いたくなるほど単純な方法である。「こんにちはのなかりかちゃん。わたしはほのぼのとしたほのかです。」に「ほのか」が含まれているから,先頭から一文字ずつ比較していく方法である。
まず探索文字列(ほのか)の1文字目(ほ)に一致するかを調べ,一致しなければ1文字ずつシフトしていく。一致した場合は2文字目,3文字目が一致するか調べていく。これじゃ,非効率だろうとボイヤーさんとムーアさんが考えたのが次の方法である。
ボイヤー・ムーア法
ボイヤー,シピンだと昔の大洋ホエールズ(現横浜ベイ・スターズ)である。古すぎて知ってる人は少ないかもしれないが,あの頃のホエールズには中塚さんとか個性的な選手が多くおもしろいチームだった。ボイヤー・ムーア法の特徴は探索文字列の最後の文字から比較するという点である。この例では「ほのか」の「か」から調べていくのである。
まず「か」と被探索文字列中の3番目の文字「に」を比べる(1)。違うので次は「に」と「か」の1文字前の「の」,次にその前の「ほ」と比べる。どれも一致しないので3文字シフトする(2)。次に「か」と6番目の文字「の」を比べる。違うので1文字前の「の」と比較する。一致するので3文字とも一致するかもしれないと期待を込めて,今度は1文字だけシフトする(3)。「か」と「な」を調べて一致しないので「な」と「の」と「ほ」を調べていく。一致しないので,3文字シフトする(4)。今度は「か」と「か」が一致する。次にその1文字前の「の」と「り」を調べる。一致しない。ここで,ボイヤー・ムーア法がその力を発揮する。3文字目が一致していて,2文字目が一致しなければ,この3文字と一致する可能性はないので,バカーンと3文字シフトできるのである(5)。きりがないので途中省略するが,この例では10回目のシフトで「ほのか」と出会う。
久しぶりにボイヤー・ムーア法を勉強しなおしてみて,『美しいなあ』と感じた。効率が良くスキがないアルゴリズムは素敵なのである。
第78話 効率がいいアルゴリズムは美しい
あなたにお薦め
今日のピックアップ
-
生成AIを3週間で「即席」導入、年3万時間の削減に成功した日清食品デジタル部隊の力
-
オープンソースソフトは何かの節目を迎えているのではないか
-
DoS攻撃に新手法、攻撃者のパケット1つで無限に続く「Loop DoS」の正体
-
AI時代に勝ち残る条件、あなたは自分の仕事を無くせますか?
-
Azureで知らぬ間に生じる無駄コスト、簡単に監視する仕組みとは
-
WeChatで人気の「歌唱AI」論文、顔写真1枚と音声だけで動画生成する仕組み
-
国産SaaSへの対応が進むETLサービス、Reckoner使いノーコードでデータ連係
-
ミニPCの作業環境を周辺機器やアクセサリーで快適に、設置方法も工夫しよう
-
スマホの平均使用は4年以上に、バッテリーの劣化とOSのサポート期間が寿命を左右
-
Excelシートを「別のブックにコピー」、自分に合う早ワザをマスターしよう
-
自分の仕事はこの先どうなる、不安なときこそ持ちたいもの
-
双日・三井化学・中外製薬のCIO/CDOが激論、IBM時代の経験はDXにこう生かす
注目記事
おすすめのセミナー
-
「仮説立案」実践講座
例えば「必要な人材育成ができていない」といった課題に、あなたならどう取り組みますか? このセミナ...
-
CIO養成講座 【第35期】
業種を問わず活用できる内容、また、幅広い年代・様々なキャリアを持つ男女ビジネスパーソンが参加し、...
-
改革リーダーのコミュニケーション術
プロジェクトを成功に導くために改革リーダーが持つべき3つのコミュニケーションスキル—「伝える」「...
-
パワポ資料が見違える「ビジネス図解」4つのセオリー
インフォグラフィックスとは、形のない情報やデータなど伝えたいことを分かりやすい形で表現する技法で...
-
間違いだらけの設計レビュー
本セミナーでは、現場で多く見られる間違ったレビューの典型例を示し、そうならないための現場の改善策...
-
オンライン版「なぜなぜ分析」演習付きセミナー実践編
このセミナーでは「抜け・漏れ」と「論理的飛躍」の無い再発防止策を推進できる現場に必須の人材を育成...
-
問題解決のためのデータ分析活用入門
例えば「必要な人材育成ができていない」といった課題に、あなたならどう取り組みますか? このセミナ...
-
業務改革プロジェクトリーダー養成講座【第16期】
3日間の集中講義とワークショップで、事務改善と業務改革に必要な知識と手法が実践で即使えるノウハウ...
注目のイベント
-
【4月19日】データの活用と保護を両立、「段階的なDX」を実現するIT基盤とは?
2024年 4月 19日 14:00
-
【4月25日】ハイパーバイザーの基本を学ぶ、参加者にはもれなくプレゼント進呈
2024年4月25日(木)
-
プラチナフォーラム 2024 Spring
2024年 4月 26日(金) 13:00~17:00(予定)
-
日経クロステックNEXT 関西 2024
2024年5月16日(木)~5月17日(金)
-
日経ビジネスCEOカウンシル
2024年5月16日(木)17:00~19:50
-
VUCA時代に勝ち残る戦略的サプライチェーン構築に向けて
2024年 5月 24 日(金) 10:00~16:20
-
人手不足を乗り越える 日本の産業界成長のシナリオ2024
2024年5月30日(木)10:20~17:45
-
キャリア・オーナーシップが社会を変える
2024年6月3日(月)~6月5日(水)
-
DX Insight 2024 Summer
2024年6月4日(火)、5日(水)
-
デジタル立国ジャパン2024
2024年6月10日(月)、11日(火)
おすすめの書籍
-
ソフトバンク もう一つの顔 成長をけん引する課題解決のプロ集団
ソフトバンクにはモバイルキャリア事業以外のもう一つの顔が存在する。本書ではキーパーソンへのインタ...
-
対立・抵抗を解消し合意に導く 改革リーダーのコミュニケーション術
本書は、改革リーダーに必須のコミュニケーション術を3つのスキルの観点からまとめ上げたものです。今...
-
もっと絞れる AWSコスト超削減術
本書ではコスト課題を解決するため、AWSコストを最適化し、テクニックによって削減する具体策を紹介...
-
優秀な人材が求める3つのこと 退職を前提とした組織運営と人材マネジメント
「学生に人気のコンサルであっても、大手企業であっても、せっかく獲得した人材が数年で辞めてしまう...
-
Web3の未解決問題
ブロックチェーン技術を主軸とするWeb3の技術について、現在の社会制度との摩擦と、その先にある新...
-
ロボット未来予測2033
ロボットの用途・市場はどう拡大していくのか。AI実装でロボットはどこまで進化するのか。技術の進展...
日経BOOKプラスの新着記事
日経クロステック Special
What's New
経営
- 「クラウド時代のあるべき運用」を熱く議論
- 大企業にもキントーンの導入が進む理由
- 製造業DX「データドリブン経営成功のシナリオとは」
- NTTドコモ支援の実践型教育プログラム
- ジェイテクトエレクトロニクスのDX事例
- DXを成功に導くITインフラとは?
- NTTデータに優秀なデジタル人財が集まる理由
- オリックス銀行×富士通時田社長 特別鼎談
- ERPプロジェクト≫IT人財の必須条件は
- 脱レガシー案件≫SIerに必要な人財像は
- イノベーションの起爆剤
- 3段階で考える、DXで企業力を高める方法
- 大規模プロジェクトでPMが注意すべき点は
- 大阪・名古屋エリアのDXが注目される理由
- 力点は「未来予測」へ:データ利活用の勘所
- 生成AI活用でSAP BTPの価値が進化
- ServiceNowでDXを加速≫方法は
- SAPプロジェクトの全体像をいかに描くか
- 基盤のモダナイゼーションで変革を実現