データ構造はコンピュータサイエンスとソフトウェアエンジニアリングの分野全体で幅広く多様な用途があります。
プログラマにとって、アルゴリズムとデータ構造は最も重要なテーマです。
プログラミングの分野に足を踏み入れたい場合は、最も一般的なデータ構造を習得し、需要の高いスキルであなたの履歴書を強化する必要があります。
本日はデータ構造とアルゴリズムを解説いたします。
データ構造とアルゴリズム
プログラミングはすべてデータ構造とアルゴリズムに関するものとなります。
コンピュータプログラミングでは、データ構造はコンピュータプログラムでデータを効率的に保存、アクセス、および処理するための事前定義された形式であり、データを配置する方法となります。
一部のデータ構造はプログラミング言語の組み込みコンポーネントであり、その他のデータ構造では構造を使用する前にライブラリまたはモジュールを含める必要がある場合があります。
コンピューター関連の貢献者である
『Linux OS』と『Git』の元開発者で生みの親とも言われる、リーナス・トーバルズ氏はこのように仰っていました。
『悪いプログラマはコードについて心配します、 良いプログラマはデータ構造とそれらの関係について心配します。』
つまりデータ構造・アルゴリズムをよく知らないと、今書いているコードを最適化できるかどうかを特定できません、それらを事前に知って可能な限り重要な場所に適用することが求められます。
データ構造とは？
データ構造とは、コンピュータシステムにおいて、データを効率的に操作できるように保存・整理する手法のことです。
非構造化データとは、定義されたデータモデルを持たず、操作や分析に適した方法で整理されていないデータのことになります。
非構造化データでは、データを収集しながらも効果的な保存や整理を行っていない組織でよく見られる問題であり、世界のデータの80%は非構造化データであると言われています。
一方で、データ構造は様々なレイアウトの形をしており、それぞれがある操作には効率的だが、他の操作には非効率的です。
プログラマの目標は、手元にあるデータに対してどのデータ構造が適切かを判断し、そのデータを活用して問題を解決することです。
データ構造は効率的なアクセスと変更を可能にする 1 つの形式にまとめられた、データの編成、管理、検索、およびストレージのブレンドです。
データ値、それらが共有する関係および適用可能な機能または操作を収集しています。
データ構造は、アルゴリズムに大きく影響し依存しているため、アルゴリズムに適したデータ構造を使用する必要があります。
つまり、データ構造は生成された大量のデータを管理するために必要であり、アルゴリズムの効率を高める上で重要な要素です。
データ構造の設計はすべての基礎・土台となっています。
データ構造はどのようなものがあるのか学んでいきましょう。
8つのデータ構造
1. 配列(Array)
最も単純なデータ構造の1つである配列は、メモリに順番に格納される同じ変数型のアイテムのコレクションです。
これは最も一般的で単純なデータ構造の1 つです。
配列内の各項目には0から始まるインデックスが付けられ、各項目は要素と呼ばれます。
上記の画像では配列の長さは6となります。
インデックス番号3の値は1となっています。
配列は、同じデータ型の値や変数(要素と呼ばれる)を含み、サイズが固定されているので配列のサイズを変更することはできません。
つまり、Javaでは配列のサイズを変更できないことに注意することが重要です。
またJavaでは配列の全ての値は整数型である必要があります。
動的サイズの場合は、リストを使用することをお勧めします。
配列はより複雑なデータ構造を構築するための構造体としてよく利用されまた、配列はソートアルゴリズムにも使用されます。
2. リスト(list)
リンクされたリストは、直線的に並べられた項目の列で、すべてが互いにつながっています。
つまり、データに順番にアクセスしなければならないので、データへのランダムアクセスは不可能となります。
リストの各要素は『ノード』と呼ばれ、各ノードにはキーとポインタが含まれます。
ポインタは、『next』と呼ばれる次のノードに移動しシーケンスは『head』で始まり、リスト内の最初の要素に移動します。
このリストの最後の要素は『tail』と呼ばれます。
個別にリンクされたリストを作成すると、各項目をheadからtailまで順方向にたどることができます。
同様に、前方にも後方にも走査できる2重リンクリストを作成することも可能です。
そして最後に、末尾の次のポインタが頭を指し、その逆もまた然りで、円を形成する円形リンクリストを作成することができる。
リンクされたリストと従来の配列はどちらも、シリアル化されたストレージを備えた線形データ構造です。
もちろん、違いもあります。
一方的な連結リストにはさまざまなメソッドがあります。
例えば、『indexOf』でノードのインデックスを返すメソッドや『remove』で特定のノードを削除したりなどです。
リンクされたリストはPCの場合では、Alt + Tab を使用してプログラムを切り替える際のシンボルテーブル管理に使用されます。
3. スタック(Stack)
スタックは、その名の通りで背の高いコンテナの中にエレメントを積み重ねてるようなものです。
追加したり削除したり(後入れと先出し)できるアイテムのコレクションのようなものだと考えてください。
スタックは、LIFO (Last In First Out) 構造として知られています。
最後に置かれた要素が最初にアクセスできるのです。
新しい要素をスタックの一番上に『push』することもできますし、『pop』してスタックの一番上にある、最後に挿入された要素を削除することもできます。
スタックは一般的に、数式の解析や評価、再帰的プログラミングにおける関数呼び出しの実装に使用されたりします。
4. キュー(Queue)
キューはスタックと似たような機能を持ちますが、LIFO構造ではなく、FIFO(First In First Out)構造になっています。
待ち行列について考える最も簡単な方法は、何かしらの建物に入るのを待っている人々の行列を考えることです。
列の先頭にいる人が先に建物に入り、最後尾の人が最後に入ることになります。
この構造体では、要素を『enqueue』することができます。
つまり、要素をキューの最後尾に挿入することです。
また要素を『dequeue』することも可能です、これは要素をキューの先頭から削除することを意味しています。
キューは、マルチスレッドでスレッドを管理するためによく使用され、優先キューイングシステムを実装するために使用されます。
5. ハッシュテーブル(Hash table)
ハッシュテーブルに飛び込む前に、ハッシュとは何かを理解することが不可欠です。
ハッシュテーブル構造は、『各値』と『キー』を関連付けて格納します。
そのため、ハッシュはキーを使って効率的に値を調べることができます。
つまり、キーと呼ばれる一意のインデックスにオブジェクトを割り当てるプロセスとなっています。
似たようなオブジェクトの集まりから特定のオブジェクトを識別するのが容易なため、データサイズに関係なく、挿入や検索を効率的に行うことができる方法となります。
例えば、どこかのアカウントに登録します。登録すると一意のユーザーID番号が割り当てられます。
このID番号は、あなたのユーザー記録に関する情報を検索するために使用できるキーとなります。
ハッシュテーブルは、『ハッシュ関数』と呼ばれるものを使用し、任意のサイズのデータセットを固定サイズのデータセットに対応付けます。
ハッシュテーブルは、要素を配列に格納し、それらをキーで識別することによって実装されます。
ハッシュ関数はキーを受け取り、値が格納されているインデックスを返します。
そのハッシュ関数が返す値は、『ハッシュ値』として知られています。
そのため、キーをハッシュ関数に入力すると、関連付けられた要素を識別する同じインデックスが常に返されます。
さらに、ハッシュ関数が既に使用されているインデックスを返す一意のキーを受け取った場合、連結リストを使用して要素のチェーンを作成できます。
ハッシュテーブルは、データベースのインデックスの作成や連想配列の作成およびセットの作成によく使われます。
6. ツリー(tree)
ツリーは、各項目がリンクされているため、リンクリストに似た構造をしています。
ですが、ツリーでは項目は階層的にリンクされ、祖先からあなたまでの家系図のような視覚的な表現だと思って下さい。
ツリーデータ構造は、配列、スタック、およびキューとは対照的に、非線形の多層データ構造です。
この構造は、挿入および検索操作中に非常に効率的です。
ツリーには様々な種類があり、それぞれが異なる用途に適しています。
7. 二分探索木(Binary search tree)
二分探索木は、ノードで構成される二分木データ構造です。
ノードとその左右の枝を分析するために使用される高度なアルゴリズムとなっています。
二分探索木はヒープまたは二分ヒープとも言い、ツリーのノードは親子関係で表現されます。
ノード内の値を適宜に配置することができます。
ヒープは木として表現されるが、バイナリ配列として表現することもできます。
ヒープには2つの種類があり、次のプロパティで配置されます。
・左のサブノードには、常に親ノードよりも小さい値が含まれます。
・右側のサブノードには、常に親ノードよりも大きな値が含まれます。
・両方のサブノードも二分探索木になります。
この構造を利用したソートアルゴリズムが『ヒープソート』となります。
優先キューを作成するアルゴリズムや、配列の最小値や最大値を求めるためのアルゴリズムによく使われたり、また3Dゲームでレンダリングする必要があるオブジェクトを決定するためにも使用されます。
階層データは非常に一般的であるため、このデータ構造はエンジニアのプロジェクトで広く使用されています。
一般的な操作を下記に示します。
・add: ノードをツリーに挿入します。
・ findMin: 最小ノードを取得
・ findMax: 最大ノードを取得
・ find: 特定のノードを検索
・ isPresent: 特定のノードの存在を判断します。
・ remove: ツリーからノードを削除
8. グラフ(Graph)
グラフは、リンクまたはエッジで結ばれた有限のノード集合からなる抽象的で非線形なデータ構造です。
ノードは『頂点』と呼ばれることもあり、値を含む一方、エッジはグラフ内の2つのノードを結ぶ単なる線または円弧です。
リンクに方向があるかどうかによって、グラフをさらに 2 つのグループに分けることができます
つまり、有向グラフと無向グラフとなります。
また、隣接行列がありこれはノードを行と列で示します。
行と列の交点は、ノード間の関係を解釈します。
グラフは、回路網や都市内の経路などのネットワークを表現するためによく使用され、グラフは実世界の問題を解くのに適しているが、デジタル・ネットワークの表現にも利用できます。
例えば、FacebookやInstagramでは、各ユーザーをノード(または頂点)で表現することができます。
それぞれ各頂点はそのユーザーに関する情報を含み、各エッジは別のユーザーとのつながりを表すことができます。
データ構造をより深く学びたいと考えている場合には、基本的なデータ構造と高度なデータ構造に分かれていることに注意してください。
先述で学んできたデータ構造は基本的な構造です。
本日では解説しませんが、例えば『トライ』『K次元の木』『素集合』などのさまざまな高度なデータ構造もございます。
アルゴリズムとは？
アルゴリズムは私たちが行うすべてのことです。
しかし、数学やプログラミングに傾倒していない人にとって、『アルゴリズム』という用語はあまり明確ではありません。
9世紀前半(西暦780年または800年)に数学と天文学の分野で偉大な足跡を残した『アル＝フワーリズミー』氏は『アルゴリズム』という用語の作成者つまり語源と言われている人物です。
9世紀といったら日本では平安時代です。
アルゴリズムは元々、ラテン語のAlgoritmi de numero Indorum(アルゴリトミ・デ・ヌーメロ・インドルム)というラテン語で西洋に訳されておりました。
その翻訳は、通称『アルゴリトミ』と呼ばれ何百年と長い間ヨーロッパ各国の大学などの教科書に用いられていました。
コンピューターを使用したアルゴリズムが最初に注目を集めたのは20世紀半ば頃です、軍がたとえば移動物体にミサイルを向ける場所を決定するための公式を書き始めたときです。
アルゴリズムの用語は、人工知能の台頭のおかげで流行語になりました。
その後、この概念はビジネス管理に移行し、コンピューターは給与などを管理するための計算式を実行し、科学では空の動きを追跡しました。
アルゴリズムとは、問題を解決したり特定のタスクを実行したりするために設計された、段階的な指示の集合体です。
タスクは、2つの数字の掛け算のような簡単なものから、音楽ファイルの再生のような複雑なものまであります。
コンピュータアルゴリズムは、入力と出力を介して機能します。
入力を受け取り、アルゴリズムの各ステップをその情報に適用して出力を生成します。
別の言い方をするのであれば、コンピューターの世界でのアルゴリズムとは、何をする必要があるかだけでなく、それをどのように行うかを定義する一連の命令です。
これは順序付けられた方法で従わなければならない一連の正確な指示となります。
つまり、コンピュータプログラミングではアルゴリズムは関数として作成されることがもっとも多いです。
プログラマまたはコンピューター科学者は、アルゴリズムを使用して、先月の売上高をデータベースに照会し、前月と昨年の同じ月と比較して、棒グラフで表示するように自分のマシンに指示する事は容易です。
複数のアルゴリズムを組み合わせると、機能するコンピュータープログラムができあがります。
それを行うための多数な種類のアルゴリズムがあります。
・ 数値アルゴリズム
・ 代数アルゴリズム
・ 順次アルゴリズム
・ 運用アルゴリズム
・ 理論アルゴリズム
コンピューティング分野では、ほとんどのアルゴリズムがデータ管理と分析の問題を解決する傾向があります。
アルゴリズムを形成するフローチャートの形状は、命令の巨大な『ツリー』になり、その複雑さによっては驚くべき結果をもたらすことさえあります。
覚えておくべきアルゴリズム
経験の浅い人には、経験豊富なプログラマがコードを暗記しているように見えることがあります。
使用するすべてのコードを覚えておくことは非現実的であり、問題をより効果的に解決するのに役立ちません。
プログラマはコードを暗記するのではなく、日常的に使用するコードに慣れ、その他すべてについて公式ドキュメントを参照します。
またプログラミング中に問題が発生した場合は80%の方はStack Overflowにアクセスします。
コードを書くほど自然に身につくものであるべきです。
プログラマはコードを暗記することを心配する必要はありません、コードを書けば書くほど自然に覚えやすくなります。
プログラマは、コード行を覚えること以外にも心配する他のことがたくさんあります。
しかし、基本的に面接官はデータ構造とアルゴリズムの使用方法を理解している資格のある候補者を求めています。
プログラミングには、分析、アルゴリズムの生成、アルゴリズムの精度とリソース消費のプロファイリング、およびアルゴリズムの実装などのタスクが含まれます。
検索アルゴリズム
検索アルゴリズムには、下記2種類の検索アプローチがあります。
・ 線形検索アプローチ
簡単なアプローチは、線形検索を行うことです。
線形検索の時間計算量はO(n) となっています。
同じタスクを実行する別の方法は、バイナリ検索を使用することです。
・ 二分探索(線形データ構造)
二分探索は、検索間隔を繰り返し半分に分割することにより、ソートされた配列で使用される検索アルゴリズムとなっています。
二分探索の考え方は、配列がソートされているという情報を使用して、時間の複雑さをO(log n)に減らすことです。
可能な項目を 1 つに絞り込むまで、項目を含む可能性のあるリストの部分を繰り返し半分に分割することです。
二乗によるべき乗
2乗または2進指数によるべき乗は、O(log2N)の数値の大きな正の整数乗を高速に計算するための一般的な方法です。
それだけでなく、この方法は多項式や正方行列のべき乗の計算にも使用されます
ソートアルゴリズム
コンピューターサイエンスの分野では、並べ替えは最も徹底的に研究されている概念の１つです。
単純な概念はリストの項目を特定の順序で並べることです。
すべての主要なプログラミング言語には組み込みの並べ替えライブラリがありますが、それらがどのように機能するかを知っていれば便利となります。
要件に応じて、下記のいずれかを使用することができます。
・ マージソート(Merge Sort)
・ クイックソート(Quick Sort)
・ ヒープソート(Heap Sort)
・ カウンティングソート(Counting Sort)
これらは、要件に応じて使用できるソートのタイプとなります。
要件に応じての例では、例えばECサイトでの価格順、人気順などでの並び替えなどになります。
ハッシング
ハッシュ ルックアップは、現在『キー』または『ID』で適切なデータを見つけるために最も広く使用されている手法です。
インデックスによってデータにアクセスします。
以前は、ソート + バイナリ検索に依存してインデックスを探していましたが、現在はハッシュを使用しています。
データ構造は、キーを値に効率的にマップする『Hash-Map』または『Hash-Table』、『Dictionary』と呼ばれます。
キーを使用して値の検索を実行可能です。
適切なハッシュ関数の選択は、構造によって異なってきます。
文字列の照合と解析
パターンマッチング/検索は、コンピューターサイエンスにおける最も重要な問題の1 つとなっています。
これは多くの調査が行われていますが、プログラマーにとって必要な基本的なものは2つのみです。
・ KMPアルゴリズム(文字列マッチング)
Knuth-Morris-Pratt(KMP)アルゴリズムは、長い文字列内の短いパターンを照合する必要がある場合に使用されます。
ドキュメント内のキーワードを『Ctrl + F』すると、ドキュメント全体でパターンマッチングが実行されます。
・ 正規表現(文字列解析)
多くの場合、定義済みの制限を解析して文字列を検証する必要があります。
これは、URLの解析と照合のためにWeb開発で頻繁に使用されます。
動的計画法(DP)
動的計画法(DP) は、複雑な問題をより単純な部分問題に分解することによって解決する方法です。
プログラマーは部分問題を解決し、その結果を記憶し、それらを使用して複雑な問題を迅速に解決します。
アルゴリズムは何に使用される？
非常に複雑なアルゴリズムの1 つは、 Facebookのニュースフィードを管理するアルゴリズムです。
これは、ユーザーがスクロールするときにどのコンテンツを表示するかを決定するためにFacebookが使用する方程式です。
言い換えれば、ニュースフィードの内容を決定するための一連の指示です。
例えばGoogleで洋服を検索したとします。
検索結果が表示され、何かを達成したような気分になったあなたは、一息ついてFacebookやInstagramに登録している友達を確認します。
ログインすると、洋服関連の広告がFacebookまたはInstagramで表示されているではありませんか。
一体どうなっている？これは、デジタルマーケティングのアルゴリズムで、あなたの過去の検索結果に基づいて広告を表示するタスクを、アルゴリズムによって自動化しているのです。
自動化が設定されたルールに従ってタスクを完了することによって機能します。
これらのルールがアルゴリズムを形成します。
Facebookタイムラインアルゴリズムの他に有名なのは、GoogleによるPageRankです。
世界で最も広く使用されているものの 1 つです。
これは、Googleが検索エンジンによってインデックス付けされたドキュメントの重要性を判断するために使用する一連のアルゴリズムです。
つまり、Google検索を行う際に、結果が表示される順番を決める要素の1つです。
Google PageRankアルゴリズムが作成された時は、最新のアルゴリズムとしての転機とも言えます。
ページ内の情報だけに頼って検索用語との関連性を判断する代わりに、検索エンジンアルゴリズムは、最良の結果を表示するのに役立つ他の多くのシグナルを組み込みました。
最も注目すべきは、その記事を指している他のリンクの数、およびそれらのページを指しているリンクの数に基づく、それらの記事の評判の良さです。
私たちが学んだように、アルゴリズムは通常はコンピューターが何をすべきかを理解するために『非常に詳細』に書かれている必要があります。
ただし、アルゴリズムを作成する人が機械学習つまり一種の人工知能を組み込んで、最も洗練されたアルゴリズムを作成する場合は、そうではありません。
これは、最も複雑なアルゴリズムは機械学習を使用しているという事です。
機械学習とは、何をすべきかを指示される代わりに、コンピューターが独自のアルゴリズムを発見することです。
従来のアルゴリズムでは、プログラマーが手順のすべてのステップを記述してきました。
しかし、人工知能によって開発されたアルゴリズムでは、目標として終点が与えられると、プログラムはその方法を理解するために自分自身で見つけ出します。
機械が学習しているという事です。
つまり人間の介入をほとんど必要とせず、非常に強力で非常に複雑なアルゴリズムを作成できます。
このように、アルゴリズムはITおよびコンピューティングのあらゆる分野で使用されています。
データを操作および処理し、さまざまな方法で計算やアクションを実行できます。
アルゴリズムを記述するための明確に定義された標準はありません。
むしろ、問題とリソースに依存しておりアルゴリズムは、特定のプログラミングコードをサポートするために作成されることはありません。
すべてのプログラミング言語がループ (do・for・while)や(if-else) フロー制御などの基本的なコード構造を共有していることはわかっています。
これらの共通構造を使用して、アルゴリズムを記述できます。
アルゴリズムは段階的に記述しますが、常にそうであるとは限りません。
アルゴリズムの作成はプロセスであり、問題領域が明確に定義された後に実行されます。
データ構造とアルゴリズムを練習するための最適な言語は『C++』または『Java』が強く推奨され、好まれます。
言語はデータ構造とはほとんど関係がないため、任意の言語を選択可能ですが、それがOOP言語であることを確認してください。
アルゴリズムは下記のような、さまざまな目的や動作に使用されます。
・挿入する
アルゴリズムを使用して、指定されたデータ項目コレクションに新しいデータ構造に追加します。
・削除
アルゴリズムを使用して、データアイテムのコレクションから既存のデータアイテムを削除します。
トラバーサルを行います。各データ項目に一度だけアクセスし、処理する。
・検索
アルゴリズムを使用し、データ項目が与えられたデータ項目のコレクションに存在する場合、その場所を見つける、つまりデータ内の項目を検索。
・ソート(並べ替え)
アルゴリズムを使用し数値データの昇順、降順、英数字データの辞書順など、特定の順序でデータ項目を並べ替えます。
優れたコードを作成する熟練したプログラマになりたいのであれば、データ構造とそれらに対してさまざまな操作を実行する方法を理解する必要があります。
そして、アルゴリズムは決して魔法のようなものではなく、アルゴリズムは一連の命令を意味するだけであることを忘れないでください。
そして人間はアルゴリズムを作成していきます。
つまり100%完璧ではなく、欠陥がある可能性があるという事になります。
最後に
データ構造はデータを保持するために使用され、アルゴリズムはそのデータを使用して問題を解決するために使用されます。
アルゴリズムは不完全かもしれませんが、それでも私たちの世界を変えています。
アルゴリズムは定着してきています。
実際、アルゴリズムは人工知能などの潜在的に強力なテクノロジーの中心にあります。
アルゴリズムはすでに自動学習技術、つまり『機械学習』の基礎となっているため、毎日新しい機能で私たちを驚かせています。
しかし、それらをどのように設計するかそしてそれらの存在をどの程度受け入れるかは、私たち次第です。
将来、アルゴリズムが私たち人間にとって良いものである事を願いながら学んでいきましょう。
データ構造とアルゴリズムに関しましてはまた続きを別途記事に致します。
本日は以上となります。
最後までこの記事を読んで頂きありがとうございます。