catch-img

プログラミングに大切なアルゴリズムとは。頻繁に使われる整列の意味

計算方法のやり方を意味するアルゴリズムは、プログラミングにとっては基礎と言える概念で、検索サービスや車載カメラなどさまざまなプログラムに応用されています。アルゴリズムの種類や活用方法、おすすめの書籍を見ていきましょう。

目次[非表示]

  1. 1.そもそもアルゴリズムとは何か
    1. 1.1.アルゴリズムの意味を知ろう
    2. 1.2.私たちの身近なところで活用されている
  2. 2.プログラミングにおいてのアルゴリズム
    1. 2.1.効率の良いプログラムを作るための考え方
    2. 2.2.基本情報技術者試験にも出題
  3. 3.アルゴリズム学習で大切なこと
    1. 3.1.順次型、分岐型、反復型など基本構造
    2. 3.2.フローチャートの読み書き
    3. 3.3.計算量の記述
  4. 4.よく使われるアルゴリズムの例
    1. 4.1.膨大なデータを並べ替えする ソート
    2. 4.2.ソートアルゴリズムの種類
  5. 5.ソート以外にも役立つアルゴリズムはいろいろある
    1. 5.1.要素をスムーズに見つける 探索
    2. 5.2.切り出しや連結などを行う 文字列操作
  6. 6.理解しやすくまとめられた書籍を読もう
    1. 6.1.アルゴリズム図鑑
    2. 6.2.プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
  7. 7.無駄のない適切なコードを書くために


そもそもアルゴリズムとは何か


プログラミングの研修カリキュラムでは、アルゴリズムという単語を目にすることがあるでしょう。アルゴリズムとは何かを理解することで、プログラミングにとっての重要性が分かります。

アルゴリズムの意味を知ろう

「アルゴリズム」とは、問題・課題を正解に導くための「効率的な処理手順」や「具体的な計算方法」です。アルゴリズムは理路整然と定式化されるため、手順通りに処理・計算すれば誰でも再現できます。

問題に対する正解は1個であっても、解答までの手順はさまざまであるため、一つの問題に対して複数のアルゴリズムが考案されるケースも少なくありません。

アルゴリズムの例として、よく「野菜のいちょう切り」が挙げられます。縦に2回切るか、輪切りにしてから4等分するかでは、野菜を切る回数で見れば前者の方が効率的です。

いちょう切りにした野菜の枚数は同じでも、手順が違えば効率は異なります。「より洗練された手順を考え選択する」というのがアルゴリズムの基本的な考え方です。

私たちの身近なところで活用されている

インターネットでキーワード検索をする際、日本国内ではほとんどのユーザーがGoogleの「検索エンジン」(検索サービスのためのプログラム)を利用しています。Yahoo!検索で使われているのもGoogleの検索エンジンです。

Googleの「検索アルゴリズム」は、検索意図・ページの関連性・コンテンツの品質・ユーザーの位置情報・情報の鮮度など、複数の要素を検討するアルゴリズムを組み合わせています。

この複雑かつ高度なアルゴリズムから成るプログラムによって、Google検索やYahoo!検索では適切なランキングを瞬時に表示する仕組みです。

ほかにも、自動車の車載カメラの映像をリアルタイムで補正する「画像処理アルゴリズム」など、身近なプログラムにさまざまなアルゴリズムが活用されています。

プログラミングにおいてのアルゴリズム


プログラミングの現場ではアルゴリズムの活用は必須です。プログラミングにおいて、アルゴリズムがなぜ重視されるのかを見ていきましょう。

効率の良いプログラムを作るための考え方

プログラミングでは、プログラムに求められる機能を実現するために処理の手順を記述します。洗練されたアルゴリズムを活用することで、プログラムの性能向上やソースコードの整理が可能です。

処理速度の速いアルゴリズムを活用すれば、時間やメモリといった有限資源を有効活用できる上、定式化されたコードは可読性が高いため、保守性を上げることにもつながります。

一般的な問題の解決に関わるアルゴリズムはすでに複数確立されていますが、それぞれの処理内容や効率を理解していなければ、プログラミングの現場では有効活用できません。

より良いプログラミングを求めるなら、より効率的な処理手順を検討し、プログラムに合ったアルゴリズムを選択できる知識・経験が重要です。

