なぜソフトウェアエンジニアにとって「アルゴリズムとデータ構造」は重要なのか？

こんにちは！

パーソルプロセス＆テクノロジー株式会社 プロダクト統括部developmentグループの森です。
普段は、TIMO Meetingというミーティングテック領域のプロダクトを開発しているエンジニアです。

最近のマイブームはAI英会話アプリ「スピークバディ」で、毎日スマホに話しかけてます。オンライン英会話は続かなかったけど、AI英会話アプリなら続けられそう😂

さて今回は「アルゴリズムとデータ構造」について書きたいと思います。
「アルゴリズムとデータ構造」と聞くと競技プログラミングやコーディング試験を思い浮かべる方が多いのではないでしょうか。競技プログラミングで有名なサイトだとLeetCodeやCodeChef、国内産だとAtCoderがあります。
私はLeetCodeを利用していて、毎日1問か2問解くようにしています。

アルゴリズムってなに？

アルゴリズムは簡単にいうと「あることを達成するための手順」のことです。例えば「朝起きて→着替えて→朝ごはんを食べて→電車で会社へ行く」という日常の行動もある種のアルゴリズムです。コンピュータの世界では、データ処理、数値演算などの問題を解決するための手順をアルゴリズムと呼びます。また、アルゴリズムは無数に存在し、どのアルゴリズムを選択するかによって問題を解決する計算時間が大きく変わってきます。

なぜ「アルゴリズムとデータ構造」が重要なのか

GAFAMをはじめとするビックテック企業はエンジニアの採用フローに必ず「アルゴリズムとデータ構造」問題のコーディング試験を導入しています。なぜビックテック企業は「アルゴリズムとデータ構造」を重要視するのでしょうか。その理由は以下の３つが考えられると思います。

1. 新しい言語の学習コストを大幅に短縮できる

2. 処理速度とメモリ使用量の最適化を行うことができる

3. 問題解決能力を向上させ、複雑な課題を効率的に解決することができる

１. 新しい言語の学習コストを大幅に短縮できる

最近だとReactのような技術が魅力的ですが、常に新しい技術が登場し、流行の技術は移り変わりが激しくなっています。特定の技術に特化したスキルは、すぐに陳腐化してしまう可能性があります。
一方で「アルゴリズムとデータ構造」はどの言語でも共通する基礎となる不変的な知識です。
なので共通する不変的な基礎知識を理解していれば、言語特有の構文や規則に惑わされることなく、問題の本質に焦点を当てることができます。そのため、新しい言語を効率的に学習し、すぐに使いこなせるようになるのです。

現代のソフトウェア開発において、変化に適応できる能力は不可欠だと思います。アルゴリズムとデータ構造を理解することは、変化の激しい環境でも活躍できるエンジニアになるための重要なステップだと思います！

HireRoo代表 葛岡さんの「コーディング試験はなぜ重要か」の記事で不変的な知識について分かりやすく説明されているので、是非読んでみてください！

コーディング試験はなぜ重要かを真剣に考えてみた（ノンバイアス） | HireRoo Tech Blogs

２. 処理速度とメモリ使用量の最適化を行うことができる

アルゴリズムとデータ構造は、ソフトウェア開発において処理速度とメモリ使用量の最適化を行うために重要です。適切なアルゴリズムとデータ構造を選択することで、プログラムのパフォーマンスを大幅に向上させることができます。

O(ビッグオー)表記とは

アルゴリズムを評価する際は、以下の２つの計算量で評価されます。

時間計算量
プログラムの実行に必要な時間を評価する。プロセッサをどれだけ利用するかを見積もる。
空間計算量
プログラムの実行に必要な記憶領域を評価する。メモリをどれだけ利用するかを見積もる。

アルゴリズムの効率性を評価する指標として、O(ビッグオー)表記がよく用いられます。ビッグオー表記は、O(n)やO(n^2)のようにnをデータの入力サイズとした関数で、アルゴリズムの実行時間の漸近的な挙動を表します。

例えば、「n件のデータを小さい順にソートしてください。nは最大でも10000件とする」という問題があるとします。問題がO(n^2)とすると、計算量はn^2に比例することになります。
O(n^2)のアルゴリズムは、データ量が10倍になれば計算量は100倍になります。上記の問題のデータ量は最大で10000なので、最悪の場合は約100000000の計算量になります。
O(n log n)のアルゴリズムではどうでしょうか。最悪の場合は約130000の計算量です。
このようにアルゴリズムが違うだけで計算量が大きく違います。
以下はデータ入力nに対して各計算量を表したグラフになります。

計算量の比較

ビッグオー表記を理解していると、自分が書いたアルゴリズムの処理速度が速いか遅いかを一定程度判断するのに役立ちます。
※注意：実際の実行時間は、コンピュータの性能やデータの特性も影響するので、ビッグオー表記だけではアルゴリズムの処理速度を完全に判断することはできません。

バブルソートとマージソートを実装してみる　

