JAVA とテンプレート

Size: px

Start display at page:

Download "JAVA とテンプレート"

ゆあよせ
4 years ago
Views:

1 JAVA とテンプレート

2 序論 : コンテナ他のクラスのオブジェクトを保存するものをコンテナ (Container) と呼ぶ集合リスト表コンテナに求められる機能追加削除参照要素の比較並べ替え要素のクラスが不明では比較できない要素が想定しているクラスのものかの判定

3 テンプレート以前の対応方法コンテナ設計時に保存されるクラスを特定してコンテナをコードする保存されるクラスごとに作成しなければならない再利用可能性が下がる最上位クラスのオブジェクトを保存するものとしてコードする想定外のオブジェクトを排除できない大小関係を比較できない比較するためのインターフェイスを実装したオブジェクトを保存するものとしてコードする想定外のオブジェクトを排除できない

4 JAVA5 以前のコンテナ private List list; private SortedSet sortedset; list = Collections.synchronizedList(new ArrayList()); sortedset = Collections.synchronizedSortedSet(new TreeSet()); /** sortedset の中身をリストに変換 */ List sortedlist = Collections.synchronizedList(new ArrayList()); while(!sortedset.isempty()){ /** sortedset から何が出てくるか不明なため Object のインスタンスになる */ Object first = sortedset.first(); sortedset.remove(first); sortedlist.add((integer)first);

5 JAVA5 以降のコンテナ : テンプレート使用 private List<Integer> list; private SortedSet<Integer> sortedset; コンテナの要素となるクラスを指定 list = Collections.synchronizedList(new ArrayList<Integer>()); sortedset = Collections.synchronizedSortedSet(new TreeSet<Integer>()); List<Integer> sortedlist = Collections.synchronizedList(new ArrayList<Integer>()); while(!sortedset.isempty()){ /** sortedset から Integer 出てくるのが明か */ Integer first = sortedset.first(); sortedset.remove(first); sortedlist.add(first);

6 テンプレートを使用したコンテナの利点コンパイル時に定義と要素の整合性を確認取り出した要素を想定されるクラスにキャストする必要がない要素を追加する際にもキャストする必要がない

7 テンプレートの活用 : メソッド public static <T extends Comparable<T>> void sort(t t[]) { for (int i = t.length; i > 0; i--) { for (int j = 0; j < i - 1; j++) { if (t[j].compareto(t[j + 1]) > 0) { T c = t[j]; t[j] = t[j + 1]; t[j + 1] = c; ソートされるオブジェクトのクラスを特定せず T と表記テンプレートクラス T はインターフェイス Comparable を実装メソッド compareto() を持つ

8 テンプレートの活用 : クラス public class BinaryHeap<T> { /** データを保持するリスト */ private List<T> list; /** 要素を比較する方法 */ private Comparator<T> comparator = null; /** 要素数 */ private int n;

9 Main.java package withouttemplate; import java.util.arraylist; import java.util.collections; import java.util.list; import java.util.sortedset; import java.util.treeset; /** * テンプレートを使わない例 tadaki */ public class Main { private List list; private SortedSet sortedset; public Main() { /** thread-safe とするための処理 */ list = Collections.synchronizedList(new ArrayList()); sortedset = Collections.synchronizedSortedSet(new TreeSet()); public void exec() { /** データの生成 */ for (int i = 0; i < 10; i++) { int k = (int) (100 * Math.random()); list.add(k); sortedset.add(k); /** list の内容を出力 */ System.out.println("members in list"); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); /** sortedset の中身をリストに変換 */ List sortedlist = Collections.synchronizedList(new ArrayList()); while(!sortedset.isempty()){ /** sortedset から何が出てくるか不明なため Object のインスタンスになる */ Object first = sortedset.first(); sortedset.remove(first); sortedlist.add((integer)first); /** sortedlist の中身を出力 */ System.out.println("members in sortedset"); for (int i = 0; i < sortedlist.size(); i++) { System.out.println(sortedList.get(i)); /** args the command line arguments */ public static void main(string[] args) { 1/2 ページ

10 Main.java new Main().exec(); 2/2 ページ

11 Main.java package withtemplate; import java.util.arraylist; import java.util.collections; import java.util.list; import java.util.sortedset; import java.util.treeset; /** * テンプレートを使った例 tadaki */ public class Main { /** テンプレートでコンテナの要素のクラスを指定 */ private List<Integer> list; private SortedSet<Integer> sortedset; public Main() { /** thread-safe とするための処理 */ list = Collections.synchronizedList(new ArrayList<Integer>()); sortedset = Collections.synchronizedSortedSet(new TreeSet<Integer>()); public void exec() { for (int i = 0; i < 10; i++) { int k = (int) (100 * Math.random()); list.add(k); sortedset.add(k); System.out.println("members in list"); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); List<Integer> sortedlist = Collections.synchronizedList(new ArrayList<Integer>()); while(!sortedset.isempty()){ /** sortedset から Integer 出てくるのが明か */ Integer first = sortedset.first(); sortedset.remove(first); sortedlist.add(first); System.out.println("members in sortedset"); for (int i = 0; i < sortedlist.size(); i++) { System.out.println(sortedList.get(i)); /** args the command line arguments */ public static void main(string[] args) { new Main().exec(); 1/1 ページ

12 Main2.java package withtemplate; import java.util.arraylist; import java.util.collections; import java.util.comparator; import java.util.list; import java.util.sortedset; import java.util.treeset; /** * tadaki */ public class Main2 { /** 保存するデータの構造を定義 */ private class Data { private String label; private double value; public Data(String label, double value) { this.label = label; this.value = value; public String getlabel() { return label; public double getvalue() { return value; /** データの比較方法を定義 */ private class DataCompare implements Comparator<Data> public int compare(data o1, Data o2) { int k = 1; if (o2.value > o1.value) { k = -1; if (o1.equals(o2)) { k = 0; return k; private SortedSet<Data> sortedset; 1/2 ページ public Main2() { sortedset = Collections.synchronizedSortedSet( new TreeSet<>(new DataCompare()));

13 Main2.java public void exec() { for (int i = 0; i < 10; i++) { double d = 100 * Math.random(); sortedset.add(new Data(String.valueOf(i), d)); List<Data> sortedlist = Collections.synchronizedList(new ArrayList<Data>()); while (!sortedset.isempty()) { /** sortedset から Integer 出てくるのが明か */ Data first = sortedset.first(); sortedset.remove(first); sortedlist.add(first); System.out.println("members in sortedset"); for (int i = 0; i < sortedlist.size(); i++) { Data d = sortedlist.get(i); System.out.println( d.getlabel() + " " + String.valueOf(d.getValue())); /** args the command line arguments */ public static void main(string[] args) { new Main2().exec(); 2/2 ページ

2. データ構造ヒープに保存するデータは番号付けられて保存される従ってリスト L として保存することとする 3. アルゴリズム 3.1. 要素の追加新しい要素の追加はリストの終端に置くことで開始するつまり最下層の一番右または新たに最下層を生成してその一番左となるこの後この要素を正し

2. データ構造ヒープに保存するデータは番号付けられて保存される従ってリスト L として保存することとする 3. アルゴリズム 3.1. 要素の追加新しい要素の追加はリストの終端に置くことで開始するつまり最下層の一番右または新たに最下層を生成してその一番左となるこの後この要素を正し 1. はじめに二分木ヒープ様々なアルゴリズムにおいてある要素の集合またはリストから最小な要素を取り出す必要があるそのような場合に使われる標準的データ構造が二分木ヒープ (binary heap) であるあるオブジェクトO を考えるそのオブジェクトはラベル O. label と値 O. value を持つとするこのようなオブジェクトを保存する二分木ヒープについて考える二分木ヒープは以下の二つの制約のある二分木である