プログラミング/12

出典: CourseWiki

目次

equalsメソッド

前回の DLinkedList クラスでは,データを検索する機能を用意していませんでした.

検索できるようにするため,DLinkedList クラスに public Object search(Object o) というメソッドを追加します.このメソッドは,連結リストから引数で指定されたオブジェクトを検索し,同じものがあればそのオブジェクトへの参照を,なければ null を返します.

この処理を行うためには,オブジェクトAとオブジェクトBが「同じ」なのか「違う」のかを判定する必要があります(同一性の判定).

オブジェクトの属すクラスによって同一性判定の基準は異なる可能性があるため,Javaでは,オブジェクト同士が等しいかどうかは,そのオブジェクトのクラスで定義する public boolean equals(Object o) メソッドで決めることになっています.

具体的には A.equals(B) == true (あるいは B.equals(A) == true) の時に限り A と B は等しいと見なします.

Stringの比較で,equals メソッドを使ったのはこれが理由です.IntegerやDoubleなどの他のクラスでも equals は定義されています(実際には,全てのクラスで equals は定義されています(自分で明示的に定義しなくても).この背景はクラスの継承を学ぶまで置いておきます).

ということで,DLinkedList クラスの search メソッドは次のように書くことができます. 各自追加しておいてください.

	public Object search(Object o) {
		for (Cell c = dummy.getNext(); c != dummy; c = c.getNext()) {
			if (c.getData().equals(o)) {
				return c.getData();
			}
		}
		return null;
	}

(CellクラスのgetData()がnullを返すことはない(つまり,nullは登録しない)という前提で書いてあります).

プログラムの実行速度

プログラミング上(システム設計上も),適切なデータ構造やアルゴリズムを選択することは非常に重要です.

用いるデータ構造やアルゴリズムでどのくらい性能が変化するかを体感するために,配列と連結リストの性能を比較してみましょう.

アルゴリズムの性能を議論する場合によく使われる尺度は処理時間と消費メモリですが, ここでは,処理時間を計測してみます(消費メモリは数倍程度の違いしかないので).

Javaで処理時間を計測するには,System.nanoTime() を使います. このメソッドはナノ秒単位の時刻を long 型で返すので,以下のようにすれば処理にかかる時間を計測できます.

long start = System.nanoTime();
計測したい処理;
long end = System.nanoTime();
long elapsed = end - start;

System.nanoTime()の返す値はナノ秒単位ですが,実際にナノ秒単位の粒度(細かさ)で測定できるわけではありません.(手許の MacOS X で試すと下3桁は常に0なので,粒度はマイクロ秒単位のようです).

配列と連結リストの性能比較

さて,ここでは以下の処理の時間を計測してみます.

挿入時間
n要素の配列または連結リストの先頭に要素を1個挿入する時間
ランダムアクセス時間
n要素の配列または連結リストで,乱数で選んだインデックスの要素を取得する時間

これを,nを1000から10000まで,1000毎に変化させて計測することにします.

配列で先頭に挿入するには,配列の要素を後ろに1つずらす(シフトする)必要がありますが, この処理に2通りのバージョンを用意しました.

  • insertArray1: 配列のシフトにfor文を使う
  • insertArray2: 配列のシフトにSystem.arraycopyを使う

{{column|1=System.arraycopy は配列をコピーするためのメソッドです(APIドキュメント).このメソッドはJavaVM自身が実行するように最適化されているので,高速に動作するはずです.}}

プログラムを以下に示します.

  • 外乱の影響を軽減するため,ITER(=10)回実行した平均時間を求めるようにしています
  • 途中にある System.gc() は,ガベージコレクション(GC)を実行するためのものです.GCはヒープメモリの空きが少なくなると自動的に実行されますが,GC実行中はプログラムの動作が停止するため,計測中にGCが発生すると計測値が大きくなってしまいます.このため,計測前に強制的にGCを行い,計測中になるべくGCが起きないようにしています.

