プログラミング応用b 第14回 『コレクション1 (Vector)』


今回は,プログラムの中で情報を保持する代表的な方法である,Vector(ベクタ)を学びます。
以前学習した配列は最も基本的なデータ構造であり,ベクタはプログラム実行時に格納可能な要素数を増やせる配列です。


【情報の保持】

一般に,複数の情報を処理して有効な結果を得るためには,その複数の情報の全てをメモリ上に保持する必要があります。まずは、情報の保持の最も基本的な方法である配列の復習と,その改良版であるベクタについて学習していきます。

【配列の復習】

 複数の情報を保持するための最も簡単な手段は,皆さんもご存じの配列です。配列の使用例として,中世の手持ち武器のファイルweapon.csvから各武器のデータを読み込んで,逆順に表示する“逆順表示”プログラムを考えてみましょう。ここでは“逆順に武器データを扱う”という処理を行うために,いったん全てのデータを配列に格納することにします。
 List 1が配列を使ってweapon.csvの中身を逆順表示するJavaプログラムの簡単な例です。89個の武器データが入ったテキストファイル weapon.csv は、Eclipseで作成したプロジェクトフォルダ直下に置いて下さい。実行したら,weapon.csvの中身が逆順に表示されているか確認しましょう。
List 1 Reverse2.java データファイル weapon.csv

import java.io.*;

public class Reverse2 {
  public static void main( String args[] ) {
    try {
      final int arrayN = 89;
      // 89個のString型オブジェクトを格納する配列
      String[] buffers = new String[ arrayN ];
      String str;
      int i = 0;
      BufferedReader br = new BufferedReader
                        ( new FileReader( "weapon.csv" ) );
      while( ( str = br.readLine() ) != null ) {
         buffers[ i++ ] = str; // 配列にデータを格納
      }
      br.close();
      for( i = buffers.length - 1; i >= 0 ; i-- )
        System.out.println( buffers[i] );
    }
    catch( IOException ioe ) {
      System.out.println( ioe.toString() );
    }
    catch( ArrayIndexOutOfBoundsException aiobe ) {
      // 添字範囲逸脱の例外を処理
      System.out.println( aiobe.toString() );
    }
  }
}


【配列のメカニズム】

 ここで配列の利点欠点をはっきりさせるために,配列がメモリ上でどのような形を取っているかを説明することにしましょう。
 Fig.1が,N個のT型要素を持つ配列のメモリ上の姿です。T型のデータがちょうどN個分だけ格納できるひとかたまりのメモリ領域が一度に確保され,そこに0番目から(N-1)番目の要素がすきまなく並んでいます。


 メモリ上の情報にアクセスするには,メモリ上の情報の位置,つまりアドレスを指定する必要があります。配列の場合,"同じ大きさ"の変数が“すきまなく”要素が並んでいるという性質から,各要素のアドレスを簡単な計算で瞬時に求めることができます。例えば,T型配列arrayのn番目の要素のアドレスは

 配列の先頭アドレス + (n × (T型データの一個一個の大きさ))

という単純な計算で得ることが可能なわけです。メモリ上へのアクセスはそのアドレスさえ分かってしまえば瞬時に実行できます。このことから,配列の場合,どの要素へのアクセスでも可能で,しかもそのアクセスは瞬時に行われるということになります。このように,どの要素にでも同じ程度の時間で自由にアクセスできる性質をランダムアクセス(random access)と言います。
 配列のような情報を保持するためのデータ構造を,一般にコレクション(collection)とかコンテナ(container)と呼びます。コレクションは文字通り「何かを集めたもの」を表しています。コンテナという単語はズバリ,“容器”という意味で,貨物輸送用のコレクションと同じ単語です。Javaでは、コレクションという用語の方を主に用います。配列は,高速なランダムアクセスを提供するコレクション,というわけです。

 


【配列の性質】
 ここで配列の性質についてもう少しよく考えてみましょう。まず配列の利点ですが,これは前述したように,“配列はメモリ上に要素がきっちりと隙間なく連続してならんでいるような領域として確保される”,という性質によって生まれてきます。要素が連続して隙間なく並んでいるおかげで,各要素のアドレスが簡単な計算で求められ,要素への高速なランダムアクセスが可能になっているわけです。
 しかし,まさにその“メモリ上に要素が隙間なく連続してならんでいる”という性質が,配列を少々柔軟性を欠いたコレクションにしてしまっているのです。配列は次のような欠点を持っています。
 ・要素の挿入・削除の効率が悪い
 ・要素数が変更できない
