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

7.Recursive7.Recursive

再帰とは 再帰(Recursion)とは,再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは,自分自身の定義の中に,自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。 階乗 整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。 n! = n × (n-1) × (n-2) × ... × 2 × 1 この式を再帰的定義に書き換えると,次のようになります。 n! = […]

Algorithms and Data StructuresAlgorithms and Data Structures

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

Reference(jp)Reference(jp)

「明解 Javaによるアルゴリズムとデータ構造」  柴田 望洋 (著)ソフトバンククリエイティブ (2007/11/7) 「明解Java 入門編」  柴田 望洋 (著)ソフトバンククリエイティブ(2007/8/8) http://bohyoh.com/Java/ 「Javaによるはじめてのアルゴリズム入門」(河西朝雄著、技術評論社、2001年) 「標準Javaプログラミングブック」(河西朝雄著、技術評論社、2001年) とほほのJava入門 (http://www.tohoho-web.com/java/index.htm )