/*
 * 連結リストと配列の性能測定
 */
public class LinkedListAndArrayBenchmark {
    // 試行回数
    private final static int ITER = 10;
 
    public static void main(String[] args) {
        System.out.printf("#Num  insAr1 insAr2 insLst accAry accList (usec)\n");
        for (int i = 1000; i <= 10000; i += 1000) {
            // 先頭への挿入時間の測定
            double insertArrayTime  = repeatInsertArray1(i) / 1000;
            double insertArrayTime2 = repeatInsertArray2(i) / 1000;
            double insertListTime   = repeatInsertList(i)    / 1000;
            // ランダムアクセス時間の測定
            double accessArrayTime  = repeatAccessArray(i) / 1000;
            double accessListTime   = repeatAccessList(i)   / 1000;
            System.out.printf("%5d %6.3f %6.3f %6.3f %6.3f %6.3f\n",
                    i, insertArrayTime, insertArrayTime2, insertListTime, 
                    accessArrayTime, accessListTime);
        }
    }
 
     // insertArray1をITER回呼び出して,平均実行時間を返す (nsec単位)
    private static double repeatInsertArray1(int n) {
        double sum = 0.0;
        for (int i = 0; i < ITER; i++) {
            // System.gc() は,強制的にガベージコレクションを実行するため.
            System.gc();
            sum += insertArray1(n);
        }
        return sum / ITER;
    }
 
    private static double repeatInsertArray2(int n) {
        double sum = 0.0;
        for (int i = 0; i < ITER; i++) {
            System.gc();
            sum += insertArray2(n);
        }
        return sum / ITER;
    }
    
    private static double repeatInsertList(int n) {
        double sum = 0.0;
        for (int i = 0; i < ITER; i++) {
            System.gc();
            sum += insertList(n);
        }
        return sum / ITER;
    }
    private static double repeatAccessArray(int n) {
        double sum = 0.0;
        for (int i = 0; i < ITER; i++) {
            System.gc();
            sum += accessArray(n);
        }
        return sum / ITER;
    }
    private static double repeatAccessList(int n) {
        double sum = 0.0;
        for (int i = 0; i < ITER; i++) {
            System.gc();
            sum += accessList(n);
        }
        return sum / ITER;
    }
    
    // n要素の配列の先頭に1つデータを挿入する処理に要した時間を返す(nsec単位)
    // バージョン1: 先頭にデータを挿入するために,配列の全てをシフト(1つずらす)
    private static double insertArray1(int n) {
        // n要素の配列を準備
        int[] array = new int[n];
        long start = System.nanoTime();    // 計測開始
        for (int j = n-1; j > 0; j--) {    // 配列全体を1つシフトして先頭を空ける
            array[j] = array[j - 1];
        }
        array[0] = 12345;                // 先頭に書き込み
        long end = System.nanoTime();    // 計測終了
        return (double)(end - start);
    }
    
    // n要素の配列の先頭に1つデータを挿入する処理に要した時間を返す(nsec単位)
    // バージョン2: 配列のシフトに System.arraycopy を使う
    private static double insertArray2(int n) {
        int[] array = new int[n];
        long start = System.nanoTime();
        // arrayの0番目からn-1個の要素をarrayの1番目以降にコピー
        System.arraycopy(array, 0, array, 1, n-1);
        array[0] = 12345;
        long end = System.nanoTime();
        return (double)(end - start);
    }
 
