Python中級

中級 Pythonで学ぶデータ構造｜ケーススタディ編

 

導入

データ構造はプログラムの効率性と可読性に直接影響を与える要素です。特に中級エンジニアにとって、適切なデータ構造の選択はプロジェクトの成功に欠かせません。本記事では、実務での具体的なシチュエーションを通じて、データ構造の選択とその実装について考察します。

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

重要な概念の整理

データ構造には、リスト、スタック、キュー、ツリー、グラフなど、さまざまな種類があります。それぞれのデータ構造は特定の用途に適しており、選択を誤るとパフォーマンスの低下や可読性の悪化を招く可能性があります。特に、データの挿入や削除が頻繁に行われる場合、選択するデータ構造がパフォーマンスに大きな影響を与えます。

コード例（Python）


class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, vertex1, vertex2):
        if vertex1 not in self.graph:
            self.graph[vertex1] = []
        self.graph[vertex1].append(vertex2)

    def dfs(self, start_vertex):
        visited = set()
        self._dfs_recursive(start_vertex, visited)

    def _dfs_recursive(self, vertex, visited):
        visited.add(vertex)
        print(vertex)
        for neighbor in self.graph.get(vertex, []):
            if neighbor not in visited:
                self._dfs_recursive(neighbor, visited)

# グラフの作成と探索
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.dfs('A')

コードの行ごとの解説

  1. Graphクラスを定義し、グラフを辞書で表現します。
  2. add_edgeメソッドで、2つの頂点を結ぶ辺を追加します。
  3. dfsメソッドで、深さ優先探索を開始します。
  4. _dfs_recursiveメソッドは再帰的に呼び出され、訪問した頂点を記録しながら隣接する頂点を探索します。
  5. 最後に、グラフを生成し、深さ優先探索を実行します。

ケーススタディ編

ある企業で、顧客の購入履歴をもとに推薦システムを構築するプロジェクトが始まりました。データは膨大で、各顧客が購入した商品間の関係をグラフで表現することが決定されました。この場合、顧客を頂点、購入した商品を辺として扱うことで、商品の関連性を可視化できます。

最初に直面した問題は、商品の関連性を効率的に探索する必要があったことです。顧客間のリンクを探索するため、深さ優先探索を用いることにしましたが、訪問済みの顧客を記録しないと、無限ループに陥る危険がありました。この落とし穴を避けるため、セットを使用して訪問済みの顧客を管理しました。

このアプローチにより、効率的に関連商品を推薦できるようになりました。さらに、将来的な拡張を考慮し、ノードの追加や削除が容易なデータ構造の選定が重要であることも認識しました。

まとめ

  • データ構造の選択はプロジェクトのパフォーマンスに大きく影響します。
  • グラフ構造を用いた場合、訪問済みの管理が重要であり、適切なデータ構造を選ぶことで効率的な探索が可能になります。
RELATED POST