4.Data Structure

データ構造とは

データ構造(データこうぞう、英: 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);
}

2016-09-04

このコードで作成したデータファイル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値の要素 × ×
自動ソート × × × ×

 

まとめ

  • 配列はシンプルで高速なアクセスが可能です。要素数が少なく,ごく単純な操作しか必要ない場合に活用すると良いでしょう。
  • コレクションは柔軟な取り扱いができるよう工夫された仕組みです。特に意味がなければ,配列ではなくコレクションを用いましょう。
参考:

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

15.Summary15.Summary

Webアプリケーション作成(コーディング・テスト、デバッグ、仕上げ)、全員発表する 発表課題: オープンデータの取得と利用 使用言語:processing もしくは Java 発表時間:5分程度 課題: オープンデータの取得と利用 オープンデータの材料選び オープンデータの取得 (URL) オープンデータの利用 (processing もしくは Java) オープンデータ応用のWEB公開 (Google sitesに埋め込み) ヒント: これまで演習したプログラムの組み合わせが必要です。 nextbus, […]

Algorithms and Data StructuresAlgorithms and Data Structures

授業概要  ソートとコレクションを中心にアルゴリズムとデータ構造に関する基本を学習する。 Java言語によるプログラミング技術の基本事項を習得する。 特にアルゴリズムとデータ構造の理解を中心に、講義および演習を行う。 授業の到達目標 ・オブジェクト指向言語の概念を理解するとともに、Javaを用いて課題を解決するスキルを身につける。 ・アプリケーションの開発に必要な概念を理解するとともに、Java言語を用いて実用的なWebアプリケーションの開発が行えるようになる。 事前・事後学習の内容 予習としてMyWasedaに掲載するレジュメの事前読了を求めることがあります。各回の予習には90分~120分かかると想定されます。 授業計画 1: 本講義の目的と進め方について説明する。最終的に作成するアプリケーションの実例を説明する。 2: 基本概念を理解する。Javaのインストールからコマンドライン実行の方法を学ぶ。 3: 基本的なアルゴリズムを学ぶ。 4: 基本的なデータ構造を学ぶ。 5: 探索アルゴリズムを学ぶ。 […]

8.Sort8.Sort

ソートとは ソートとは,複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の2つがあります。 昇順:小さいものから大きなものへ 降順:大きなものから小さなものへ   並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所(文字列)による並べ替えが行われます。 ソートアルゴリズム ソートの処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。 ソートを行うアルゴリズムの例として次のものが挙げられます。 基本形 基本交換法:バブルソート 基本選択法:直接選択法 基本挿入法 応用形 改良交換法:クイックソート 改良選択法:ヒープソート 改良挿入法:シェルソート バブルソート バブルソート (bubble […]