    // n要素の連結リストの先頭に要素を1つ挿入する処理に要した時間を返す
    private static double insertList(int n) {
        DLinkedList list = new DLinkedList();
        for (int i = 0; i < n; i++) {
            list.addFirst("DUMMY");
        }
        // 配列では int の配列を使ったが,連結リストでは Integer のリストで計測する.
        Integer tmp = new Integer(12345);
        long start = System.nanoTime();
        // addFirstが速すぎて1回の呼び出しでは測定できないので(start==endになる),
        // 100回繰り返す(繰り返すことで連結リストのサイズが変わってしまうが,目をつぶることにする)
        // より高速な計算機では値を増やす必要があるかも知れない
        final int LISTITER = 100;
        for (int i = 0; i < LISTITER; i++) {
            list.addFirst(tmp);
        }
        long end = System.nanoTime();
        return (double)(end - start) / LISTITER;
    }
 
    // 要素数nの配列にn回アクセスし,1回あたりの所要時間を返す
    private static double accessArray(int n) {
        int[] array = new int[n];
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            // アクセスするインデックスは乱数できめる
            int index = (int)(Math.random() * n);
            int dummy = array[index];
        }
        long end = System.nanoTime();
        return (double)(end - start) / n; 
    }
 
    // 要素数nの連結リストにn回アクセスし,1回あたりの所要時間を返す
    private static double accessList(int n) {
        DLinkedList list = new DLinkedList();
        // 連結リストにダミーのデータをn個追加
        for (int i = 0; i < n; i++) {
            list.addFirst("DUMMY");
        }
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            int index = (int)(Math.random() * n);
            list.get(index);
        }
        long end = System.nanoTime();
        return (double)(end - start) / n;
    }
}

結果

実行すると,次のような結果が出力されるはずです. (実行する際は,なるべく他のプログラムを止めて実行すること).

#Num  insAr1 insAr2 insLst accAry accList (usec)
 1000 10.200  3.000  0.065  0.245  0.849
 2000 10.100  2.400  0.020  0.094  1.849
 3000 12.700  3.100  0.020  0.093  3.002
 4000 14.400  3.900  0.020  0.094  4.086
 5000 16.700  4.000  0.017  0.092  5.142
 6000 19.200  4.600  0.019  0.096  6.176
 7000 20.900  5.300  0.017  0.092  7.226
 8000 23.400  5.500  0.021  0.092  8.308
 9000 25.600  6.700  0.020  0.093  9.313
10000 27.300  6.900  0.020  0.094 10.426

iMac (Intel Core2Duo 2.8GHz), 3GB RAM, MacOS X 10.5.4付属のJava環境で実行.

各列の意味は以下のとおりです.

意味
Num n(繰り返し数)
insAr1 配列での挿入時間(insertArray1)(単位はマイクロ秒)
insAr2 配列での挿入時間(insertArray2)
insLst 連結リストでの挿入時間
accAry 配列でのアクセス時間
accLst 連結リストでのアクセス時間

これだと分かりにくいので結果をグラフ化してみます.

グラフには Microsoft Excel のような表計算ソフトを使っても良いのですが,将来論文やレポートにグラフを張り込むことを考えてここではグラフ描画ソフトウェアである gnuplot を使うことにします. 今回の課題でも使うのでインストールしておいて下さい.

上の実行結果を time.dat というテキストファイルにセーブし,gnuplot 上で次のコマンドを実行すると挿入時間のグラフが表示されるはずです.

plot 'time.dat' using 1:2 with linespoints title "Array1", 'time.dat' using 1:3 with
linespoints title "Array2", 'time.dat' using 1:4 with linespoints title 'LinkedList'
(実際は1行で書く)
(plot コマンドは2次元グラフを描くコマンドです.'time.dat' はデータファイル名,using 1:2 はデータファイル1列目がX,2列目がYの値,with linespoints は線の種類,title "Array1" は凡例です.)

画像:insertTime.png
先頭への挿入時間

アクセス時間のグラフは次のコマンドで得られます.

plot 'time.dat' using 1:5 with linespoints title "Array", 'time.dat' using 1:6 with 
linespoints title "LinkedList"

画像:accessTime.png
ランダムアクセス時間

グラフからは次のことがわかります.

