エンジニア実践的基礎: データ構造とアルゴリズム

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

データ構造とアルゴリズムとは

データ構造とアルゴリズムは、ソフトウェアエンジニアリングの基本です。データ構造はデータを保管するための箱で、箱の種類によってデータの保管方法や取り出し方が異なります。例えば、スタックとキューというデータ構造があります。これらは一見難しそうですが、実は身近なものです。スタックは食器棚のお皿をイメージしてください。

お皿が積み重なった状態がスタックです。最後に置いたお皿を取り出すには、一番上のお皿を確認するだけです。次のお皿を置くときも、上から重ねるだけです。お皿を取り出す際、一番上なら簡単ですが、真ん中や一番下のお皿を取り出すのは手間がかかります。このように、データの配置や取り出しにおける特徴がスタックにはあります。例えば、迷路で通った道を順にスタックに記録すれば、逆順に辿って元の場所に戻ることができます。

一方、キューはラーメン屋の行列です。

行列では、最初に並んだ人から順にラーメンを食べることができます。後から来た人は前の人を待たなければなりません。割り込みはマナー違反です。つまり、キューは入れた順に処理するデータ構造です。キューはとても便利で、システム設計でも頻繁に使われます。後回しにしたいことをキューに詰め込んでおけば、その順番で後から処理できます。この時間差がキューのポイントです。

アルゴリズムは、目的を達成するための手順です。例えば、辞書で「なすび」を調べるとき、どこから探しますか？先頭からページをめくる方法もありますが、真ん中あたりを開いて左右にページをめくる方が効率的です。この手順は「クイックソート」と呼ばれるアルゴリズムに似ています。先頭からめくるのも立派なアルゴリズムですが、効率の良し悪しがあります。真ん中から探す方が早く目的を達成できるので効率的です。アルゴリズムは日常生活で自然と実践しているもので、選択によって目的達成にかかる時間が大きく変わります。

データ構造とアルゴリズムは、お互いに補完関係にあります。アルゴリズムは手順の中でデータを箱に入れる必要があり、その箱がデータ構造です。逆に、データ構造も基礎的なデータ構造をアルゴリズムで加工して作られます。わかりやすく言えば、木の椅子は木の板という基礎的な材料を、4本の脚が座面を支えるという手順で組み合わせて作られます。データ構造とアルゴリズムは兄弟のように、お互いを支え合う存在なのです。