では、Javaでバブルソートとマージソートのアルゴリズムを書いてみます。
バブルソートは 、データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列を並び替えるというアルゴリズムです。
データの入力サイズ n に対して実行時間は O(n^2)になります。

public class BubbleSort {
  public static void sort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (array[j] > array[j + 1]) {
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    int[] array = { 5, 2, 4, 6, 1, 3 };
    sort(array);
  }
}

マージソートは、並べ替えるデータを一度ばらばらにして、それを再びマージする過程で並べ替えると、最終的に一つのデータに戻るときには、自然に並べ替えられているというアルゴリズムです。
データの入力サイズ n に対して実行時間は O(n log n)になります。

public class MergeSort {

  public static int[] sort(int[] array) {
    int n = array.length;
    if (n <= 1) {
      return array;
    }

    int mid = n / 2;
    int[] left = sort(Arrays.copyOfRange(array, 0, mid));
    int[] right = sort(Arrays.copyOfRange(array, mid, n));

    return merge(left, right);
  }

  private static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result[k++] = left[i++];
      } else {
        result[k++] = right[j++];
      }
    }

    while (i < left.length) {
      result[k++] = left[i++];
    }

    while (j < right.length) {
      result[k++] = right[j++];
    }

    return result;
  }

  public static void main(String[] args) {
    int[] array = { 5, 2, 4, 6, 1, 3 };
    int[] sortedArray = sort(array);
  }
}

このように、アルゴリズムを変えるだけで、処理速度が大幅に変化することが分かります。適切なアルゴリズムとデータ構造を選択することで、プログラムのパフォーマンスを大幅に向上させることができます。

３. 問題解決能力を向上させ、複雑な課題を効率的に解決することができる

アルゴリズムとデータ構造は、問題解決能力を向上させ、複雑な課題を効率的に解決するために重要です。これらの知識を理解することで、以下のようなメリットを得ることができます。

効率的な問題解決
最適なアルゴリズムとデータ構造を選択することで、問題を効率的に解決することができます。
複雑な問題への対応
アルゴリズムとデータ構造を組み合わせることで、複雑な問題をより簡単に解決することができます。
汎用的な問題解決能力
アルゴリズムとデータ構造は、プログラミング言語に依存しない普遍的な知識体系です。そのため、これらの知識を習得することで、様々な問題に応用することができます。

探索アルゴリズム

データの検索は、プログラミングにおいて非常に重要なタスクです。データ量が少ない場合は、単純な線形探索でも十分ですが、データ量が増えるにつれて、探索速度が遅くなります。
そこで、二分探索のような効率的な探索アルゴリズムを用いることで、データ量に関係なく、高速な検索を実現することができます。
二分探索の実行時間は O(log n) です。

グラフアルゴリズム

グラフは、ネットワークや地図など、様々な問題を表現するために用いられるデータ構造です。グラフアルゴリズムを用いることで、最短経路検索や巡回セールスマン問題などの複雑な問題を効率的に解決することができます。
実行時間はO((V + E) * log V) となります。V は頂点の数、E は辺の数です。

探索アルゴリズムのサンプルコード

public class BinarySearch {

  public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
      int mid = (left + right) / 2;

      if (array[mid] == target) {
        return mid;
      } else if (array[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  }

  public static void main(String[] args) {
    int[] array = { 1, 3, 5, 7, 9 };
    int target = 5;

    int index = binarySearch(array, target);

    if (index == -1) {
      System.out.println("The target value is not found.");
    } else {
      System.out.println("The target value is found at index " + index);
    }
  }
}

勉強方法について

ここまでアルゴリズムとデータ構造の基礎知識を理解することの重要性やメリットについてまとめました。
最後に私が行っている勉強方法について紹介したいと思います。

参考書としては以下の書籍で一通り勉強しました。
米国でベストセラー書(Cracking the Coding Interview: 189 Programming Questions and Solutions)の日本語版です。

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~ | Gayle Laakmann McDowell, 岡田 佑一, 小林 啓倫 |本 | 通販 | Amazon

その後は、LeetCodeを解くようにしています。

LeetCodeとは
登録者数500万以上のプログラミングスキルの向上に焦点を当てた競技プログラミング・コンテストサイトです。3094問の問題が公開されており、各問題にはジャンルごとのタグ、難易度、解法、ユーザー同士のディスカッションの場などが用意されています。

LeetCode - The World's Leading Online Programming Learning Platform

最後に

ここまで読んでいただきありがとうございます！
弊社は一緒に働いていただける方を募集中です！
就職/転職活動中や、まだ情報収集中の方、少しでも興味を持っていただけた方は、以下のアドレスに「note見た！」とご連絡いただけると幸いです💡
プロダクト推進部/採用担当アドレス：pdo_js@persol-pt.co.jp

パーソルプロセス＆テクノロジー株式会社 | 【ポジションサーチ／エンジニア】リモート・フレックス可／新規事業部門の自社プロダクト開発（※ご経験や適性に応じてポジションをご提案させて頂きます）