Collection で気をつけること

2010年04月10日 18時41分 Java • Tags:



※対象バージョン:Java1.4

Collection はオブジェクトの集合を管理する必要不可欠な機能ですが、実装している Collection クラスによってオブジェクト管理方法が異なり気をつけるべきことがあります。

使い回しを避ける

以下のソースコードを例にしてみましょう。

Vector cols = new Vector();
Vector rows = new Vector();

cols.add("col 1-1");
cols.add("col 1-2");
rows.add(cols);
cols.clear();

cols.add("col 2-1");
cols.add("col 2-2");
rows.add(cols);
cols.clear();

このソースコードは縦横のテーブル構造を意識して作られております。Vector の cols に 1 行分の列データ、Vector の rows には行データを、それぞれ管理しています。rows に cols を追加していき、テーブル構造を再現しています。

一見して正しいように見えますが、重大なバグがあります。このソースコードの実装者の意図はこうです。

cols オブジェクトを再利用してメモリを節約する

cols はオブジェクトであり、参照型であることを忘れてはいないでしょうか?一度 rows に登録された cols は、オブジェクトがコピーされたわけではなく、あくまでも cols への参照が登録されただけのため、登録後に cols の clear 処理をしてしまうと登録した cols に登録していた “col 1-1″, “col1-2″ が clear されてしまいます。このため最終的には空の cols が取得できるだけで取得したい cols に登録されたオブジェクトは取得できません。

この解決策は行データ1つにつき Vector オブジェクトを作成することです。

× row.clear();
   ↓
○ row = new Vector();

なおオブジェクトの入れ箱となる変数は使いまわしても構いません。rows に登録してしまえば GC の対象になりません。逆に言うと何でもかんでも Collection に登録してしまうと GC されないメモリリークが発生します。

LinkedListでの注意点

Vector や ArrayList は配列でオブジェクトを管理しているのに対し、LinkedList はリンクリストのデータ構造を持っています。リンクリストは各オブジェクトに次のオブジェクトへの参照を持たせることで、次へ、次へ、次へとリストを実現します。この構造により高速にデータの管理が可能だと説明されることがありますが、実際には実装方法に依存するところがあります。

LinkedList が高速に処理できるのは先頭や末尾でないリスト中にデータを挿入 (add()) したり、削除 (remove()) する場合です。先頭や末尾を挿入したり削除しても ArrayList とほとんど実行時間はかわりません。

LinkedList が高速に処理できるのは先頭や末尾でないリスト中にデータを挿入したり、削除する場合です。先頭や末尾を挿入したり削除しても ArrayList とほとんど実行時間はかわりません。

また LinkedList で get() を利用すると恐ろしく実行時間がかかります。ArrayList と比較したところ約 1000 ~ 10000 倍近くも時間がかかってしまいました。

単一のオブジェクトではなく、リストの全てのオブジェクトを取得するのであれば LinkedList の iterator() メソッドで取得した Iterator オブジェクトを利用する方が高速にリストに登録されたオブジェクトを取得することができます。ArrayList の場合は get(int) でも Iterator でもどっちを利用しても大して変わりません。

サンプルコード

int start = 0;
int end = 10000000;
long startTime;
long stopTime;
long diffTime;
Iterator it;

// LinkedList add
List list = new LinkedList();
list.add(String.valueOf(start));
list.add(String.valueOf(end));
startTime = System.currentTimeMillis();
for (int i = start + 1; i < end; i++) {
    list.add(1,String.valueOf(i));
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;
System.out.println("LinkedList add(1) " + diffTime + "ms");

// LinkedList get
startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;
System.out.println("LinkedList get() " + diffTime + "ms");

// LinkedList iterator
it = list.iterator();
startTime = System.currentTimeMillis();
while (it.hasNext()){
    it.next();
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;
System.out.println("LinkedList iterator " + diffTime + "ms");

// ArrayList add
list = new ArrayList();
list.add(String.valueOf(start));
list.add(String.valueOf(end));
startTime = System.currentTimeMillis();
for (int i = start + 1; i < end; i++) {
    list.add(1,String.valueOf(i));
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;        
System.out.println("ArrayList add(1) " + diffTime + "ms");

// ArrayList get
startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;
System.out.println("ArrayList get() " + diffTime + "ms");

// ArrayList iterator
it = list.iterator();
startTime = System.currentTimeMillis();
int j = 0;
while (it.hasNext()){
    it.next();
}
stopTime = System.currentTimeMillis();
diffTime = stopTime - startTime;        
System.out.println("ArrayList iterator " + diffTime + "ms");


/******* プログラム実行結果 **********************************************************
**************************************************************************************/


Leave a Reply

preload preload preload