DATA STRUCTURES AND ALGORITHMS

DSAとは

DSAは「Data Structures and Algorithms」の略で、日本語では「データ構造とアルゴリズム」です。データをどのような形で持ち、どのような手順で処理するかを考え、課題を正しく効率的に解くための基礎知識です。

DSAは何のためにあるのか

DSAは、計算したい課題をコンピューターが正しく解ける形にし、限られた時間とメモリの中で実行できる方法を考えるためにあります。特定の一人が一つの方法論として作ったものではなく、計算機科学の中で、データの表し方と課題を解く手順が研究・整理されてきた分野です。

データが少ないときは問題なく動いていた実装でも、扱う件数や実行回数が増えると、画面の反応が遅くなったり、ゲームのフレームが止まったりすることがあります。

DSAを学ぶと、単に「もっと速いコード」を探すのではなく、何を計算したいのか、どの結果を守るのか、どの制約があるのかを整理して、課題に合う方法を設計・比較できるようになります。

このガイドラインでは、設計の流れを一つずつ追う題材として経路探索を使います。ただし、VEINでDSAが役立つ場面は経路探索だけではありません。実際のコードでは、ゲームの状態更新、戦闘、描画、進行管理にも、目的に応じたデータ構造と処理手順を使っています。

Array / List

盤面、戦闘参加者、描画対象を順番に保持して走査する。

Set

訪問済みのマス、攻撃中・撃破済みのID、占有座標の重複を除く。

Map

IDから対象を取得し、対象ごとのダメージや種類ごとの進行状態を管理する。

Queue / ArrayDeque

コアにつながった魔力脈を、近い位置から順に広げる。

groupBy

同じ座標にいる探索者をまとめ、描画時の配置を決める。

Sort / Comparator

攻撃対象や演出の処理順を、毎回同じ規則で決める。

VEINに自然な実例がある章では実コードを使い、連結リストや2ポインターなど現在のVEINに適切な用途がない章では、標準的な課題を使って考え方を学びます。

データ構造は、データを保存し、取り出すための整理方法です。List、Set、Map、Queue、Heap、Graphなどがあり、それぞれ得意な操作が異なります。アルゴリズムは、入力から目的の結果を得るまでの処理手順です。探索、並べ替え、経路探索などが代表例です。

例えば利用者をIDから探す場合、利用者を順番に並べたListから毎回探す方法と、IDをキーにしたMapから取り出す方法があります。どちらを選ぶかは、利用者の数、検索する頻度、表示順を守る必要、追加メモリを使えるかによって変わります。

DSAでは、処理が速いかだけでなく、必要な結果を正しく返せるかを最初に確認します。順序、重複、空のデータ、最大値など、変更してはいけない振る舞いをテストで確かめたうえで、時間計算量と空間計算量を比較します。

計算量は、入力が増えたときに処理時間やメモリ使用量がどのように増えるかを考えるために使います。ただし、計算量だけではAndroid端末上の速さは決まりません。実際の入力と端末を使い、処理時間、フレーム時間、メモリ、GCなどを測って確かめます。

DSAは、重複を許すか、順序を守るか、どのデータ同士が関係しているかを明確にするためにも使えます。適切なデータ構造を選ぶことで、コードが扱うルールや意図が分かりやすくなり、テストやコードレビューもしやすくなります。

適切な方法は、データ量、実行頻度、端末、必要な正しさによって変わります。まず正しく動く単純な方法を作り、必要性と測定結果に応じて見直します。高度なデータ構造を使うこと自体を目的にせず、その時点の課題に対して最も単純で説明できる方法を選びます。