これら柔軟性の無さを象徴する欠点は,いずれも配列の“要素がメモリ上に連続して存在している”という性質に起因しているのです。
 コレクションに格納されている要素の前後関係に意味があるような場合には,要素の挿入や削除は重要になってきます。しかしながら,配列においては要素の間に新たな要素を挿入したり,特定の要素を削除したりする作業は効率の悪いものになってしまいます。例としてFig.3-(1)に示す6個の要素を持つ配列への要素の挿入を考えてみましょう。


 今,この配列には5つの有効な要素(a,c,d,e,f)が格納されていて,本来5番目の要素が格納されている場所には有効な要素は格納されていないものとします。そして,0番目と1番目の要素の間に新たな要素bを格納する必要が生じたとします。すると,配列の“要素がメモリ上に連続して存在していなければならない”という構造上,要素を挿入する前に,1番目から4番目の要素の全てをコピーによってひとつずつ後方へずらさなければなりません(Fig.3-(1)の(b))。このコピーにかかる時間的なコストは,配列に格納している要素数が大きくなればなるほど,高くつくことになります。削除の場合も同様に“ずらしコピー”が必要になります(Fig.3-(2))。
 ところで,Fig.3の例は実際に格納している要素,すなわち有効な要素の数(要素の挿入と削除によって増減)が,配列の要素数と一致しない場合もあることを示しています。配列はそのランダムアクセス性から,有効でない要素に対しても簡単にアクセスできてしまいます。そのため,要素の全てが有効とは限らないような使い方をしているケースでは,各要素が有効であるかどうかを判別する手段が必要になってきます。一番便利な方法は,要素自体で判別できるようにしておくことです。有効でない特別な要素値としては,ポインタ型(C言語/C++)のヌルポインタ,参照型(Java)のnullが使用できます。しかし,要素型が非ポインタ型(C言語/C++)やプリミティブ型(Java)の場合には,そのような特別な値がないので,有効な要素数を自前で管理するなどして,対処しなければなりません。

 さて,Fig.3の例では有効な要素数が配列の要素数に達していなかったために,新たな要素を挿入することができました。しかし,配列の要素全てが有効である状態で更に要素を挿入する必要が生じた場合はどうしましょう? 
 もちろん,一度作成した配列の大きさを自由に変えることができれば問題は解決するわけですが,実際には配列の要素数をプログラム実行時に変更することはできません。次にこのことについて考えてみます。
 6個の要素を持つ配列arrayが既に存在している場合に,更に2個の要素を格納する必要が生じた場合を例にしてみましょう。まず,最初に確保されている要素N個の配列の領域はFig.4-(1)のようになっているわけです。このとき配列領域の前後には他の使用中(確保済み)のメモリ領域があるかもしれないことに注意して下さい。Fig.4-(1)の例でも,配列arrayのすぐ後ろに使用中のメモリ領域AとBがあります。

 もし,拡張したい分だけの未使用領域が既存の配列の直後に有れば,運良く配列を拡張することができるかもしれませんね。しかし,一般にメモリ領域を確保する場合は,そのメモリ上に順序よく確保されていきますので,Fig.4-(1)のように既存の配列領域の後ろには他の目的で使用されているメモリ領域(図の例では領域A)が存在していることが多く,そのような試みはまず失敗します。この場合,arrayの末端と使用済み領域Aの間には,2個分の要素を格納するだけの隙間はありません。

 またFig.4-(1)の例では,使用済み領域Aと使用済み領域Bの間には2個分の要素を格納する領域はありますが,ここを配列arrayの拡張に利用することはできません。なぜなら,配列は“要素がメモリ上に連続して存在していなければならない”からです。
 したがって,一般的なプログラム言語では一度確保した配列の要素数(=配列領域の大きさ)は変更することができないようになっています。もしどうしても配列の要素数をプログラム実行時に増やしたい場合には,Fig.4-(2)のように,別の配列領域を新しく確保して元の配列の要素をコピーしなくてはなりません。このような配列の拡張の方法には
 ・一時的に多くのメモリ領域が必要
 ・要素のコピーに時間がかかる
という問題があります。Fig.4-(2)の(a)と(b)を見ればわかりますが,コピーの作業を行うためには元の配列と新しい配列,すなわち元の配列の2倍以上のメモリ領域が必要になります。そしてそのコピーにかかる時間は,要素の大きさと
要素数が大きくなるにつれて長くなってしまうわけです。


【ベクタ】
 しかし,プログラム実行時に大きさが変えられる配列は,配列を拡張するときに生じるメモリ容量とコピー時間のオーバヘッドなどの問題点が有ったとしても用途によっては十分魅力的ではあります。実際,Javaではベクタ(vector)と呼ばれるクラスが用意されており,動的に大きさが変えられる配列として使えるようになっています。仕組みとしては,ベクタオブジェクトが内部的に配列を保持していて,その配列の前半部分に有効な要素が詰められており,配列に格納できる要素数(容量)と有効な要素の数を管理するようになっています(Fig.5)。Javaでは,容量をcapacity有効な要素の数をsizeと呼んでいます。

 この内部配列の容量は明示的に指定しても変えられるようになっていますが,ベクタクラスの便利なところは,要素の挿入時に配列の容量が足らなくなったっ場合に,自動的に配列領域を拡張してくれるという点です。ではJavaのベクタクラスから説明していきましょう。


