第4章アルゴリズムとデータ構造

アルゴリズムとデータ構造は、コンピュータ科学とプログラミングの重要な要素であり、それらを理解し学習することはプログラミングの基本スキルを向上させる上で極めて重要です。

アルゴリズム

アルゴリズムは、問題を解決するための手順の集まりです。アルゴリズムは、明確な開始と終了、そして明確な手順を持つべきです。同じ問題を解決するための異なるアルゴリズムは数多く存在し、それぞれのアルゴリズムは、実行時間やメモリ使用量といった異なる性能特性を持つことがあります。

アルゴリズムの例としては、ソートアルゴリズム（バブルソート、クイックソートなど）、検索アルゴリズム（二分検索、線形検索など）、グラフアルゴリズム（深さ優先探索、幅優先探索など）などがあります。

データ構造

データ構造は、データを効率的に管理、操作するための方式です。データ構造は、データの格納方法とデータ間の関係を定義します。それにより、データの挿入、削除、検索などの操作をより効率的に行うことが可能となります。主なデータ構造には、配列、リスト、スタック、キュー、ツリー、グラフ、ハッシュテーブルなどがあります。

例えば、配列は固定サイズの要素の集まりで、各要素はインデックスまたはキーでアクセスされます。一方、リスト（特に連結リスト）は動的にサイズが変わることができ、要素はノードとして格納され、各ノードは次のノードへの参照を持ちます。

アルゴリズムとデータ構造の関係

データ構造とアルゴリズムは、しばしば密接に関連しています。特定のアルゴリズムは、特定のデータ構造を使用してデータを操作します。例えば、深さ優先探索（DFS）アルゴリズムは、グラフやツリーというデータ構造を探索するために使用されます。同様に、バブルソートやクイックソートといったソートアルゴリズムは、配列やリストといったデータ構造に対して使用されます。

したがって、プログラミングを学ぶ際には、データ構造とアルゴリズムの両方を理解することが重要です。これにより、特定の問題に対して最適なデータ構造とアルゴリズムを選択でき、効率的かつ効果的なソフトウェアソリューションを作成する能力を身につけることができます。

データ構造の例

配列

同じ型の要素の集合で、各要素はインデックスによって識別されます。配列は固定長で、一度作成するとそのサイズを変更することはできません（動的配列はこの限りではありませんが、それは別のトピックです）。

以下に配列を使用する基本的な擬似コードを示します

// 配列の初期化
array myArray = new array[5] 

// 配列に値を設定する
myArray[0] = "Apple"
myArray[1] = "Banana"
myArray[2] = "Cherry"
myArray[3] = "Date"
myArray[4] = "Elderberry"

// 配列から値を取得する
print(myArray[1]) // "Banana"を出力します

// 配列をループで処理する
for i = 0 to myArray.length - 1
    print(myArray[i])
end for

上記の擬似コードでは、5つの要素を持つ新しい配列を作成し、各要素にフルーツの名前を割り当てています。次に、特定のインデックスでの値を取得し、配列のすべての要素を順番に出力するためのループを作成しています。

配列は、要素にランダムにアクセスするための時間複雑性がO(1)であるという優れた特性を持っています。つまり、任意のインデックスでの値の取得や設定は非常に高速に行えます。しかし、配列のサイズを変更することはできないため、動的に要素を追加したり削除したりするには、新しい配列を作成し要素をコピーする必要があります。これは時間とメモリの両方にコストがかかります。

通常、要素の集合を保持するデータ構造で、それぞれの要素は前後の要素への参照を持つことが一般的です。配列とは異なり、リストは動的にサイズを変更でき、データを追加または削除するのが容易です。最も一般的なリストの形式は、「連結リスト」です。これは要素（ノードとも呼ばれる）が次の要素への参照を持つ形式のリストです。

以下に連結リストを使用する基本的な擬似コードを示します

// ノードクラスの定義
class Node {
    var data
    var next
}

// リストの初期化
var head = null

// リストにノードを追加する関数
function addNode(data) {
    var newNode = new Node()
    newNode.data = data
    newNode.next = null

    if (head == null) {
        head = newNode
    } else {
        var current = head
        while (current.next != null) {
            current = current.next
        }
        current.next = newNode
    }
}

// リストからノードを探す関数
function findNode(data) {
    var current = head
    while (current != null) {
        if (current.data == data) {
            return current
        }
        current = current.next
    }
    return null
}

// リストにノードを追加
addNode("Apple")
addNode("Banana")
addNode("Cherry")