先頭への要素挿入
* 連結リストが圧倒的に速く,nが大きくなっても処理時間は増えない
* 配列ではnに比例して時間がかかる
* System.arraycopyもnに比例して時間がかかるが,for文でコピーするよりも高速
ランダムアクセス時間
* 配列は圧倒的に速く,nが大きくなっても処理時間は増えない
* 連結リストではnに比例して時間がかかる

なお,n=1000のところだけ少し処理時間がかかっていますが,おそらくJavaVMのJIT (Just In-time Compiler)機能の影響と思われます.

JavaVMは,通常はバイトコードをインタプリタで実行しますが,処理に時間が掛かっている部分(hotspot)を発見すると,高速化のためにその部分を自動的に機械語にコンパイルするようになっています(JIT機能).

n=1000では最初の実行になるので,まだ内部的にコンパイルが行われていなかった,もしくはJITによるコンパイル時間がかかっていると思われます.

このように,JITを使うとプログラムの実行時間が乱れるため,アルゴリズムの性能比較がやりにくいという問題があります. JavaVMのJIT機能を無効にするには,javaコマンドに -Xint オプションを指定します.この場合,すべてインタプリタで実行するため,処理速度は遅くなりますが(数十倍程度),実行結果の解釈は容易になります.

上のプログラムを -Xint オプションを指定して JIT を使わずに実行し,結果を比較してみて下さい.

  • コマンドラインでは,java -Xint LinkedListAndArrayBenchmark のように実行します.
  • Eclipseでは Run Configurations → Java Application の Arguments タブの,VM arguments のところに -Xint を指定します.

オーダ記法

アルゴリズムの性能を議論するとき,問題の規模(ここではn)を増加させたときに, 必要な計算機資源(CPUの処理時間や消費メモリなど)がどのように変化するかが重要です.

ある処理で必要な計算機資源が,問題の規模nに比例するとき,アルファベットのOを使ってO(n)と表現します(オーダnと読む).また,資源がnとは無関係な定数ならば,O(1)と表現します(定数オーダ). n2に比例するならば,O(n2)です.このような記法をオーダ記法といいます.

  • より正確な定義は以下のとおり.
必要な資源がf(n)のとき,2つの定数n0とcがあって,n0 < nである全てのnにおいて,f(n) \leq c\times g(n) が成り立つならば O(g(n)) .
  • n0より上の部分しか気にしないということは,nが小さい範囲のことは気にしないという意味です.
  • O(..) は上界(上限)を与えます.同様に下界を与えるΩ(..),上界と下界を同時に与えるΘ(..) という記法もあります.
  • オーダ記法では係数は無視します.つまり,ある計算機で実行時間が 0.001n 秒のアルゴリズムも 1000n 秒のアルゴリズムもオーダ記法では O(n) になります(係数の違いは高々定数倍の違いに過ぎないため).
    • ただし,現実には係数の違いは無視できない場合も多いです.

さまざまなオーダのアルゴリズムがあります.以下は一例です (cは定数).

  • O(cn) (指数オーダ)
  • O(nc) (多項式オーダ)
  • O(log(n)) (対数オーダ)
  • O(\sqrt{n}) (平方根オーダ)

以下のグラフから,指数オーダのアルゴリズムよりも多項式オーダのアルゴリズムの方が,多項式オーダのアルゴリズムよりも対数オーダのアルゴリズムの方がよいことが理解できると思います.

画像:scale1.png

下のグラフは,上のグラフのy軸の範囲を変えたものです.指数オーダは急激に増加することがわかります.

画像:scale2.png

世の中には指数オーダのアルゴリズムしか見つかっていない問題がたくさんありますが(巡回セールスマン問題など),指数オーダのアルゴリズムは少しnが大きくなるだけで処理できなくなります.このような問題を処理するためには近似アルゴリズム(厳密解に近い解を求めるアルゴリズム)がよく用いられます.

先ほどのプログラムで,処理時間のオーダを考えてみます.

