JavaScript上級

上級 JavaScriptで実装するアルゴリズム演習集｜練習問題編

 

導入

本記事では、上級者向けのJavaScriptを用いたアルゴリズム演習に焦点を当てます。特に、実務において遭遇しやすいシチュエーションを選定し、その中でのアルゴリズムの実装を通じて、より深い理解を促進します。具体的には、複雑なデータ構造を扱う際の最適化手法や、パフォーマンスのボトルネックを回避する方法について考察します。

教科書レベルの解説（アルゴリズム演習）

重要な概念の整理

アルゴリズムを実装する際、特に注意が必要なのはデータ構造の選択です。例えば、リストやツリー、ハッシュテーブルなど、それぞれの特性を理解し、適切なものを選ぶことが、効率的な処理の鍵となります。加えて、時間計算量や空間計算量を考慮することも不可欠です。これにより、どのアルゴリズムが最適かを判断する材料となります。

コード例（JavaScript）


// グラフの最短経路を求めるDijkstraアルゴリズムの実装
class Graph {
    constructor() {
        this.nodes = new Map();
    }

    addNode(node) {
        this.nodes.set(node, []);
    }

    addEdge(startNode, endNode, weight) {
        this.nodes.get(startNode).push({ node: endNode, weight });
        this.nodes.get(endNode).push({ node: startNode, weight }); // 無向グラフ
    }

    dijkstra(start) {
        const distances = new Map();
        const visited = new Set();
        const priorityQueue = new PriorityQueue();

        for (let node of this.nodes.keys()) {
            distances.set(node, Infinity);
        }
        distances.set(start, 0);
        priorityQueue.enqueue(start, 0);

        while (!priorityQueue.isEmpty()) {
            const { element } = priorityQueue.dequeue();
            if (visited.has(element)) continue;
            visited.add(element);

            for (let neighbor of this.nodes.get(element)) {
                const newDistance = distances.get(element) + neighbor.weight;
                if (newDistance < distances.get(neighbor.node)) {
                    distances.set(neighbor.node, newDistance);
                    priorityQueue.enqueue(neighbor.node, newDistance);
                }
            }
        }
        return distances;
    }
}

class PriorityQueue {
    constructor() {
        this.items = [];
    }

    enqueue(element, priority) {
        this.items.push({ element, priority });
        this.items.sort((a, b) => a.priority - b.priority);
    }

    dequeue() {
        return this.items.shift();
    }

    isEmpty() {
        return this.items.length === 0;
    }
}

// 使用例
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'C', 4);
graph.addEdge('B', 'C', 2);
console.log(graph.dijkstra('A'));

コードの行ごとの解説

  1. Graphクラス: グラフを表現するためのクラス。ノードを追加し、エッジを設定するメソッドを持つ。
  2. addNodeメソッド: 新しいノードをグラフに追加する。
  3. addEdgeメソッド: ノード間にエッジを追加し、重みを設定する。
  4. dijkstraメソッド: Dijkstraアルゴリズムを用いて、指定したノードから他のノードへの最短距離を計算する。
  5. PriorityQueueクラス: プライオリティキューを実装し、ノードの探索順序を管理する。
  6. 使用例: グラフを作成し、Aから他のノードへの最短距離を計算して表示する。

練習問題編

以下に、実践的な問題を用意しました。各問題に対する模範解答と解説も記載しています。

  1. 問題1: 与えられた配列から重複を排除し、ユニークな値の配列を返す関数を実装してください。
    2. 
function uniqueArray(arr) {
    return [...new Set(arr)];
}

    この関数は、Setオブジェクトを利用して重複を排除しています。

  2. 問題2: 文字列を反転させる関数を実装してください。
    3. 
function reverseString(str) {
    return str.split('').reverse().join('');
}

    splitで文字列を配列に変換し、reverseで反転、その後joinで再度文字列に戻しています。

  3. 問題3: フィボナッチ数列を計算する再帰関数を実装してください。
    4. 
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

    再帰を用いたシンプルな実装ですが、計算量が指数関数的に増加するため、メモ化を考慮することが望ましいです。

  4. 問題4: 与えられた配列の最小値と最大値を求める関数を実装してください。
    5. 
function minMax(arr) {
    return { min: Math.min(...arr), max: Math.max(...arr) };
}

    スプレッド構文を利用して、配列の最小値と最大値を効率的に取得しています。

まとめ

  • データ構造の理解がアルゴリズムの効率に直結する。
  • 実務で役立つアルゴリズムを実装することで、問題解決能力を向上させる。
  • 練習問題を通じて、実際の業務に即したスキルを磨くことができる。
RELATED POST