// リストからノードを探す
print(findNode("Banana")) // "Banana"ノードを出力

この擬似コードでは、最初にノードクラスを定義しています。各ノードは、データ部分と次のノードへの参照を持ちます。リストはヘッドノードから始まり、次のノードへの参照をたどることで全てのノードを訪れることができます。

リストは要素の挿入と削除が容易であるというメリットがありますが、要素へのランダムアクセスが配列よりも効率的ではないというデメリットもあります。リスト内の特定の要素にアクセスするには、リストの頭から始めてその要素を見つけるまでノードを逐次的にたどる必要があります。このため、特定の要素を検索する時間複雑性はO(n)となります。

スタック

スタックは「後入れ先出し」（Last In First Out, LIFO）という原則に基づくデータ構造の一つです。これは新しい要素がスタックの一番上に追加され、削除もまた最上部から行われるという意味です。一般的に、スタックには次の基本的な操作があります。

Push：スタックの一番上に新しい要素を追加します。
Pop：スタックの一番上の要素を削除し、その要素を返します。
Peek/Top：スタックの一番上の要素を返します（削除はしません）。
isEmpty：スタックが空かどうかを確認します。

以下にスタックの操作を行う基本的な擬似コードを示します

// スタックの実装
class Stack {
    constructor() {
        this.stack = []
    }

    push(item) {
        this.stack.push(item)
    }

    pop() {
        if (this.isEmpty()) {
            return "Stack is empty"
        }
        return this.stack.pop()
    }

    peek() {
        if (this.isEmpty()) {
            return "Stack is empty"
        }
        return this.stack[this.stack.length - 1]
    }

    isEmpty() {
        return this.stack.length == 0
    }
}

// スタックの使用例
var myStack = new Stack()

myStack.push(1)
myStack.push(2)
myStack.push(3)

print(myStack.peek()) // 3を出力
print(myStack.pop())  // 3を出力
print(myStack.peek()) // 2を出力

スタックは再帰、関数呼び出し、逆ポーランド記法など、多くのプログラミングタスクにおいて使用されます。また、深さ優先探索（DFS）などのアルゴリズムでも利用されます。。

キュー

キューは、先入れ先出し（FIFO: First In First Out）原則に基づいたデータ構造です。これは、最初に追加された要素が最初に削除され、新しい要素が絶えず追加される特性を持つ構造です。例えば、実生活の待ち行列（行列）や印刷ジョブの待ち行列などがキューの例です。

以下にキューを使用する基本的な擬似コードを示します

// キュークラスの定義
class Queue {
    var items = []

    // キューに要素を追加
    function enqueue(item) {
        items.push(item)
    }

    // キューから要素を取り出す
    function dequeue() {
        if (isEmpty()) {
            return "Queue is empty"
        } else {
            return items.shift()
        }
    }

    // キューが空であるかを確認
    function isEmpty() {
        return items.length == 0
    }

    // キューの先頭を確認
    function front() {
        if (isEmpty()) {
            return "Queue is empty"
        } else {
            return items[0]
        }
    }
}

// キューの使用例
var myQueue = new Queue()
myQueue.enqueue("Apple")
myQueue.enqueue("Banana")
myQueue.enqueue("Cherry")

print(myQueue.front()) // "Apple"を出力
print(myQueue.dequeue()) // "Apple"を出力
print(myQueue.front()) // "Banana"を出力

上記の擬似コードでは、最初にキュークラスを定義しています。このクラスはenqueueメソッド（キューに要素を追加する）、dequeueメソッド（キューから要素を取り出す）、isEmptyメソッド（キューが空であるかを確認する）、およびfrontメソッド（キューの先頭要素を確認する）を持っています。

キューは、要素の追加と削除がO(1)で実行できるため、高速に操作を行うことができます。ただし、ランダムアクセスは配列と比較して効率が悪く、キュー内の特定の要素にアクセスするためには先頭から順に追っていく必要があります。

ツリー

ツリーは、ノード（節点）とエッジ（辺）によって構成される階層的なデータ構造です。ツリーには「親」ノードがあり、それぞれの親ノードには0個以上の「子」ノードが存在します。ツリーは、ファイルシステム、DOM（Document Object Model）など、多くの実世界のシナリオで使用されています。

ツリーの最も一般的な形式の1つが「二分木」で、各ノードが最大2つの子ノードを持つツリーです。

以下に二分木を操作する基本的な擬似コードを示します

// ノードクラスの定義
class Node {
    var data
    var leftChild
    var rightChild
}