先頭への要素挿入
* 連結リストへの挿入処理(DLinkedListクラスのaddFirst)では,nに依存した処理はないので(前回の内容),処理時間は O(1) です.測定した時間もほぼ一定になっています.
* insertArray1 では配列の先頭に1要素挿入するために,n個の要素をシフトさせています.このため,実行時間はnに比例します.つまりO(n)です.グラフも直線状になっています.
* insertArray2 では配列のシフトに System.arraycopy を使っていますが,arraycopy でもn要素をシフトするにはnに比例した時間がかかります.
ランダムアクセス
要素数nとして,アクセスする要素のインデックスが0〜(n-1)まで一様に分布するとして,
* 配列でのランダムアクセス: 定数時間なので O(1).測定した時間もほぼ一定になっています.
* 連結リストでのランダムアクセス: 先頭から順番にセルを辿る必要があるので O(n)
先頭からたどるセル数の期待値はn/2なのでO(n)です.グラフも直線状になっています.

なお,連結リストはランダムアクセスは遅いですが,前後の要素へのアクセスは O(1) 時間で可能です.

ハッシュテーブル

ハッシュテーブル(hash table)はハッシュ表とも呼ばれ,良く使われるデータ構造の1つです.

要素数nの連結リストや配列から特定の要素を検索する場合,先頭から検索する必要があるため平均O(n)時間かかります. これに対し,ハッシュテーブルは登録・検索時間がほぼ O(1) という優れた性質を持っています.

Java Collection Frameworkでもハッシュテーブルの実装が提供されていますが(java.util.HashMapクラスなど),例によって勉強のために自分で実装してみることにします.

ハッシュテーブルの基本操作は以下の通りです.

登録(put)
データを登録
取得(get)
引数で指定したオブジェクトが存在すればそれを返す.存在しなければnullを返す.
削除(remove)
引数で指定したオブジェクトを削除する(存在する場合).

考え方

行数 s の表 table (これがハッシュ表です)を用意します (table[0]..table[s-1]). 登録するデータを x とするとき,x を 0 から s-1 の範囲の整数に変換する関数 f が存在するものとします(0\leq f(x)< s).

登録処理
x を登録するとき,table の f(x) 行目に登録します
取得処理 (削除処理も同様)
検索したいデータ を y とするとき,table の f(y) 行目をチェックします.table にあればそれを返し,なければ null を返します.

画像:HashTable.png
ハッシュテーブル

関数 f をハッシュ関数(hash function)といいます.また,あるデータに対してハッシュ関数が返す値をハッシュ値と呼びます.

次の図のように,異なるデータでもハッシュ値が同一になる場合があります(異なるデータで同一のハッシュ値になることをハッシュの衝突(hash collision)といいます).この場合の対処法はいくつかありますが,ここでは表の各要素は連結リストにしておき,同一のハッシュ値のデータは連結リストに登録しておくことにします.

画像:HashCollision.png
ハッシュの衝突

ハッシュテーブルの効率

ハッシュテーブルでは,ハッシュの衝突が発生しない限り,登録,取得,削除はO(1)時間で実行できます. (衝突が発生した場合は,連結リストの長さに比例する時間がかかります). その代わり,配列や連結リストに比べてメモリ消費量は多少大きくなります.

ハッシュテーブルが効率良く動作するためには,ハッシュの衝突の確率が低いことが必要です.そのためには以下が重要になります.

  • ハッシュ関数が,なるべく一様にデータを分散させること
  • ハッシュテーブルのサイズが,登録するデータの数よりも十分大きいこと

ハッシュテーブルに登録されているデータの数をテーブルサイズで割った値を load factor(占有率または負荷率) といいます. load factor が大きくなるとハッシュが衝突する可能性が高くなり,性能が劣化します.

ハッシュ関数

さて,ハッシュ関数はどうやって書けば良いのでしょうか.

