TypeScript中級

中級 TypeScriptで学ぶデータ構造｜アンチパターン編

 

導入

データ構造はプログラミングの根幹を成す要素であり、効率的なアルゴリズムの実装に不可欠です。特に中級エンジニアにとって、データ構造の選定や実装におけるアンチパターンを理解することは、実務におけるパフォーマンス向上に繋がります。本記事では、TypeScriptを用いた具体的なケーススタディを通じて、よくある失敗例とその改善策を探ります。

教科書レベルの解説（データ構造）

重要な概念の整理

データ構造は、データを効率的に管理・操作するための手法です。リスト、スタック、キュー、ツリー、グラフなど、様々な形態があります。これらのデータ構造は、特定のニーズに応じて適切に選択されるべきです。たとえば、頻繁にデータを追加・削除する場合は、リンクリストが適しているかもしれません。一方、データの検索が主な目的であれば、バイナリツリーの使用が考えられます。

コード例（TypeScript）


class Node {
    constructor(public value: number, public next: Node | null = null) {}
}

class LinkedList {
    private head: Node | null = null;

    add(value: number): void {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    find(value: number): Node | null {
        let current = this.head;
        while (current) {
            if (current.value === value) {
                return current;
            }
            current = current.next;
        }
        return null;
    }
}

コードの行ごとの解説

  1. Nodeクラス: 各ノードは値と次のノードへの参照を持ちます。
  2. LinkedListクラス: リスト全体を管理し、ノードの追加や検索を行います。
  3. addメソッド: 新しいノードをリストの末尾に追加します。リストが空であれば、ヘッドを新しいノードに設定します。
  4. findメソッド: 指定された値を持つノードをリスト内で検索します。

アンチパターン編

このコードには、いくつかのアンチパターンが存在します。特に「find」メソッドにおける線形探索は、リストが大きくなるとパフォーマンスが低下します。リストの要素数が増えるほど、検索に要する時間が比例して増加します。これに対処するためには、データ構造の見直しが必要です。

例えば、検索を頻繁に行うシナリオでは、配列やハッシュテーブルの使用が考えられます。ハッシュテーブルを使用すれば、平均的な検索時間をO(1)にすることが可能です。以下に、ハッシュテーブルを用いた改善例を示します。

改善されたコード例（TypeScript）


class HashTable {
    private table: { [key: number]: boolean } = {};

    add(value: number): void {
        this.table[value] = true;
    }

    find(value: number): boolean {
        return this.table[value] || false;
    }
}

このハッシュテーブルの実装では、データの追加と検索が効率的に行えます。

まとめ

  • データ構造の選定は、使用ケースに応じて慎重に行う必要があります。
  • アンチパターンを理解し、改善策を講じることで、プログラムのパフォーマンスを向上させることが可能です。
RELATED POST