基本情報技術者試験にも出題

『基本情報技術者試験』とは、高度IT人材であることを証明する基礎的な試験の一つです。基礎的といっても経済産業省が行う国家試験であり、近年の合格率は30%にも満たない狭き門となっています。

基本情報技術者試験の出題範囲は、コンピュータシステムや開発技術に加え、プロジェクトマネジメント・経営戦略・法務などと網羅的です。

試験は午前試験・午後試験の1日がかりで、アルゴリズムは午後試験の必須回答科目となっています。100点中25点と配点も大きく、正答率60%以上という合格ラインから見ても重要な科目です。

主な出題内容は、アルゴリズムのコーディング・途中経過・実行回数・エラーの原因究明などとなっています。

アルゴリズム学習で大切なこと

アルゴリズムには条件分岐やループ処理など処理手順の構造があり、その構造はフローチャートで図式化できます。処理構造やフローチャート、効率性の指標である計算量を理解することの重要性を見ていきましょう。

順次型、分岐型、反復型など基本構造

アルゴリズムを処理手順の基本構造で見ると、「順次処理(逐次構造)」「分岐処理(条件構造)」「反復処理(繰り返し構造)」などに分類できます。

  • 順次処理:記述されたコードの流れ通りに、一通りの処理を順次行うタイプ
  • 分岐処理:条件を指定して、値が条件を満たすなら処理A、条件を満たさないなら処理Bという分岐があるタイプ
  • 反復処理:値が条件を満たす(または満たさない)まで処理Aを反復し、条件を満たした(または満たさなかった)なら処理Bに進むタイプ

実際のプログラミングでは条件分岐やループ処理は頻出するため、利用するアルゴリズムがどのような構造かを理解し、処理手順を整理することは重要です。

フローチャートの読み書き

「フローチャート」とは、プロジェクトの工程やアルゴリズムの処理手順などを図式化したものです。チーム単位でシステム設計を行う場合、工程・工数管理などのためにフローチャートを作成する場合があります。

また、分岐処理・反復処理などのアルゴリズムの処理手順も、フローチャートで図式化が可能です。プログラミングを始める前にフローチャートを作成することで、事前設計に沿ったソースコードを作成しやすくなります。

フローチャートはメンバー全員にとって可読性が高いことも利点です。個々の業務内容に専門知識がなくても、業務進捗の遅れや実装内容の誤りなどをメンバーが相互チェックできます。

プログラマー個人のパフォーマンス向上という意味はもとより、特にチーム単位でプログラミングに従事する場合、フローチャートの読み書きは重要なスキルです。

計算量の記述

「計算量」とは、アルゴリズムが解を導くまでに要する計算時間です。1課題に対して複数のアルゴリズムが利用できる場合、計算量の少ないアルゴリズムの方がハイパフォーマンスと判断できます。

つまり、計算量はアルゴリズムの効率性を判断する指標の一つと言えるでしょう。プログラムを実行するコンピュータによって絶対的な計算時間は異なるため、一般的には「O記法」(オー記法、オーダー記法)による相対的な計算時間を比較します。

たとえば、総当たりの組み合わせを求める「On^2)」のアルゴリズムでは、入力データ数n2乗の計算量です。n10倍になると計算量は100倍になってしまい、膨大なデータの処理には向きません。

一方で、反復処理を活用した「Olog n)」のアルゴリズムでは、n1000でも実行回数は10回程度です。処理手順の違いでパフォーマンスが大きく異なるため、プログラミングの現場では計算量の比較も重要と言えます。

よく使われるアルゴリズムの例

アルゴリズムは解決したい問題・課題によって多種多様です。ここでは、データの整列に関わるソートアルゴリズムを例として見ていきましょう。

膨大なデータを並べ替えする ソート

「ソートアルゴリズム」は、プログラムに入力した複数の数値や文字列を、昇順(小さい値から大きい値へ)または降順(大きい値から小さい値へ)に並べ替えるアルゴリズムの総称です。

たとえば、受験者1000人分の点数や住所録1000人分の住所を、自動的に昇順または降順に整列します。データの整列はプログラムが担う基礎的な機能であるため、確立されたソートアルゴリズムの種類は豊富です。

処理手順によって効率はさまざまで、プログラマーには適切なソートアルゴリズムを選択するスキルが求められます。