コンピュータ内部では全てのデータは数値(2進数)で表現されているので,全てのデータは数値に変換可能です.例えばStringクラスの場合,内部では文字コード(JavaではUnicode)という数値で扱われているので,ここから何らかの値を計算することができます.他のクラスでも同様に,インスタンス変数の値に何らかの演算を行ってハッシュ値を計算できます.

幸いなことにJavaの全てのクラスは,public int hashCode() というメソッドを備えていて,これがインスタンスのハッシュ値を計算することになっています.(hashCode()はハッシュテーブルを実現するために存在しているようなものです).hashCode()は,そのクラスに適した方法でハッシュ値を計算します.

String foo = "FOO", bar = "BAR";
System.out.println(foo.hashCode() + ", " + bar.hashCode());
// 69798, 65523 が表示された

ちなみに,StringクラスのAPIドキュメントによると,hashCode メソッドは次のようにハッシュ値を計算します.

この文字列のハッシュコードを返します。String のハッシュコードは、次の方法で計算します。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

int 算術を使います。 s[i] は文字列の i 番目の文字、n は文字列の長さ、^ は、べき乗を示します。空の文字列のハッシュ値は 0 です。

hashCode() メソッドは(負の数を含めて) int の全ての範囲の値を返す可能性があります.これを0からs-1までの整数に変換しないといけませんが,これにはいくつか方法があります.

ここでは,単純に

int i = Math.abs(foo.hashCode()) % s;

としておきます(除算法).

なお,Javaでは A.equals(B) ならば,A.hashCode() == B.hashCode() が成立することになっています(逆は必ずしも成立しません).

(正確には,成立するように equals メソッドと hashCode メソッドを書く約束になっている).

HashTableクラス

ハッシュテーブルのシンプルな実装を以下に示します. (java.util.Hashtableという標準のクラスと混同しないようにしてください)

mainメソッドも入れてあるので(こういう書き方もできます),実行することもできます.

/*
 * ハッシュテーブルのクラス
 */
public class HashTable {
    // 表は連結リストの配列
    private DLinkedList[] table;
 
    // コンストラクタ
    public HashTable(int size) {
        table = new DLinkedList[size];
    }
    
    // 引数のオブジェクトが table 上でどのインデックスに入るか計算する
    private int getIndex(Object o) {
        return Math.abs(o.hashCode()) % table.length;
    }
    
    // 登録
    public void put(Object o) {
        int slot = getIndex(o);
        // table[slot]がnullならば,そのエントリは空なので,
        // 連結リストを作成していれておく
        if (table[slot] == null) {
            table[slot] = new DLinkedList();
        }
        table[slot].addFirst(o);
    }
    
    // 取得
    public Object get(Object o) {
        int slot = getIndex(o);
        DLinkedList list = table[slot];
        if (list == null) {
            return null;
        }
        // search from the list
        return list.search(o);
    }
 
