データ構造とは
データ構造(データこうぞう、英: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。
配列
配列(はいれつ)は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め,要素を区別します。配列によってまとめられた,一つひとつの変数を要素(ようそ)と呼びます。要素を区別するために添えた数字を添字(そえじ)と呼びます。
配列は大変シンプルで,コレクションクラスに比較すると必要とするメモリ量が少なく,アクセスが高速なことがメリットです。データを単純に格納して,順番に参照する程度の用途であれば,コレクションクラスに比較して配列のほうが有利です。
最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し,配列の添字を明記して要素に値を代入し,添字を指定して要素の値を呼び出します。
String names[] = {“Tim Bray”, // 0番目の要素
“Brian Kernighan”, // 1番目の要素
“Jon Bentley”, // 2番目の要素
“Karl Fogel”}; // 3番目の要素
for(int i = 0; i < names.length; ++i){
println(names[i]);
}
ランダムな整数データを500個もつデータファイルRandomData.txtを作成
int NUMBER_OF_RANDOM_DATA = 500;
int MIN_SIZE_OF_RANDOM_DATA = 1;
int MAX_SIZE_OF_RANDOM_DATA = 500;
String DATA_FILE_NAME = “RandomData.txt”;
int DIAMETER = 5;
void setup(){
//ランダムなデータの作成
ArrayList<Integer> nums = new ArrayList<Integer>();
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
nums.add((int)random(MIN_SIZE_OF_RANDOM_DATA,MAX_SIZE_OF_RANDOM_DATA));
}
//画面に出力してみる
size(500,500);
background(0,0,0);
stroke(255,0,0);
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
ellipse(i,nums.get(i),DIAMETER,DIAMETER);
}
//ファイルに出力
String[] data = new String[NUMBER_OF_RANDOM_DATA];
for(Integer i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
data[i] = nums.get(i).toString();
}
saveStrings(DATA_FILE_NAME,data);
}
このコードで作成したデータファイルRandomData.txt
はスケッチフォルダGenerateRandomData
内にあります。他のsketchで利用する場合は,そのsketchのスケッチフォルダにコピーしてください。
コレクション
配列は変数に添字と呼ばれる番号を振ることで要素を区別しています。場合によっては添字が不要であったり余計であったりします。
コレクション(collection)(時には,コンテナー(container)と呼ばれます)は,効率的なアクセスのために有用な方法で,オブジェクトを保持してまとめる入れ物です。
コレクション(リスト、セット)や マップ は、オブジェクトの集合を扱うための仕組みです。
カテゴリ | クラス | 説明 |
---|---|---|
List系 | ArrayList | 配列を扱います。 |
LinkedList | 配列を扱います。挿入・削除が高速です。 | |
Vector | 配列を扱います。 パフォーマンスが悪いため現在ではあまり推奨されない古いクラスです。 |
|
Set系 | HashSet | 値の重複を許さない順不同の要素集合を扱います。 |
TreeSet | 値の重複を許さないソートされたの要素集合を扱います。 | |
Map系 | HashMap | キーと値の組からなる要素の集合を扱います。 |
TreeMap | キーと値の組からなる要素の集合を扱います。 キーでソートされています。 |
Array List |
Linked List |
Hash Map |
Tree Map |
Hash Set |
TreeSet | |
---|---|---|---|---|---|---|
インタフェイス | List | List | Map | Map | Set | Set |
要素の重複 | ○ | ○ | × | × | × | × |
null値の要素 | ○ | ○ | ○ | × | ○ | × |
自動ソート | × | × | × | ○ | × | ○ |
まとめ
- 配列はシンプルで高速なアクセスが可能です。要素数が少なく,ごく単純な操作しか必要ない場合に活用すると良いでしょう。
- コレクションは柔軟な取り扱いができるよう工夫された仕組みです。特に意味がなければ,配列ではなくコレクションを用いましょう。