【Javaのベクタクラス】

 JavaのVectorクラス(パッケージはjava.util)は,Object型変数を要素に持つ高機能な配列として機能します。Table 1 に Vector の主な機能を示します。
(Vectorの完全な説明書はこちら)

要素の型がObject型なので,クラス型のオブジェクトならばなんでも格納することができます。また,配列と言っても所詮はクラス型のオブジェクトですから,[]演算子を使った要素へのアクセスはできません。かわりに,添字整数を引数に持つメソッドelementAtやsetElementAtによって要素へアクセスします。
 それでは,Vectorの使用例を見てみましょう。List 2はVectorオブジェクトを利用してList 1を書き直したものです。9行目でVectorオブジェクトbuffersを宣言しています。コンストラクタの引数にはVectorの配列の大きさ,すなわちコレクションとしての容量(capacity)が指定されています。List 2では,この値を50に設定しています。つまり,このままでは配列の大きさは少なすぎるわけです。よって51個めの要素を挿入するところで,配列の自動的な拡張が起こることになります。
 その要素への挿入ですが,List 2では15行目のメソッドaddElementで行っています。このaddElementはVectorオブジェクトの内部配列の有効要素の列の最後に,指定された要素を追加します。このような有効要素の列の最後に新しい要素をつけ加えるという挿入の仕方は,Fig.3-(1)で問題にした“ずらしコピー”の必要がないので高速に行うことができます。ですから,挿入する要素の順番が特に問題にならない場合や,要素を順次挿入していくだけの場合には,このような有効要素列の末尾への追加手続きを利用するべきです。そして18〜19行目のfor文で,前述のメソッドelementAtを使ってベクタの要素の各文字列を添字つきで読み出し,表示しています。
 List 2を実行してみると,ちゃんとList 2と同じように表示され,Vectorオブジェクトの内部配列が自動的に拡張されていることがわかります。
List 2 Reverse3.java

import java.io.*;
import java.util.*; // for Vector

public class Reverse3 {
  public static void main( String args[] ) {
    try {
      final int arrayN = 50;
      // ベクタオブジェクトbuffers(初期容量50)
      Vector buffers = new Vector( arrayN ); 
      String str;
      BufferedReader br = new BufferedReader
                  ( new FileReader( "weapon.csv" ) );
      while( ( str = br.readLine() ) != null ) {
        // ベクタにデータを挿入
        buffers.addElement( str );
      }
      br.close();
      for( int i = buffers.size() - 1; i >= 0 ; i-- )
        System.out.println( buffers.elementAt( i ) );
    }
    catch( IOException ioe ) {
      System.out.println( ioe.toString() );
    }
    catch( ArrayIndexOutOfBoundsException aiobe ) {
      // 添字範囲逸脱の例外を処理
      System.out.println( aiobe.toString() );
    }
  }
}

実は,Vector型オブジェクトは,複数のスレッドから同時に利用されても安全である(スレッドセーフと言う)ように定義されています。しかし,その分,処理は低速になってしまっています。
Java には,Vectorと同じ様に使える高機能配列として ArrayList クラスが用意されています。ArrayList はスレッドセーフではない分,高速で,現在では Vector より ArrayList を
使う方が主流になっています。次回は, ArrayList についても紹介します。



【提出課題(第14回 1/11出題)】 〜 第15回 1/18の授業開始時に印刷済みのソースプログラムをレポートとして提出すること。複数枚になる場合はホッチキスなどでとめること。

●課題
今回用意したサンプルデータファイル weapon.csv は,各行に
武器名,片手武器(1)か両手武器(2)か,武器カテゴリー
という内容が入っている。例えば,13行目の
 knife,1,Dagger
という内容は,ナイフが片手武器(1)で,武器カテゴリーは短剣(dagger)であることを表している。
このサンプルデータファイルを利用して,以下の様なプログラムを作成せよ。
 List 2 を参考に, weapon.csv の全内容を1行ずつベクタに読み込む。そして,キーボードから新たな
データを追加できるようにし,追加したデータを武器名で辞書順にソートして,全データを weapon.csv に改めて書き込むこと。
データを追加登録する際,最低限,以下のデータを追加すること。これは,日本刀(katana)が両手武器(2)で,カテゴリーが剣(sword)であることを意味している。
katana,2,sword


戻る