// 二分木の探索（深さ優先探索）
function search(node, target) {
    if (node == null) {
        return null
    } else if (node.data == target) {
        return node
    } else {
        var result = search(node.leftChild, target)
        if (result != null) {
            return result
        } else {
            return search(node.rightChild, target)
        }
    }
}

// ノードの作成と探索の例
var rootNode = new Node()
rootNode.data = "Apple"
rootNode.leftChild = new Node()
rootNode.leftChild.data = "Banana"
rootNode.rightChild = new Node()
rootNode.rightChild.data = "Cherry"

print(search(rootNode, "Banana"))  // "Banana"ノードを出力

この擬似コードでは、まずノードクラスを定義しています。各ノードはデータ部分と2つの子ノード（左と右）を持ちます。探索関数では、深さ優先探索（DFS）を使用して特定のノードを探しています。

ツリーの主なメリットは、階層的なデータを効率的に表現し管理することができることです。デメリットとしては、ツリー構造の操作が配列やリストよりも複雑であること、また適切なバランスが取れていない場合（例えば、一方向にしか枝分かれしないツリー）、ツリーの操作の時間複雑性が悪化することが挙げられます。

グラフ

グラフは、頂点（ノード）とエッジ（辺）で構成されるデータ構造です。グラフはツリーやリストの一般化された形で、頂点と頂点の間の関係を表現することができます。グラフは無向（エッジに方向性がない）または有向（エッジに方向性がある）であることがあります。

以下にグラフの基本的な表現と探索（幅優先探索）を示す擬似コードを示します

// グラフクラスの定義
class Graph {
    var adjacencyList = []

    // 頂点の追加
    function addVertex(vertex) {
        adjacencyList[vertex] = []
    }

    // エッジの追加
    function addEdge(v1, v2) {
        adjacencyList[v1].push(v2)
        adjacencyList[v2].push(v1)
    }

    // 幅優先探索
    function bfs(start) {
        var visited = []
        var queue = []
        queue.push(start)

        while (queue.length > 0) {
            var vertex = queue.shift()
            if (!visited[vertex]) {
                visited[vertex] = true
                print(vertex)
                for (var neighbor in adjacencyList[vertex]) {
                    queue.push(neighbor)
                }
            }
        }
    }
}

// グラフの作成と探索の例
var myGraph = new Graph()
myGraph.addVertex("A")
myGraph.addVertex("B")
myGraph.addVertex("C")
myGraph.addEdge("A", "B")
myGraph.addEdge("A", "C")

myGraph.bfs("A")  // "A", "B", "C"を出力

上記の擬似コードでは、まずグラフクラスを定義しています。このクラスはaddVertexメソッド（頂点を追加する）、addEdgeメソッド（エッジを追加する）、およびbfsメソッド（幅優先探索を行う）を持っています。

グラフは、ネットワークのモデリング、最短経路問題など、多くの実世界の問題に対する解を表現するために使用されます。しかし、グラフの操作は他のデータ構造に比べてより複雑であり、特にサイクルの存在やエッジの重みなどを考慮に入れるとなると、更に複雑性が増します。

ハッシュテーブル

ハッシュテーブルは、キーと値のペアを保存する効率的なデータ構造です。ハッシュテーブルは「ハッシュ関数」を使って、キーを配列のインデックスに変換します。これにより、特定のキーに関連付けられた値を迅速に検索、追加、または削除することが可能になります。

以下にハッシュテーブルの基本的な実装を示す擬似コードを示します

// ハッシュテーブルクラスの定義
class HashTable {
    var size
    var table

    function HashTable(n) {
        size = n
        table = new Array(n)
    }

    // ハッシュ関数
    function hash(key) {
        var hash = 0
        for (var i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * i) % size
        }
        return hash
    }

    // 値のセット
    function set(key, value) {
        var index = hash(key)
        table[index] = value
    }

    // 値の取得
    function get(key) {
        var index = hash(key)
        return table[index]
    }
}

// ハッシュテーブルの作成と操作の例
var myTable = new HashTable(10)
myTable.set("apple", "red")
myTable.set("banana", "yellow")
myTable.set("cherry", "red")

print(myTable.get("apple"))  // "red"を出力
print(myTable.get("banana"))  // "yellow"を出力

アルゴリズムの例

ソート

ソートは、リストまたは配列内の要素を特定の順序（昇順または降順など）に配置するアルゴリズムです。ソートには様々なアルゴリズムが存在しますが、ここではシンプルな「バブルソート」について説明します。