ソートアルゴリズムの種類

ソートアルゴリズムにはさまざまな種類があり、定式化されたメソッドをもとに、コードを適切に調整して実装します。ソートアルゴリズムの例は以下の通りです。

  • バブルソート:先頭または末尾から隣接する二つの値を比較・交換していき、末尾または先頭から値を確定していくことを繰り返す
  • 選択ソート:入力データから最大値や最小値を探し、先頭または末尾の値から確定していくことを繰り返す
  • クイックソート:適当な基準値(ピボット)を選択し、基準値より小さい値を基準値前方、基準値より大きい値を基準値後方に交換することを繰り返す

ソート以外にも役立つアルゴリズムはいろいろある

複数の入力データを扱うプログラムにとってソートアルゴリズムは必須ですが、探索アルゴリズムや文字列操作に関わるアルゴリズムも有用です。

要素をスムーズに見つける 探索

「探索アルゴリズム」は、指定した条件を満たす解を導くアルゴリズムの総称です。入力データから目的の値を検索する単純な探索もあれば、将棋の勝ち筋を初手から求めるような複雑な探索もあります。

代表的な探索アルゴリズムは「線形探索」や「二分探索」です。

  • 線形探索:リストの先頭から目的の値を検索する
  • 二分探索:ソート済みのリストを二分して左右の大小関係を比較し、目的の値が見つかるまで二分を繰り返す

また、「文字列探索」も探索アルゴリズムの一種です。部分文字列検索(パターンマッチング)や正規表現マッチングなどがあり、複数ファイルの横断的な文字列探索を「全文検索」と呼びます。

切り出しや連結などを行う 文字列操作

文字列の抽出(スライス)や連結なども、定式化されたアルゴリズムの一種です。文字列とは、単語や文章などの文字の「シーケンス(配列)」を指します。

プログラムに入力する文字列には1文字ずつインデックス番号が振られており、文字列とインデックス番号を指定して文章の分割が可能です。文字列の大文字化・小文字化や、複数文字列の結合などもできます。

また、「ランレングス圧縮」による文字列データの圧縮も可能です。たとえば「AAABBBBCCCCC」という文字列を「A3B4C5」に変換して、データ量を2分の1に圧縮できます。単純な可逆圧縮なので、復元も容易です。

理解しやすくまとめられた書籍を読もう

より良いプログラミングを求めるなら、アルゴリズムをいかに活用するかが重要です。アルゴリズムの理解を深めるために、初心者にも分かりやすくまとめられた書籍で学びましょう。

アルゴリズム図鑑

Appleの選ぶ2016年のベストアプリ』に選出されたエンジニア向け学習アプリ『アルゴリズム図鑑』の書籍版です。

アルゴリズムを理解するために必須の7種類の「データ構造」と、ソート・グラフ探索・セキュリティなど6カテゴリーから基本的な26種類のアルゴリズムが学べます。

図解を多用しているため初心者でも理解しやすく、これからアルゴリズムを学ぶ人におすすめの書籍です。

  • タイトル:アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
  • Amazon商品ページ

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』は、プログラミングの能力や技術を競い合う「プログラミングコンテスト」を攻略するための書籍です。攻略といっても初心者向けの内容で、体系的かつ実践的にアルゴリズム・データ構造について学べます。

本書で学習した内容は、プログラミング問題のオンライン採点システム『Aizu Online JudgeAOJ)』でチャレンジできます。学んだスキルで問題を解き、応用も楽しみたい人におすすめの書籍です。

  • タイトル:プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
  • Amazon:商品ページ

無駄のない適切なコードを書くために

簡単なプログラミングを行うだけならアルゴリズムの知識は必須ではありませんが、上級エンジニアを目指すならアルゴリズムやフローチャートの理解は必須です。

適切なアルゴリズムを選択してプログラムを作成すれば、処理時間の短縮やメモリ使用量の縮小につながる上、デバッグや機能追加の際にも作業しやすいソースコードに仕上がります。

設計の段階からプログラムの効率化を求め、有限資源を無駄に消費することのない、適切なコーディングを行いましょう。




プロエンジニア育成コース(Java,SQL,Spring) 短期通学講座、オンライン・リモート講座 (Java,HTML5・CSS・JavaScript)について お気軽にお問い合わせ下さい。