    public static void main(String[] args) {
        final int max = 1000;
        // mainメソッドの中で自分のクラスをインスタンス化
        // max/2個のデータを格納するので,ハッシュテーブルのサイズをmaxにしておけば
        // load factor = 0.5 になる
        HashTable ht = new HashTable(max);
        for (int i = 0; i < max; i++) {
            // iが偶数のときだけ "DATA" + i (String) を put する 
            if (i % 2 == 0) {
                ht.put("DATA" + i);
            }
        }
        // ちゃんと入っているか確認
        for (int i = 0; i < max; i++) {
            Object o = ht.get("DATA" + i);
            if (o != null) {
                System.out.print(o + " ");
            }
            if (i % 20 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }
}

HashTableクラスのデータ構造は以下のようになっています.table上のnullのエントリはデータが存在しないところです.

画像:HashTableClass.png
HashTableクラスの構造

課題12-1(ハッシュテーブル)

  1. 上のHashTableクラスに,public boolean remove(Object o) メソッドを追加してください.このメソッドは,引数のオブジェクトと同じものがあれば削除して true を返します.なければ false を返します.
    • removeメソッドが正常に動作することを示すプログラムと実行結果を示すこと.
    • ヒント: まず DLinkedList クラスに,指定されたオブジェクトを削除するremove(Object o)メソッドを付け加える.
  2. ハッシュテーブルの load factor によって,getに要する時間がどのように変化するかを調べ,適切な load factor について考察して下さい(load factor が小さくなるほど性能がよくなる代わりにメモリを消費するため,load factorが小さければよいというものではありません.load factorが半分になると,ハッシュ表のサイズは倍になります).
    • データ数を適当な数n(例えば100,000)に固定する.load factor が 0.05 から 4.0 まで 0.05 刻みで変化するようにテーブルサイズを変化させながら,n個の要素をgetする時間を計測する(何回か測定して最小値を求めたほうが良い).横軸に load factor,縦軸にn個の要素をgetする時間をプロットしたグラフを作成し,考察してみよ.
      • 注意: load factor が 0.05 ならば,ハッシュ表のサイズは 100,000/0.05 = 2,000,000 になる.
    • ハッシュテーブルに登録(あるいは取得)するデータを,上のサンプルプログラムのように "DATA" + i のようにすると文字列の連結自体に時間がかかってしまい,良い結果が得られないので(getの時間を測っているのか文字列の連結時間を測っているのか..),Integerを使うと良い.(hashtable.put(new Integer(i));)
    • JITの影響を避けるために,プログラム実行時に -Xint オプションを指定しましょう.
    • ガベージコレクションの影響を避けるために,計測直前に System.gc() を実行しましょう.
    gnuplotでグラフを描くのが難しければ Excel などで作成しても構いません.

レポートにはソースコード,グラフ,考察,感想を含めて下さい.

余裕がある人用1

HashTableクラスにpublic String toString() メソッドを追加し,System.out.println() などで内容を簡単に表示できるようにしてください.

HashTable h = new HashTable(10);
h.put("x1"); 
h.put("x2");
h.put("x3");
System.out.println(h);
// [x2, x1, x3] のように表示される.ハッシュ表上の順序で構わない.

ヒント:

文字列を追加していく処理の書き方は DLinkedListクラスのtoString()メソッドが参考になるはずです.

連結リストの要素をたどりながら処理を行う必要がありますが,DLinkedListクラスのget(int index)メソッドを使うと遅いので,セルのnextを辿りながら処理を行いましょう. DLinkedListにダミーセルを返す public Cell getDummyCell() メソッドを追加すると,以下のように繰り返しを実行できます.

DLinkedList list;
...
Cell dummy = list.getDummyCell();
for (Cell c = dummy.getNext(); c != dummy; c = c.getNext()) {
  ...
}

(本当はダミーセルを返すのではなく,連結リスト上で繰り返しを行うためのクラス(イテレータ(iterator))を定義するほうが良いのですが,とりあえず)

余裕がある人用2

上の HashTable クラスは,最初にサイズを決める必要があるため,最初に想定した数より多くのデータを登録すると load factor が上がって性能が劣化します.put のときに load factorを計算し,一定の値を上回ったら table を2倍のサイズに拡大するように変更してください.

ヒント:

  • load factorを計算するためには,現在格納されているデータ数をインスタンス変数で記憶しておく
  • tableを2倍に拡大する方法:
    • 新しく2倍の大きさの配列(DLinkedList[] newtable)を確保し,
    • 既にtableに入っているデータをnewtableにコピーする.このとき,各データのハッシュ値からnewtableのどのインデックスに入れるかどうかを計算し直さないといけないことに注意すること.
    • 最後にtable=newtable;として配列を入れ替え

可能ならば,テーブルサイズを拡大しない場合と比較して,拡大すると性能がよいことを示してください.

Copyright (C) 2002-2015 Kota Abe, Osaka City University

ナビゲーション