バブルソートは、隣接する2つの要素を比較し、その順序が間違っている場合に交換することを繰り返すことでリストをソートします。

以下にバブルソートの擬似コードを示します

function bubbleSort(arr) {
    var n = arr.length
    for (var i = 0; i < n-1; i++) {
        for (var j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // swap arr[j] and arr[j+1]
                var temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
    return arr
}

// 配列のソートの例
var array = [64, 34, 25, 12, 22, 11, 90]
print(bubbleSort(array))  // [11, 12, 22, 25, 34, 64, 90]を出力

この擬似コードでは、まず外側のループ（iのループ）が配列の各要素を処理します。内側のループ（jのループ）は各パスで未ソートの部分を処理し、それぞれの要素を隣接する要素と比較して必要に応じて交換します。

バブルソートは実装が簡単な反面、時間的な効率性が低いというデメリットがあります。すなわち、最悪の場合および平均の場合、バブルソートの時間計算量はO(n^2)です。このため、大規模なデータセットに対しては他のソートアルゴリズム（例えばクイックソート、マージソートなど）が推奨されます。

探索

探索は、特定の条件を満たす要素をデータ構造（リストや配列など）から見つけるためのアルゴリズムです。以下では、「線形探索」と「二分探索」の2つの基本的な探索アルゴリズムを紹介します。

線形探索は最も基本的な探索アルゴリズムで、リストの先頭から順に要素を探し、目的の要素を見つけるかリストの末尾に達するまで探索を続けます。

以下に線形探索の擬似コードを示します

function linearSearch(arr, x) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] == x) {
            return i
        }
    }
    return -1
}

// 配列から要素を探す例
var array = [24, 18, 12, 9, 16, 66, 32, 4]
print(linearSearch(array, 16))  // 4を出力

一方、二分探索はソートされたリストや配列に対して行う探索アルゴリズムで、中央の要素をチェックして目的の要素がそれより大きいか小さいかを判断し、その結果に基づいてリストの検索範囲を半分にしていきます。

以下に二分探索の擬似コードを示します

function binarySearch(arr, x) {
    var left = 0
    var right = arr.length - 1
    while (left <= right) {
        var mid = left + (right - left) / 2
        if (arr[mid] == x) {
            return mid
        }
        if (arr[mid] < x) {
            left = mid + 1
        }
        else {
            right = mid - 1
        }
    }
    return -1
}

// ソートされた配列から要素を探す例
var array = [2, 3, 4, 10, 40]
print(binarySearch(array, 10))  // 3を出力

線形探索はシンプルでソートされていないリストでも使用できますが、リストが長いと効率が悪くなります。一方、二分探索はソートされたリストに対して非常に効率的ですが、ソートされていないリストには使用できません。

グラフ

グラフアルゴリズムは、ノード（または頂点）とエッジ（または辺）で構成されるデータ構造であるグラフを操作するためのアルゴリズムの一種です。以下では、「深さ優先探索 (DFS: Depth-First Search)」と「幅優先探索 (BFS: Breadth-First Search)」という2つの基本的なグラフ探索アルゴリズムを紹介します。

深さ優先探索 (DFS) は、グラフの探索において、まず深く探索し尽くすという戦略を採用したアルゴリズムです。探索は現在のノードから次に探索すべき未訪問のノードへ進み、そのようなノードがなくなれば探索の起点に戻ります。

以下にDFSの擬似コードを示します

function DFS(node, visited) {
    if (node is null or visited[node]) {
        return
    }
    visited[node] = true
    for each neighbor in node.neighbors {
        DFS(neighbor, visited)
    }
}

一方、幅優先探索 (BFS) は、現在のノードから直接繋がっている全てのノードを訪問した後に、それらのノードの隣接ノードを訪問するという探索戦略を採用します。BFSは一般にキューを用いて実装します。

以下にBFSの擬似コードを示します

function BFS(start) {
    var queue = empty queue
    var visited = set of nodes

    enqueue start into queue
    add start to visited

    while queue is not empty {
        node = dequeue from queue
        for each neighbor in node.neighbors {
            if neighbor not in visited {
                enqueue neighbor into queue
                add neighbor to visited
            }
        }
    }
}

DFSとBFSはそれぞれ異なる状況で使用されます。DFSは全てのパスを完全に探索するためのアルゴリズムで、パスベースの問題に有効です。一方、BFSは最短パス問題など、近いノードから順に探索することが有利な状況で使用されます。

第4章 アルゴリズムとデータ構造