(57)【要約】      （修正有）【課題】配列の管理領域を記憶する追加領域を小さくする。【解決手段】アドレスワードとデータワードを含む定数個のワードを有する複数のブロックを連続して構成する配列を有し、複数のブロックの二分割位置を示す境界と配列の要素の初期値とを記憶し、二分割された第１領域内の未書き込みブロックの数と二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を境界とする配列を制御する。ブロックに対する書込みが呼ばれると境界を移動して第１領域を拡張し第１領域内に初期化済み書込みブロックを生成する処理を行い、第２領域の未書込みブロックへの書込みの場合、第１領域の初期化済み書込みブロックのアドレスワードに、第２領域の書込み先ブロックのアドレスを記憶し、第２領域の書込み先ブロックのアドレスワードに第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、第２領域の書込み先ブロックに値を書き込む。【選択図】図３
2018037010.tif 000002
【特許請求の範囲】
【請求項１】
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
前記処理は、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御プログラム。
【請求項２】
前記第２領域の前記書込み先ブロックに値を書き込む処理は、書込み先インデックスが前記データワードなら前記書込み先インデックスの要素に値を書込み、前記書き込み先インデックスが前記アドレスワードなら前記第２領域の前記書込み先ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードに値を書き込む、請求項１に記載の配列制御プログラム。
【請求項３】
前記処理は、さらに、
初期化が呼ばれると、全てのブロックが前記第２領域の未書込みブロックになるよう前記境界の位置を初期化し、前記初期化の初期値を記憶する初期化することを有し、請求項１に記載の配列制御プログラム。
【請求項４】
前記処理は、さらに、
読み出しが呼ばれると、
読み出し先ブロックが未書込みブロックの場合、前記初期値を返し、
前記第１領域の書込み済みブロックの場合、読み出し先インデックスの値を返し、
前記第２領域の書込み済みブロックの場合、前記読み出し先インデックスが前記データワードなら前記読み出し先インデックスの値を返し、前記読み出し先インデックスが前記アドレスワードなら前記読み出し先ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードのデータを返すことを有する、請求項３に記載の配列制御プログラム。
【請求項５】
前記処理は、さらに、
アクセス先インデックスと前記境界とに基づいてアクセス先が前記第１領域のブロックかまたは第２領域のブロックかを判別し、アクセス先ブロックが前記リンクを形成するか否かに基づいて前記アクセス先が前記第１領域の未書込みブロックかまたは前記第２領域の書込み済みブロックかを判別することを有する、請求項１に記載の配列制御プログラム。
【請求項６】
前記処理は、さらに、
前記リンクの形成を目的とせず前記第１領域の書込み済みブロックの値を書き換えた場合、前記第２領域の未書込みブロックのアドレスワードを、前記第１領域の書込み済みブロックとリンクが形成されないよう制御する非リンクすることを有する、請求項１に記載の配列制御プログラム。
【請求項７】
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックであり、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じ場合、前記書込み先ブロックに値を書込み、前記書込み先ブロックの不要なリンクを切断する非リンクを行うことを有する、請求項１に記載の配列制御プログラム。
【請求項８】
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第１領域の未書込みブロックの場合、
前記書込み先ブロックである前記第１領域の未書込みブロックの値を、前記エクステンド処理で生成した前記第１領域の初期化済み書込みブロックに書込んで、前記書込み先ブロックである前記第１領域の未書込みブロックのリンク先の第２領域の書込み済みブロックと前記エクステンド処理で生成した前記第１領域の初期化済み書込みブロックとの間にリンクを生成し、前記書込み先ブロックである前記第１領域の未書込みブロックに値を書き込むことを有する、請求項１に記載の配列制御プログラム。
【請求項９】
前記初期値は、インデックスに対応して初期値を返す初期化関数に対応付けられる、請求項３に記載の配列制御プログラム。
【請求項１０】
前記初期化可能配列は、前記配列に加えて、前記エクステンド処理が完了したことを示すエクステンド完了フラグを記憶する領域を有し、
前記複数のブロックは、管理情報のワード数に前記アドレスワードとデータワードの２を加算した数以上のデータワードを有し、
前記初期化することは、最後に前記第１領域に変化する前記第２領域の最後ブロックの管理情報のワードに前記境界と初期値を書込むことと、前記エクステンド完了フラグを未完了状態にクリアすることを含み、
前記書込みすることは、書込み先インデックスが前記第２領域の最後ブロックの前記管理情報のワードの場合、前記第２領域の最後ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードに書込み値を書込むことを含み、
前記エクステンド処理することは、前記エクステンド処理で前記第２領域の最後ブロックが第１領域のブロックに変化する場合、前記エクステンド完了フラグを完了状態にセットすることを含む、請求項３に記載の配列制御プログラム。
【請求項１１】
前記整数比は、１：ｋで、前記ｋは１以上の整数であり、
前記リンクは、１個の第１領域内の未書込みブロックとｋ個の第２領域内の書込み済みブロックを循環するリンクである、請求項１に記載の配列制御プログラム。
【請求項１２】
前記整数比が、１：ｋで、前記ｋが２以上の整数であり、
前記第２領域の高々ｋ−１個のブロックが初期化済みの端数ブロックとして管理される、請求項１に記載の配置制御プログラム。
【請求項１３】
前記処理は、
前記書込みの書込み先ブロックが前記第２領域の未書込みブロックの場合に、
更に前記端数ブロックがｋ−１個より少ない場合は、前記書込み先ブロックを初期化して端数ブロックに変更し、前記変更した端数ブロックに値を書込み、
更に前記端数ブロックがｋ−１個存在する場合は、エクステンド処理を実行して前記第１の領域に初期化済みブロックを生成し、前記書込み先ブロックと前記ｋ−１個の端数ブロックと前記初期化済みブロックとに循環リンクを生成し、前記書込み先ブロックに値を書き込む、請求項１２に記載の配置制御プログラム。
【請求項１４】
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する配列制御方法であって、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御方法。
【請求項１５】
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を記憶する記憶装置と、
前記記憶装置にアクセス可能なプロセッサとを有し、
前記プロセッサは、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
配列制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，配列制御プログラム、配列制御方法、配列制御装置に関する。
【背景技術】
【０００２】
配列（array）は、データ集計等で使用する基本的なデータ構造の一つである。配列はインデックスに対応してデータである値を記憶する記憶領域（主領域）を有する。配列は、インデックス0≦i＜Nに対して、読み出し（read）と書込み（write）を実行し、あるインデックスiに対して読み出しを行うとインデックスiの主領域に最後に書き込まれた値を返す。通常の配列の初期化は、全てインデックスの主領域に初期値を書き込む初期化処理を行うため、配列サイズNに比例した初期化時間がかかる。
【０００３】
一方、初期化可能配列（initializable array）というデータ構造は、上記の読み出し（read）と書込み（write）に加えて、初期化（initialize）を行うと全てのインデックス0≦i＜Nの値を初期値にする。初期化可能配列は、初期化を特別にサポートする構成を有し、初期化処理を配列サイズNにかかわらず一定時間で行う。例えば、word RAM(Random Access Machine)モデルにおいて、初期化initialize(x)が呼ばれた時に初期値xを記憶しておき、各インデックスiに書込み（write）されたかどうかを示す管理情報を記憶しておき、書込みが行われていないインデックスに読み出し（read）が呼ばれた場合は初期化で記憶した初期値xを返す技術が知られている。
【０００４】
このような初期化可能配列のデータ構造は、例えば、リアルタイムで動作しなければならないアプリケーションプログラムにおいて、初期化処理を配列のサイズNに依存しない固定時間で行う必要がある場合に利用される。配列のデータ構造については以下の特許文献、非特許文献に記載がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０５−１５８７８３号公報
【特許文献２】特開２００２−２０７６３４号公報
【特許文献３】特開２００４−３０３５３号公報
【特許文献４】特表２００９−５２１０４９号公報
【非特許文献】
【０００６】
【非特許文献１】A. Aho, J. Hopcroft, and J. Ullman, "The Design and Analysis of Computer Algorithms" Addison-Wesley, 1974
【非特許文献２】2 G. Navarro, "Dynamic dictionaries in constant worst-case time" Technical Report TR/DCC-2007-11, University of Chile, Department of Computer Science, October 2007
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の初期化可能配列は、インデックスに書込みが行われたか否かを示す管理情報を記憶するための追加領域が、配列の主領域に加えて必要である。
【０００８】
そこで，第1の側面の目的は，管理情報を記憶する追加領域のサイズを抑制する配列制御プログラム、配列制御方法、配列制御装置を提供することにある。
【課題を解決するための手段】
【０００９】
第１の側面は，少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
前記処理は、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御プログラム、である。
【発明の効果】
【００１０】
第１の側面によれば，配列の管理情報を記憶する追加領域のサイズを抑制することができる。
【図面の簡単な説明】
【００１１】
【図１】初期化可能配列と配列制御プログラムの一例を示す図である。
【図２】配列制御装置の構成例を示す図である。
【図３】本実施の形態における初期化可能配列を示す図である。
【図４】図３の配列の値の保存場所を説明する図である。
【図５】初期化と非リンクの制御を示すフローチャート図である。
【図６】初期化処理を示す図である。
【図７】読み出しの制御を示すフローチャート図である。
【図８】読み出し制御を示す図である。
【図９】非リンクの制御を示す図である。
【図１０】エクステンドextend()の制御のフローチャート図である。
【図１１】境界に隣接するＷ領域のブロックＢ１の種別がＷＳの場合のエクステンド制御Ｅ１を示す図である。
【図１２】境界に隣接するＷ領域のブロックＢ１の種別がＷＰの場合のエクステンド制御Ｅ２を示す図である。
【図１３】書込みwrite(i,x)の制御を示すフローチャート図である。
【図１４】書込みの処理Ｗ１を示す図である。
【図１５】書き込み処理Ｗ２−１を示す図である。
【図１６】書き込み処理Ｗ２−２を示す図である。
【図１７】書き込み処理Ｗ２−３を示す図である。
【図１８】初期化可能配列ARの具体例と、初期化を示す図である。
【図１９】図１６で説明した書込みＷ２−２の具体例を示す図である。
【図２０】図１６で説明した書込みＷ２−２の具体例を示す図である。
【図２１】図１６で説明した書込みＷ２−３の具体例を示す図である。
【図２２】図１６で説明した書込みＷ２−１の具体例を示す図である。
【図２３】図１６で説明した書込みＷ１の具体例を示す図である。
【図２４】読み出しreadの３種類の具体例を示す図である。
【図２５】読み出しreadの２種類の具体例と初期化initializeの具体例を示す図である。
【図２６】第２の実施の形態における初期化可能配列を示す図である。
【図２７】第２の実施の形態の配列の具体例を示す図である。
【図２８】第３の実施の形態における初期化可能配列を示す図である。
【図２９】図３７−３９の４つの例と第３の実施の形態の比較表を示す図である。
【図３０】第４の実施の形態における初期化可能配列を示す図である。
【図３１】第４の実施の形態の配列での読み出し制御を示す図である。
【図３２】希望しないリンクの解消を行うアンリンク制御を示す図である。
【図３３】境界に隣接するＷ領域のブロックがＷＰの場合で端数ブロックが存在する場合のエクステンド処理を示す図である。
【図３４】境界に隣接するＷ領域のブロックがＷＰの場合で端数ブロックが存在しない場合のエクステンド処理を示す図である。
【図３５】書込み先ブロックＢ１が未書込みブロックＷＳの場合で、端数ブロックＷＢが存在しない場合の書き込み処理を示す図である。
【図３６】書込み先ブロックＢ１が未書込みブロックＷＳの場合で、端数ブロックＷＢが存在する場合の書き込み処理を示す図である。
【図３７】配列の第１の例を示す図である。
【図３８】初期化可能配列の２つの例を示す図である。
【図３９】図３８の２つの配列をハイブリッド化した配列の例である。
【発明を実施するための形態】
【００１２】
図１は、初期化可能配列と配列制御プログラムの一例を示す図である。図１には、配列制御プログラムが初期化可能配列に対して行う制御が示される。図１中、処理制御部２は、処理対象データ１について所定の処理を実行し、その所定の処理に伴って初期化可能配列４に初期化（initialize）、読み出し（read）、書込み（write）を実行する。そして、配列制御部３は、初期化可能配列に対する初期化処理、書き込み処理、読み出し処理などの制御を実行する。初期化可能配列４には、配列の要素の初期値と、配列の書込み済み（または未書込み）インデックスなどの管理情報を記憶する管理領域５が設けられる。
【００１３】
初期化可能配列４は、配列の要素のデータ（値）を記憶するメモリなどの記憶装置である。また、管理領域５は、初期値や書込み済み（または未書込み）インデックスなどの管理情報を記憶するメモリなどの記憶装置である。
【００１４】
そして、処理制御部２は、コンピュータのプロセッサがあるアプリケーションプログラム（以下単にアプリケーション）を実行することにより構築される。また、配列制御部３は、プロセッサが配列制御プログラムを実行することにより構築される。
【００１５】
図２は、配列制御装置の構成例を示す図である。配列制御装置は、プロセッサであるCPU（Central Processing Unit）１０と、CPUによりアクセスされるRAM(Random Access Memory)などのメインメモリ１２と、外部とのインターフェース１４とを有し、それらがバス２８を介して接続される。また、バス２８には大容量の補助記憶装置２０−２６がCPUからアクセス可能に設けられる。補助記憶装置には、基本プログラムであるOS（Operating System）や各種ミドルウエアを格納する記憶装置２０と、アプリケーションプログラム（以下、アプリケーションと称する）２２と、処理対象データ２３と、配列制御プログラム２４とを記憶する記憶装置とを有する。さらに、CPUが配列制御プログラム２４を実行して、記憶装置２６内に記憶した初期化可能配列に対してアプリケーション２２からの初期化処理、書き込み処理、読み出し処理を行う。記憶装置２６内には初期化可能配列の主領域に加えて、その管理データを記憶する管理領域が記憶される。
【００１６】
ここで、初期化可能配列について一例に基づいて説明する。配列はインデックスに対応してデータを記憶する複数の要素を含む主領域を有する。そして、配列の「初期化」とは全ての要素を初期値で初期化することで、「書込み」とは初期化された要素に書込み値を上書きすることで、「未書込み」とは初期化されたままの要素で未だ書込み値が上書きされていないことをそれぞれ意味する。
【００１７】
図３７は、配列の第１の例を示す図である。配列ARは、インデックスに対応してデータ（値）をそれぞれ記憶する複数の要素を含む主領域を有する。図３７の配列ARは、主領域にインデックス０−７それぞれに対応する８つの要素を有する。また、主領域に加えて、ある集計値を記憶する集計値領域AGを有する。例えば、プロセッサがアプリケーションを実行して、８名のユーザのうちサーバに１日３回以上アクセスしたユーザ数をリアルタイムに集計する場合を想定する。つまり、配列ARのインデックス０−７は８名のユーザに対応し、各要素には各ユーザのアクセス回数が書き込まれる。そして、アクセス回数が３回以上のユーザ数が、集計値として集計値領域AGに記憶される。
【００１８】
配列AR1は、初期化した状態を示す。すなわち、アプリケーションからの初期化処理の呼び出し応答して、プロセッサは配列制御プログラムを実行して、配列AR1の全ての要素に初期値０（アクセス数０回）を、集計値領域AG1には初期値０（０人）をそれぞれ書き込む。そして、配列AR2では、インデックス２に対応するユーザがアクセスしたことに伴い、アプリケーションによりインデックス２の要素の値「２」が加算されて「３」が書き込まれる。同時に、集計値領域AG1の値「３」が加算されて「４」が書き込まれる。最後に、アプリケーションにより、要求された任意のタイミングで、配列AR3に対応する集計値領域AG3の値「４」が読み出される。そして、毎日所定のタイミングで、配列が初期化処理される。上記の初期化処理、配列の要素の値の読み出し処理、書込み処理は、配列制御プログラムによりプロセッサが実行する。
【００１９】
図３７の例では、初期化処理では、全てのインデックスに初期値「０」を書き込む必要がある。したがって、初期化処理は、配列サイズＮに比例した時間Ｏ（Ｎ）がかかり、初期化処理中は配列に対して書込みや読み出しを実行できない。一方、読み出しと書込みは定数時間Ｏ（１）で可能である。図３７の配列は、リアルタイムのサーバへのアクセス回数を記録するアプリケーションには不向きである。なお、前記Ｏはオーダーの頭文字である。
【００２０】
図３８は、初期化可能配列の２つの例を示す図である。初期化可能配列とは、初期化を高速に行うことができるデータ構造である。初期化可能配列がサポートする機能には、次のものがある。
（１）読み出しread(i)では、インデックスｉの要素の値を返す。
（２）書込みwrite(i,x)では、インデックスｉの要素にｘを書き込む。
（３）初期化initialize(x)では、全てのインデックス０≦ｉ＜Ｎの要素にｘを書き込む。
【００２１】
そして、プロセッサは、配列制御プログラムを実行することにより、初期化initialize(x)が呼ばれたとき、配列の全ての要素に初期値ｘを書き込まず単に初期値ｘを記憶し、各インデックスについて書込みされたか否かの管理情報を記憶する。そして、書き込みされてないインデックスiへの読み出しread(i)が呼ばれた場合、初期化で記憶した初期値ｘを返す。これにより、初期化処理を配列のサイズNに依存しない固定時間で行う。
【００２２】
図３８（Ａ）の配列では、インデックス０−１５のＮ＝１６の要素を有する配列ARが、４要素ずつのブロック０−３に分割され、管理領域として、各ブロックの未書込みと書込み済みを区別するビットマップBT_MPと、配列の全要素の初期値を記憶する初期値領域INTとを有する。プロセッサが配列制御プログラムを実行し、初期化が呼ばれると初期値領域INTに初期値「０」が書き込まれ、ビットマップブロックに「０」が書き込まれる。初期化では全インデックスに初期値を書き込むことは行わない。書き込みが呼ばれると、そのブロックの書込み先インデックスに書込み値が書き込まれ残りのインデックスに初期値「０」が書き込まれ、ビットマップの対応するブロックに書込み済みを示す「１」が書き込まれる。ビットマップは、書込みが行われたブロックには「１」を、未書込みのブロックには「０」を記憶し、書込み済みブロックと未書込みブロックの管理情報を記憶する。
【００２３】
図３８（Ａ）の配列では、初期化は図３７の配列より短い時間Ｏ（Ｎ／ｌｏｇＮ）で完了するが、ビットマップを初期化する必要があるので初期化時間は配列サイズＮに依存する時間ｏ（Ｎ）である。なお、時間ｏ（Ｎ）＝Ｏ（Ｎ／ｌｏｇＮ）は、時間Ｏ（Ｎ）より短いことを意味し、logは底を２とする二進対数である。但し、管理情報として初期値INTに加えてビットマップBT_MPが含まれるので、管理にＯ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ）の追加領域が必要になる。つまり、ビットマップはブロック毎の要素を有するので、配列サイズＮに依存した領域Ｏ（Ｎ）より小さいが領域ｏ（Ｎ）が必要である。
【００２４】
図３８（Ｂ）の配列は、インデックス０−１５のＮ＝１６の要素を有する配列ARに加えて、管理情報を記憶するための補助領域AUX、スタック領域ST、スタックポインタ領域ST_P、初期値領域INTを有する。補助領域とスタック領域は共に１６の要素を有する。この配列では、配列制御プログラムを実行するプロセッサが、配列ARのあるインデックスに書込みを行うと、補助領域の同じインデックスの要素とスタック領域の最小未書込み要素とに互いのインデックスを書き込んで双方向リンクを生成する。双方向リンクの生成とともに、スタックポインタが最大書込み要素のインデックスに更新される。
【００２５】
図３８（Ｂ）の例では、配列ARには５つのインデックスの要素に書込みが行われ、補助領域AUXの同じ５つのインデックスの要素とスタック領域の要素との間に双方向リンクが形成されている。例えば、配列のインデックス３には値「０」が書き込まれ、補助領域の同じインデックス３の値「４」に対応するスタック領域のインデックス４には補助領域のインデックス「３」が書き込まれ、補助領域とスタック領域との間で双方向リンクが形成されている。また、スタックポインタの値「４」は、スタック領域内の双方向リンクが形成されている最大インデックスを指している。
【００２６】
読み出しが呼ばれると、プロセッサは、読み出し先インデックスｉの補助領域の要素が双方向リンクを形成していれば、配列の読み出し先インデックスの値を返し、形成されていなければ初期値領域INTの値を返す。
【００２７】
この配列において、初期化が呼ばれると初期値領域INTに初期値「０」を書込み、スタックポインタST_Pに最小インデックス「０」を書き込む。したがって、初期化に要する時間は配列サイズＮに依存せず定数時間Ｏ（１）である。しかし、管理領域は配列の主領域の２００％程度を要し、追加領域は配列サイズＮに依存するＯ（Ｎ）である。
【００２８】
図３９は、図３８の２つの配列をハイブリッド化した配列の例である。図３９では、図３８（Ａ）と同様の配列ARの主領域とビットマップBT_MPを有する。さらに、ビットマップについて、図３８（Ｂ）と同様の補助領域AUX、スタックST、スタックポインタST_Pを有する。ビットマップが配列ARの主領域より小さいサイズであり、その分管理領域を小さくできる。
【００２９】
この例では、初期化が定数時間Ｏ（１）で可能である。一方、管理情報を記憶する管理領域にＯ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ）の追加領域が必要である。一般に、図３８（Ａ）のビットマップ法の３倍程度の追加領域になる。
【００３０】
図３７，図３８（Ａ），図３８（Ｂ），図３９をまとめると、図３７の配列は、初期化時間は配列サイズＮに依存する（Ｏ（Ｎ））が、管理の追加領域は定数サイズ（Ｏ（１））である。図３８（Ａ）の配列は、初期化時間は配列サイズＮに依存する時間よりも短く（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））、管理の追加領域も同様である（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））。図３８（Ｂ）の配列は初期化時間は定数時間（Ｏ（１））であるが、管理の追加領域は配列サイズＮに依存するサイズ（Ｏ（Ｎ））。そして、図３９の配列は、初期化時間は定数時間（Ｏ（１））、管理の追加領域は配列サイズに依存するサイズより小さい（Ｏ（Ｎ／ｌｏｇＮ）＝ｏ（Ｎ））。
【００３１】
以下説明する本実施の形態の配列は、初期化時間も定数時間、管理の追加領域も定数領域である。
【００３２】
［第１の実施の形態の初期化可能配列］
図３は、本実施の形態における初期化可能配列を示す図である。この初期化可能配列は、読み出しと書き込みが配列サイズに依存しない定数時間で行われ、初期化も定数時間で行われる。さらに、管理の追加領域も配列サイズに依存しない定数サイズである。
【００３３】
図３の配列ARは、インデックス０≦ｉ＜１６でＮ（＝１６）個の要素を有し、アドレスワードとデータワードを含む２以上の定数個（図３の例は２個）のワード（主領域の各要素に対応）をそれぞれ有する複数（図３の例は８個）のブロックを連続して構成する。
【００３４】
図３の例では、各ブロックには２個の要素（ワード）が含まれ（１ブロックが２ワードを含む）、ブロック内の最小インデックスの要素は後述する双方向リンクのリンク先インデックスを書き込むアドレスワード、その他のインデックスの要素は値を書き込むデータワードである。但し、アドレスワードにもデータが書き込まれる。
【００３５】
ここで、値が書き込まれる要素をワードと称する理由は、要素に書き込まれる値が３２ビット、６４ビットなどのワードであることに起因する。
【００３６】
さらに、配列の複数のブロックの二分割位置を示す境界BDを記憶する境界ポインタBD_Pと、要素の初期値を記憶する初期値領域INTとを有する。境界ポインタBD_Pには境界BDの右側のインデックス「６」が書き込まれている。初期値領域INTには一例として初期値「０」が書き込まれている。
【００３７】
境界で二分割された左側の第１領域は未書込みブロックの数が記憶されるＭ領域と、右側の第２領域は書込みブロックの数が記憶されるＷ領域と、それぞれ称する。分割方法は、Ｍ領域の未書込みブロック（ＭＰと称する）の数と、Ｗ領域の書込み済みブロック（ＷＰと称する）の数とが同数になる位置に境界BDを選択することである。この境界は一意に定まる。
【００３８】
さらに、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰとを一対一に対応付ける。一対一の対応付けは、両ブロックＭＰ，ＷＰ間に双方向リンクを形成することで行われる。図中、双方向リンクは実線の矢印で示される。
【００３９】
具体的には、インデックス０，１の未書込みブロックＭＰとインデックス１２，１３の書込み済みブロックＷＰの場合、未書込みブロックＭＰのアドレスワードAWD（インデックス０の要素）には書込み済みブロックＷＰのインデックス「１２」が書き込まれ、書込み済みブロックＷＰのアドレスワードAWD（インデックス１２の要素）には未書込みブロックＭＰのインデックス「０」が書き込まれる。インデックス２，３のブロックＭＰとインデックス８，９のブロックＷＰも同様に双方向リンクを形成する。Ｍ領域内の未書込みブロックＭＰの数とＷ領域内の書込み済みブロックＷＰの数が同じになるよう境界BDを管理し、両ブロックＭＰ、ＷＰの間に双方向リンクを形成することで、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰを管理情報として記憶し、両ブロックの数を同数に管理する。
【００４０】
双方向リンクを形成するとＷ領域の書込み済みブロックＷＰのアドレスワードAWD（インデックス１２の要素）には値を書き込むことができない。そこで、Ｗ領域の書込み済みブロックＷＰのリンク先のＭ領域の未書込みブロックＭＰのデータワードDWD（インデックス１の要素）に値を書き込む。この点については後で詳述する。
【００４１】
一方、Ｍ領域の書込み済みブロックＭＳとＷ領域の未書込みブロックＷＳとが、一対一に対応付けされないように、つまり上記の双方向リンクができないように、Ｗ領域のブロックのアドレスワードにＭ領域の書込みブロックＭＳのインデックスが格納されないよう制御する。
【００４２】
具体的には、インデックス４，５の書込み済みブロックＭＳのアドレスワードには「１４」が書き込まれているので、インデックス１４，１５のブロックに片方リンクを形成している。そこで、インデックス１４，１５のブロックのアドレスワードにはＭ領域のインデックスが記憶されないようにする。図３の例では、インデックス１４，１５のブロックのアドレスワードには自分のインデックス「１４」が書き込まれている。また、インデックス６，７のブロックＷＳ、インデックス１０，１１のブロックＷＳは、未書込みブロックであり記憶されている値は読み出しでは参照されず（図中？で示す。）、初期値領域INTの値「０」が読み出される。
【００４３】
ブロックの種別は、対応付けのあるブロックをＰ（pair）ブロック、対応付けのないブロックをＳ（single）ブロックと称する。したがって、Ｍ領域とＷ領域にそれぞれＰブロックとＳブロックが存在しうるので、ブロックの種別は以下の４種類になる。
Ｍ領域
ＭＰ：未書込みブロック、ＷＰと双方向リンクが形成される。
ＭＳ：書込み済みブロック、Ｗ領域のブロックと双方向リンクは形成されない。
Ｗ領域
ＷＰ：書込み済みブロック、ＭＰと双方向リンクが形成される。
ＷＳ：未書込みブロック、Ｍ領域のブロックと双方向リンクは形成されない。
【００４４】
図４は、図３の配列の値の保存場所を説明する図である。図４の配列ARは図３の配列ARと同じである。まず、Ｍ領域の書込み済みブロックＭＳには、そのブロックの２つのワードに値を保存する。例えば、インデックス４，５のブロックＭＳが例である。
【００４５】
次に、Ｗ領域の書込み済みブロックＷＰには、そのブロックＷＰのデータワードDWDと、ブロックＷＰと双方向リンクするＭ領域の未書込みブロックＭＰのデータワードDWDとに２つの値を保存する。つまり、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰは双方向リンクを形成するためにアドレスワードAWDにはリンク先インデックスが互いに書き込まれる。したがって、アドレスワード以外のワードに値を保存する。例えば、ブロックＷＰのインデックス８に保存する値「０」はリンク先ブロックＭＰのインデックス３のデータワードDWDに保存される。また、ブロックＷＰのインデックス１２に保存される値「０」はリンク先ブロックＭＰのインデックス１のデータワードDWDに保存される。なお、１つのブロックの最小インデックスはアドレスワードであり、残りのインデックスはデータワードである。１ブロックのワード数をｂ≧２とすると、対応付けられた１対のブロックの２＊ｂワードのうち、２ワードがアドレスワードに、２＊ｂ−２のワードがデータワードとして使用される。
【００４６】
最後に、未書込みブロックＭＰ、ＷＳは、初期値が保存されているとみなし、初期値領域INTに値が保存され、ブロックＭＰ，ＷＳのワードには書込み値は保存されない。たとえば、インデックス１４，１５のブロックＷＳの値は、初期値領域INTの値である。
【００４７】
図４には、実際に保存されている値が示される実配列ARに対応して、保存されているインデックスと値を論理的に示した論理配列L_ARが示されている。特にインデックス８，１２に書き込まれた値「９」「０」は、それぞれインデックス３，１に保存されていることが論理配列L_ARに示される。
【００４８】
図３の初期化可能配列は、以下のような特徴を有する。
【００４９】
（１）配列の未だ書き込みが行われていない主領域に、書込み済み領域（ブロックＷＰ）と未書込み領域（ブロックＭＰ）を区別する管理情報（双方向リンク）を保存することで、管理の追加領域を境界ポインタBD_Pと初期値領域INTにする。したがって、管理の追加領域は配列サイズＮに依存するオーダより小さいＯ（ｌｏｇＮ）に、または後述する実施の形態のように固定サイズＯ（１）にする。
【００５０】
（２）配列の主領域の書込み済み領域と未書込み領域を区別する管理情報として、書込み済み領域のインデックスを記憶すると、書込みが進むに従い配列内の未書込み領域が減少するので、管理情報を保存できる領域が不足する。一方、管理情報として未書込み領域を記憶すると、初期化処理で全ての領域が未書込み領域になるので、初期化処理が配列サイズに依存する時間を要し定数時間で完了できない。そこで、書込み済み領域を記憶することと未書込み領域を記憶することをハイブリッド化する。すなわち、配列の主領域を、未書込み領域を管理するＭ領域と、書込み領域を管理するＷ領域とに分割し、初期化ではＭ領域のサイズを０にし、書込みが進むにつれてＷ領域のサイズが減少しＭ領域のサイズが増加するようにする。それにより、初期化時間を定数時間で完了し（境界ポインタをインデックス０にし初期値ｘを初期値領域に書き込む）、書込みが進むにつれて管理するＷ領域の書込み済み領域ＷＰの数を減らして管理情報（双方向リンク）が減少するよう制御する。また、書き込み時に管理情報（境界BD、双方リンク）の変更を行う。
【００５１】
（３）管理情報は配列の未書込み領域に保存するが、ユーザがどこに書き込むかどこに書き込まないかを決定するので、未書込み領域が断片化してしまう。そこで、配列の主領域をアドレスワードとデータワードを持つブロック単位で管理し、１対のブロックのアドレスワードを利用して双方向リンクを生成して管理情報を保存し、ユーザデータの一部を双方向リンク先のブロックのデータワードに保存する。
【００５２】
［配列制御プログラム］
次に、プロセッサにより実行される配列制御プログラムの処理、初期化可能配列の初期値ｘによる初期化initialize(x)、インデックスｉの読み出しread(i)、インデックスiに値ｘを書き込む書込みwrite(i,x)と、書込み機能を実現するための補助機能であるインデックスｉのブロックの非リンクunlink(i)、境界BDをシフトしてＭ領域を拡張するエクステンドextend()、それぞれの制御方法を説明する。
【００５３】
まず、プロセッサは、配列制御プログラムを実行して、初期化initialize(ｘ)が呼ばれると以下の初期化処理を行い、読み出しread(i)が呼ばれるとインデックスｉの値を読み出して返し、書込みwrite(i,x)が呼ばれるとインデックスｉに値ｘを書き込む。
【００５４】
［初期値ｘによる初期化initialize(x)］
図５は、初期化と非リンクの制御を示すフローチャート図である。図６は、初期化処理を示す図である。初期化initialize(x)が呼ばれると、配列制御プログラムを実行するプロセッサは、初期値領域INTに初期値ｘを保存し（S1）、境界ポインタBD_Pにインデックス０を保存して境界を左端に移動して初期化する（S2）。境界ポインタBD_Pには境界の右側のインデックスが保存される。境界の初期化により配列ARの主領域は全てＷ領域になり、双方向リンクはなくなり、Ｗ領域は全て未書込みブロックＷＳになる。図５の非リンクは後述する。
【００５５】
［インデックスｉの読み出しread(i)］
図７は、読み出しの制御を示すフローチャート図である。図８は、読み出し制御を示す図である。ここでは読み出し先インデックスｉのブロックをＢ１と称する。
【００５６】
読み出しread(i)が呼ばれると、配列制御プログラムを実行するプロセッサは、インデックスｉのブロックＢ１の種別をチェックする(S21)。ブロックの種別の判別は、インデックスｉが境界ポインタより小さいか（Ｍ領域）以上か（Ｗ領域）の判定と、インデックスｉのブロックが双方向リンクを持つか否か（双方向リンクならＭＰ，ＷＰ、それ以外ならＭＳ，ＷＳ）により行う。インデックスｉのブロックＢ１の種別がＭ領域の未書込みブロックＭＰまたはＷ領域の未書込みブロックＷＳの場合（S21のMPまたはWS）、初期値領域INT内の初期値を返して終了する（S22）。図８中のA:read(14)が一例である。
【００５７】
インデックスｉのブロックＢ１の種別がＭ領域の書込み済みブロックＭＳの場合(S21のMS)、インデックスｉに保存されている値を返して終了する(S23)。図８中のB:read(4)が一例である。
【００５８】
インデックスｉのブロックＢ１の種別がＷ領域の書込み済みブロックＷＰの場合(S21のWP)、インデックスｉがデータワードの場合(S24のYES)、インデックスｉに保存されている値を返して終了する(S23)。図８中のc-1:read(9)が一例である。逆に、インデックスｉがアドレスワードの場合(S24のNO)、ブロックＢ１に対応付けられた（双方向リンクされた）ブロックＭＰの該当するデータワードに保存されている値を返して終了する(S25)。図８中のc-2:read(8)が一例である。図８の例ではブロックのデータワードは１個しかないので、インデックス２のブロックＭＰのインデックス３のデータワードの値を返す。１つのブロックが複数のデータワードを有する場合、あらかじめ決められたデータワードに双方向リンク先のアドレスワードに書き込まれる値が保存される。
【００５９】
次に、書込みwrite(i,x)が呼ばれると、以下の非リンクunlink(i)と、境界をシフトするエクステンドextend()とを適宜呼んで、インデックスiに値xを書き込む処理が行われる。エクステンドextendは２種類のエクステンド処理Ｅ１，Ｅ２がある。書込みwriteは４種類の書込み処理Ｗ１、Ｗ２−１，Ｗ２−２，Ｗ２−３がある。また、それぞれの処理で、意図しないリンクが形成されたＭ領域のブロックのリンクを切断して種別ＭＳにする非リンクunlink処理が行われる。つまり、エクステンドextendと非リンクunlinkは、書き込みの補助機能である。
【００６０】
［インデックスｉのブロックの非リンクunlink(i)］
図５は、非リンクの制御を示すフローチャート図である。図９は、非リンクの制御を示す図である。非リンクunlinkは、種別ＭＳのブロックの値を書き替えた時にＷ領域のブロックと偶然双方向リンクができてしまう場合、意図してないリンクを切断して種別ＭＳを維持するなどの目的で使用する。非リンクは、偶然生成された双方向リンクのＷ領域側のブロックのアドレスワードを自身のインデックスで書き換えることで行われる。
【００６１】
非リンクunlink(i)が呼ばれると、配列制御プログラムを実行するプロセッサは、Ｍ領域のインデックスiのブロックＢ１に双方向リンクが形成されたＷ領域のブロックＢ２が存在するかチェックし(S11)、存在する場合、Ｗ領域のブロックＢ２のアドレスワードをＭ領域のブロック以外のインデックスに書き換える(S12)。具体的には、例えばＷ領域のブロックＢ２のアドレスワードを自身のインデックスに書き換える。
【００６２】
図９の具体例では、配列AR1でブロックＢ１がＭ領域の書込み済みブロックＭＳであり、一方Ｗ領域内の未書込みブロックＷＳ（Ｂ２）のアドレスワードに偶然「２」が保存されていたとする。配列AR2にて、インデックス２に値「１０」が書き込まれると、偶然にＭ領域の書込み済みブロックＢ１とＷ領域の未書込みブロックＢ２との間に意図しない双方向リンクが発生する。そこで、非リンクunlink(2)を呼び出し、Ｗ領域のブロックＢ２のアドレスワードに自身のインデックス「１０」を書き込んで意図しないリンクを切断する。非リンクにはＷ領域のインデックスを書き込めばよいが、前述のように自身のインデックスを書き込んでも良い。
【００６３】
［エクステンドextend()］
エクステンドextendは、未書込みブロックＭＰまたはＷＳに書込みが行われる場合、未書込みのブロックのうち一つのブロックに初期値を書込み、初期化された種別ＭＳのブロックを生成し返す処理である。そして、書込みwrite処理では、この初期化済みブロックＭＳに書込みが行われるか、初期化済みブロックＭＳの位置をユーザの書込み先に実質的に移動させ移動した初期化済みブロックに書込みが行われる。１つのブロックは２つ以上のワードを有しそのうち１つのワードに書込みが行われる。したがって、予め全ワードに初期値を書き込んだ初期化済みブロックＭＳを取得し、その初期化済みブロックＭＳの１つのワードに書込み値を書き込む（または移動した初期化済みブロックの１つのワードに書込み値を書き込む）。
【００６４】
別の言葉で説明すると、未書込みブロックＭＰまたはＷＳに書込みが行われると、未書込みブロックＭＰまたはＷＳが１つ減り、書込み済みブロックＭＳまたはＷＰが１つ増加する。そこで、エクステンドextend処理は、Ｍ領域のブロックＭＳとＷ領域のブロックＷＰの数を等しく保つための処理を行う。
【００６５】
図１０は、エクステンドextend()の制御のフローチャート図である。図１１は、境界に隣接するＷ領域のブロックＢ１の種別がＷＳの場合のエクステンド制御Ｅ１を示す図である。図１２は、境界に隣接するＷ領域のブロックＢ１の種別がＷＰの場合のエクステンド制御Ｅ２を示す図である。
【００６６】
図１０のフローチャートに示されるとおり、エクステンドextend()が呼ばれると、配列制御プログラムを実行するプロセッサは、境界に隣接するＷ領域のブロックＢ１（境界ポインタのインデックスのブロック）の種別を判定する(S31)。
【００６７】
（Ｅ１）図１１に示されるとおり、境界右ブロックＢ１が種別ＷＳの場合(S31のWS)、プロセッサは、この未書込みブロックＷＳ（Ｂ１）に初期値「０」を書込み(S32)、境界をシフトしてＭ領域を1ブロック分拡張し（S33）、必要な場合非リンクunlink処理してブロックＢ１の種別をＭＳにする（S34）。この初期化済み（初期値書込み済み）ブロックＭＳが、書き込み対象の空ブロックＭＳとしてリターンされる(S35)。つまり、この処理では、境界右ブロックＷＳ（Ｂ１）を直接初期化済みＭＳに変更し、直接境界右ブロックＷＳ（Ｂ１）を1減らしＭＳ（Ｂ１）を1増やし、ＭＰとＷＰの数に変動がなく、ＭＰとＷＰの数が等しい状態を維持する。
【００６８】
（Ｅ２）一方、図１２に示されるとおり、境界右ブロックＢ１が種別ＷＰの場合(S31のWP)、プロセッサは、この書込み済みブロックＷＰ（Ｂ１）のアドレスワードにそのリンク先ブロックＭＰ（Ｂ２）のデータワードに書き込んでいたデータを書込み（コピー）（S36）、リンク先ブロックＭＰ（Ｂ２）の全てのワードに初期値を書込む（S37）。そして、境界をシフトしてＭ領域を1ブロック拡張し（S38）、必要な非リンクunlink処理し（S39）、境界右ブロックＷＰ（Ｂ１）とそのリンク先ブロックＭＰ（Ｂ２）を共に書込み済みＭＳにする。この初期化済み（初期値書込み済み）ブロックＭＳ（Ｂ２）がリターンされる(S40)。つまり、この処理では、エクステンドによりＷＰ（Ｂ１）が１減るので、ＭＰ（Ｂ２）を１減らしＭＳを１増やすことで、ＭＰとＷＰの数が等しい状態を維持する。但し、境界右ブロックＷＰ（Ｂ１）のリンク先のＭＰ（Ｂ２）を初期化済みＭＳに変更することができないので、境界右ブロックＷＰ（Ｂ１）にそのリンク先ＭＰ（Ｂ２）のデータを書き込んでＭＳに変更し、リンク先ＭＰ（Ｂ２）に初期値を書き込んで初期化済みＭＳを生成する。これにより、Ｍ領域のＭＰとＷ領域のＷＰの数を等しく保つ数合わせを行う。
【００６９】
上記のとおり、エクステンドextend処理の意味は次の通りである。例えば、未書込みブロックＭＰに書込みが行われて書込み済みＭＳに変更されるとＭ領域のＭＰが減少し、一方、未書込みブロックＷＳに書込みが行われて書込み済みブロックＷＰに変更されるとＷ領域のＷＰが増加し、Ｍ,Ｗ領域の管理対象ブロックＭＰ,ＷＰのうちＭＰの減少またはＷＰの増加になる。その結果、ＭＰ,ＷＰの数を同じに保つという条件を維持するために、境界を右側にシフトさせて、ＭＰの減少にはＭＰの追加を行い、ＷＰの増加にもＭＰの追加を行うことが必要になる。
【００７０】
この数合わせのために、エクステンドextend処理を行う。上記の通り、エクステンドextend処理では、境界を右シフトし初期化済み（初期値書込み済み）ＭＳを生成する。そして、以下に説明するwrite処理では、この初期化済みＭＳに書込み値が直接書き込まれるか、初期化済みＭＳの位置を変更して変更後のブロックに書込み値が書き込まれる。
【００７１】
［インデックスiに値ｘの書込みwrite(i,x)］
図１３は、書込みwrite(i,x)の制御を示すフローチャート図である。また、図１４は、書込みの処理Ｗ１を示す図である。図１５，図１６，図１７は、書き込み処理Ｗ２−１，Ｗ２−２，Ｗ２−３をそれぞれ示す図である。ここでは、書込み先インデックスのブロックをＢ１、エクステンドextendにより取得するブロックをＢ２、ブロックＢ１と対応付けられているブロックをＢ３と称する。
【００７２】
書込みwrite(i,x)の呼び出しがあると、配列制御プログラムを実行中のプロセッサは、書込み先インデックスｉのブロックＢ１の種別を判別する(S51)。
【００７３】
（Ｗ１）図１４に示されるとおり、書込み先のインデックスｉのブロックＢ１の種別が書込み済みブロックＭＳまたはＷＰの場合（S51のMSまたはWP）、読み出しread処理と同じ方法で書込み先を特定し、その書込み先に書込み値ｘを書き込む。例えば、インデックスｉのブロックＢ１がＭＳの場合、インデックスｉのブロックＢ１（ＭＳ）に書込み値を書込み（S52）、非リンクunlinkを使って意図しないリンクを切断する（S53）。また、インデックスｉのブロックＢ１がＷＰの場合、インデックスｉがデータワードなら（S54のYES）、インデックスｉに書込み値ｘを書込み(S55)、アドレスワードなら（S54のNO）、書込み先のブロックＷＰ（Ｂ１）のリンク先ブロックＭＰのデータワードに値ｘを書き込む(S56)。図１４には、write(0,12)が工程S52で書き込まれ、write(9,12)が工程S55で書き込まれ、write(8,12)が工程S56で書き込まれることが示される。
【００７４】
（Ｗ２）書込み先のインデックスｉのブロックＢ１の種別が未書込みブロックＭＰまたはＷＳの場合、エクステンドextend処理を行って初期化済みブロックＢ２(ＭＳ)を取得する（S57）。
【００７５】
（Ｗ２−１）図１５に示すとおり、書込み先ブロックＢ１と初期化済みブロックＢ２とが同じブロックの場合（S58のYES）、書込み先ブロックＢ１が初期化済みＭＳであるので、書込み先がＭＳの場合と同様にインデックスｉに値ｘを書込み（S52）、必要なunlink処理をして意図しないリンクを切断してＭＳを維持する（S53）。図１５では、write(2,12)について、extendで書込み先ブロックＢ１（ＭＰ）がＭＳに変更され、代わりにインデックス６のブロックがＢ１のリンク先ブロックＷＰのリンク先に変更されている。そして、ＭＳに変更された書込み先ブロックＢ１に値「１２」が書き込まれ、unlink(2)によりリンクが切断されている。
【００７６】
つまり、書込みＷ２−１では、エクステンド処理で取得した初期化済みブロックＢ２(ＭＳ)が書込み先ブロックＢ１と一致したので、書込み先インデックスｉに値を書き込む。
【００７７】
（Ｗ２−２）図１６に示す通り、書込み先ブロックＢ１と初期化済みブロックＢ２とが異なるブロックで(S58のNO)、Ｂ１の種別がＷＳの場合（S59のWS）、書込み先ブロックＢ１（ＷＳ）とエクステンドで生成した初期化済みブロックＢ２（ＭＳ）の間に双方向リンクを作成して対応付け（S60）、書込み先ブロックＢ１（リンク付けでＷＳから変更したＷＰ）に初期値を書込む（S61）。そして、書込み先ブロックＢ１がＷＰの場合と同様に書込み値を書き込む（S54,55,56）。図１６では、write(10,12)について、書込み先インデックス１０がアドレスワードであるため、書込み先ブロックＢ１（ＷＰ）のリンク先ブロックＢ２（ＭＰ）のデータワード（インデックス３）に書込み値「１２」が書き込まれている。
【００７８】
つまり、書込み先ブロックＢ１をＷＳから初期化済みＷＰに変更して書き込む必要があるので、extendで取得した初期化済みブロックＢ２(ＭＳ)を上記初期化済みＷＰのリンク先ブロックＭＰに変更する。この変更は、実質的に、extend処理で取得した初期化済みブロックＢ２（ＭＳ）の位置を、書込み先ブロックＢ１（初期化済みＷＰ）に移動させたことを意味する。
【００７９】
（Ｗ２−３）図１７に示す通り、書込み先ブロックＢ１と初期化済みブロックＢ２とが異なるブロックで（S58のNO）、Ｂ１の種別がＭＰの場合（S59のMP）、書込み先ブロックＢ１（ＭＰ）のデータワードの値を初期化済みブロックＢ２（ＭＳ）に書き込んで（S62）、書込み先ブロックＢ１（ＭＰ）のリンク先ブロックＢ３（ＷＰ）と初期化済みブロックＢ２間にリンクを張る（S63）。この結果初期化済みブロックＢ２はＭＳからＭＰに変更される。そして、書込み先ブロックＢ１に初期値を書込んで（S64）初期化済みブロックＭＳとする。これによりextend処理で取得したブロックＢ２（初期化済みＭＳ）が実質的に書込み先ブロックＢ１に移動する。そして、書込み先ブロックＢ１がＭＳの場合と同様に値を書き込む（S52,S53）。すなわち、書込み先ブロックＢ１に書込み値を書込み（S52）、unlink処理で意図しないリンクを切断する（S53）。
【００８０】
つまり、書込み先ブロックＢ１をＭＰから初期化済みＭＳにして書き込む必要があるので、エクステンドで生成した初期化済みブロックＢ２(ＭＳ)を、書込み先ブロックＢ１の代えて、ブロックＢ３（ＷＰ）のリンク先ＭＰに変更する。これにより、実質的に、extendで取得したブロックＢ２(初期化済みＭＳ)を、書込み先Ｂ１(ＭＳ)のリンク先だったＢ３(ＷＰ)のリンク先に変更し、書込み先ブロックＢ１を初期化済みＭＳに変更してそこに値を書き込む。
【００８１】
［初期化、書込み、読み出しの具体例］
次に、初期化、書込み、読み出しを具体例に沿って説明する。以下の具体例では、初期化状態後の書き込みにより、未書込みブロックＷＳに書込みして書込み済みブロックＷＰが１増加し双方向リンクも増加し、境界右ブロックがＷＰの場合のエクステンドにより書込み済みブロックＷＰが１減少することを示す。また、エクステンドによりＭ領域が増加し、Ｗ領域が減少することを示す。さらに、Ｗ領域が少なくなると双方向シフトの数が減少し管理情報量が減少することを示す。
【００８２】
図１８は、初期化可能配列ARの具体例と、初期化を示す図である。配列AR0は、配列の長さ１６、1ブロックが２ワードを含む初期化可能配列である。境界ポインタBD_Pの値「１２」により境界BDがインデックス１１と１２の間にあることが示され、初期値領域INTの値「１３」が初期値であることが示される。したがって、配列の主領域の値は、境界ポインタの値が「０」の初期状態では不定値であり、境界ポインタの値が「０」より大きいと書込み済みブロックＭＳ、ＷＰ内の値は真の値である。また、ブロックの種別ＭＳ，ＭＰ，ＷＳ，ＷＰは実際に値が保存されているわけではない。ブロックの種別は、ブロックのインデックスｉ、境界ポインタBD_P、ブロック内のアドレスワードの値により定数時間で計算可能である。
【００８３】
初期化initialize(0)が呼ばれると、プロセッサは、配列制御プログラムを実行して、初期値「０」を設定する。具体的には、プロセッサは、配列AR1で、境界ポインタBD_Pの値を「０」に書き換え(図５のS1)、初期値ＩＮＴに初期値「０」を書き込む（S2）。境界ポインタが「０」になるので、全てのブロックの種別は未書込みブロックＷＳになる。また、全インデックスの値は不定値となる。
【００８４】
図１９は、図１６で説明した書込みＷ２−２の具体例を示す図である。配列AR2は初期状態の配列AR1と同じである。配列AR2で、書込みwrite(5,9)が呼ばれてプロセッサがインデックス５に値「９」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、境界BDに隣接するＷ領域のブロックの種別はＷＳである。
【００８５】
そこで、配列AR3では、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「２」に書き換えて境界BDをシフトし、Ｍ領域内に初期化済み（初期値「０」が書き込まれた）ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドextendは図１１の処理Ｅ１である。さらに、配列AR4では、プロセッサが書込み先ブロックＢ１と初期化済みブロックＭＳ（Ｂ２）との間に双方向リンクを作成し(S60)、書込み先インデックス５に書込み値「９」を書込む（S55）。このように、境界BDに隣接するＷ領域のブロック以外の未書込みブロックＷＳへの書込みが発生すると、エクステンドで境界がシフトしてＭ領域が増加しＷ領域が減少し、双方リンクが１増加する。
【００８６】
図２０は、図１６で説明した書込みＷ２−２の具体例を示す図である。配列AR5(=AR4)で、書込みwrite(10,8)が呼ばれてプロセッサがインデックス１０に値「８」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、境界BDに隣接するＷ領域のブロックの種別はＷＳである。
【００８７】
そこで、配列AR6で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「４」に書き換えて境界BDをシフトし、Ｍ領域内に初期化済み（初期値「０」が書き込まれた）ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドextendは図１１の処理Ｅ１である。さらに、配列AR7では、プロセッサが書込み先ブロックＢ１と初期化済みブロックＭＳ（Ｂ２）との間に双方向リンクを作成し(S60)、書込み先インデックス１０がアドレスワードであるので、書込み先ブロックＢ１のリンク先ブロックＢ２のデータワード(インデックス３)に書込み値「８」を書込む（S56）。図１９と同様に、境界BDに隣接するＷ領域のブロック以外の未書込みブロックＷＳへの書込みが発生すると、境界がシフトしてＭ領域が増加しＷ領域が減少し、双方リンクが１増加する。
【００８８】
図２１は、図１６で説明した書込みＷ２−３の具体例を示す図である。配列AR8(=AR7)で、書込みwrite(2,14)が呼ばれ、プロセッサがインデックス２に値「１４」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＭＰであり、境界BDに隣接するＷ領域のブロックの種別はＷＰである。
【００８９】
そこで、配列AR9で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「６」に書き換えて境界BDをシフトし、Ｍ領域内に初期化済み（初期値「０」が書き込まれた）ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドは図１２の処理Ｅ２である。さらに、配列AR10で、プロセッサが書込み先ブロックＢ１（ＭＰ）の内容を初期化済みブロックＢ２（ＭＳ）に書込み(S62)、書込み先ブロックＢ１のリンク先ブロックＢ３（ＷＰ）のアドレスワードにＢ２のインデックス０を書き込んで双方向リンクを変更する(S63)。また、書込み先ブロックＢ１に初期値を書き込んで初期化済みブロックＭＳに変更する(S64)。その後、配列AR11で、プロセッサが書込み先インデックス２に書込み値「１４」を書込み（S52）、配列AR12で書込み先ブロックＢ１に生成された意図しないリンクを切断する(S53)。この場合、エクステンドextendによりＭ領域が増加しＷ領域が減少し、さらに書込み済みブロックＷＰが１減少し、双方向リンクも１減少している。
【００９０】
図２２は、図１６で説明した書込みＷ２−１の具体例を示す図である。配列AR13(=AR12)で、書込みwrite(6,10)が呼ばれ、プロセッサがインデックス６に値「１０」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックＷＳであり、境界BDに隣接するＷ領域のブロックの種別はＷＳである。
【００９１】
そこで、配列AR14で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「８」に書き換えて境界BDをシフトし、Ｍ領域内に初期化済み（初期値「０」が書き込まれた）ブロックＭＳ（Ｂ２）を生成する(S57)。このエクステンドは図１２の処理Ｅ１である。そして、配列AR14では、書込み先ブロックＢ１とエクステンドで生成した初期化済みブロックＭＳ（Ｂ２）とが一致している(S58のYES)。そこで、配列AR15で、プロセッサが書込み先ブロックＢ１（ＭＳ）のインデックス６に値「１０」を書込み（S52）、書込み先ブロックＢ１に意図しないリンクが発生しないことを確認する(S53)。この場合、エクステンドextendによりＭ領域が増加しＷ領域が減少し、しかし未書込みブロックＭＰと書込み済みブロックＷＰの数は不変で、双方向リンク数も不変である。
【００９２】
図２３は、図１６で説明した書込みＷ１の具体例を示す図である。配列AR16(=AR15)で、書込みwrite(4,12)が呼ばれ、プロセッサがインデックス４に値「１２」を書き込む。この書込みの場合、書き込むブロックの種別は書込み済みブロックＭＳである(S51のMS)。書込み済みブロックに書き込むので、エクステンドextendにより境界をシフトして初期化済みブロックＭＳを生成する必要はない。
【００９３】
そこで、配列AR17で、プロセッサが書込み先ブロックＢ１（ＭＳ）のインデックス４に値「１２」を書込む（S52）。この書き込みにより、書込み先ブロックＢ１にインデックス８のブロックとの間に意図しないリンクが発生している。そこで、配列AR18で、インデックス８に自身のインデックス８を書き込んで意図しないリンクを切断する(S53)。この場合、Ｍ領域とＷ領域の数は不変で、未書込みブロックＭＰと書込み済みブロックＷＰの数も不変、双方向リンク数も不変である。
【００９４】
以上のとおり、配列への書込みが繰り返されると境界が徐々にシフトしていく。初期化直後は双方向リンク数が少ないので、Ｍ領域のブロック数が少なくても少ない管理情報（双方向リンクの情報）を配列の主領域に保存することができる。その後、未書込みブロックＷＳへの書込みにより境界がシフトし徐々に双方向リンク数が増えるが、Ｍ領域のブロック数も増えるので増加する管理情報（双方向リンクの情報）を配列の主領域に保存できる。そして、境界がＷ領域の最大インデックスに近づいてくると、書込み済みブロックＷＰがエクステンドにより書込み済みブロックＭＳに変更されるなどにより双方向リンク数が減ってくる。その結果、Ｗ領域のブロック数が少なくても減少した管理情報を保存することができる。つまり、Ｍ領域の未書込みブロック数とＷ領域の書込み済みブロック数を管理するというハイブリッド的管理により、双方向リンクの最大数を抑制し、且つ合計書き込み数が少ないほど及び合計書き込み数が多いほど双方向リンクの数が少なく、配列内に双方向リンクの管理情報を保存することができる。
【００９５】
図２４は、読み出しreadの３種類の具体例を示す図である。配列AR19（＝AR18）で、読み出しread(1)が呼ばれ、プロセッサがインデックス１の値を読み出す。読み出し先ブロックの種別が未書込みブロックＭＰであるので(S21のMP)、プロセッサは初期値INTの値「０」を読み出して返す（S22）。
【００９６】
配列AR20で、読み出しread(2)が呼ばれ、プロセッサがインデックス２の値を読み出す。読み出し先ブロックの種別が書込み済みブロックＭＳであるので(S21のMS)、プロセッサはインデックス２の値「１４」を読み出して返す（S23）。
【００９７】
配列AR21で、読み出しread(8)が呼ばれ、プロセッサがインデックス８の値を読み出す。読み出し先ブロックの種別が未書込みブロックＷＳであるので(S21のWS)、プロセッサは初期値INTの値「０」を読み出して返す（S22）。
【００９８】
図２５は、読み出しreadの２種類の具体例と初期化initializeの具体例を示す図である。配列AR22（＝AR21）で、読み出しread(10)が呼ばれ、プロセッサがインデックス１０の値を読み出す。読み出し先ブロックの種別が書込み済みブロックＷＰであり(S21のWP)、読み出し先インデックスがアドレスワードであるので（S24のNO）、プロセッサは読み出し先ブロックＷＰのリンク先の未書込みブロックＭＰのデータワードの値「８」（インデックス１の値）を読み出して返す（S25）。
【００９９】
配列AR23で、読み出しread(11)が呼ばれ、プロセッサがインデックス１１の値を読み出す。読み出し先ブロックの種別が書込み済みブロックＷＰであり(S21のWP)、読み出し先インデックスがデータワードであるので（S24のYES）、プロセッサは読み出し先インデックス１１の値「０」を読み出して返す（S23）。
【０１００】
最後に、配列AR24では、初期化initialize(7)が呼ばれ、プロセッサにより初期値７で初期化されている。すなわち、プロセッサは境界ポインタBD_Pの値を「０」に書き換え（S2）、初期値領域INTを初期値「７」に書き換える（S1）。この結果、境界BDは配列の左端に移動し全てのブロックが未書込みブロックＷＳになる。
【０１０１】
［第２の実施の形態］
図２６は、第２の実施の形態における初期化可能配列を示す図である。配列ARは、初期値領域INTに初期化関数func(i)を設定する。それ以外は、第１の実施の形態と同じである。
【０１０２】
初期化関数func(i)の例３０では、初期化関数func(i)が呼ばれるとインデックスiの２倍の値「2*i」を返す。したがって、配列の未書込みブロックのインデックス６，７，１０，１１，１４，１５の読み出しread(i)が呼び出されると、プロセッサは、配列制御プログラムを実行して、初期値領域INTの初期化関数func(i)をコールし、値「2*i」を返す。その結果、インデックスiの２倍の値がリターンされる。
【０１０３】
図２７は、第２の実施の形態の配列の具体例を示す図である。この具体例は、例えば、サーバの設定ファイルを配列で定義し、プロトタイプのオブジェクト４０を初期値関数func(i)として生成しておく。そして、複数のインスタンスの設定ファイルの配列４０＿１，４０＿２を生成する場合、配列を初期化することでオブジェクト４０の複製をインスタンス４０＿１，４０＿２の配列として生成し、それぞれの配列の一部のみ書き換える。これにより、初期化と書込みを固定時間で行うことができ、複数のインスタンスの設定ファイルの作成を設定ファイルのサイズに依存しない固定時間で完了することができる。
【０１０４】
図中、３０は初期化関数func(i)の一例である。例えば、インスタンスの設定ファイル４０＿１，４０＿２を参照する場合、書き換えたインデックスを除くインデックスiの読み出しread(i)が呼び出されると、初期化関数func(i)が呼び出され、各インデックスｉに対応して設定項目と設定値、例えばversion=4, sevice=2など、が返される。
【０１０５】
［第３の実施の形態］
図２８は、第３の実施の形態における初期化可能配列を示す図である。第１、第２の実施の形態の配列は、境界ポインタBD_Pと初期値INTの管理情報を配列外の追加領域に保存する。したがって、管理情報のための追加領域のサイズは定数ワードＯ（ｌｏｇＮ）になる。logは底を２とする二進対数である。例えば、境界ポインタは配列のサイズＮの桁数（ビット数）の値を保存するので、logNに依存するオーダＯ（ｌｏｇＮ）になる。
【０１０６】
それに対して、第３の実施の形態の初期化可能配列は、境界ポインタBD_Pと初期値INTも配列内に保存し、代わりに１ビットのエクステンド完了フラグEX_Cを配列外に保存する。配列AR30に示されるとおり、エクステンドが繰り返されて最後にＭ領域になるＷ領域のブロックＢ１（最後ブロック）のアドレスワードAWD（インデックス１２）にもデータワードDWD（インデックス１５）にも使われないワード（インデックス１３，１４）に、定数ワードの管理情報として境界ポインタBD_Pと初期値INTを記憶する。
【０１０７】
それに伴い、ブロックサイズを、管理情報の定数ワード数＋２ワード（アドレスワード＋リンク先ブロックのアドレスワードの値を記憶するデータワード）にする。配列AR30の最後ブロックＢ１は、インデックス１２−１５が順にアドレスワードAWD、境界ポインタBD_P、初期値INT、データワードDWDの合計４ワードを持つ。
【０１０８】
具体的な制御は次の通りである。
（１）初期化で境界ポインタBD_P=0と初期値xをインデックス１３，１４に書込む。
（２）書込みが呼ばれてエクステンドするたびに境界ポインタBD_Pを書き換える。
（３）最後ブロックＢ１のアドレスワードAWD(インデックス１２)への書込みが呼ばれると、最後ブロックＢ１のリンク先ブロックＢ２のデータワード（インデックス５）に値を書き込む。
（４）最後ブロックＢ１の境界ポインタワード(インデックス１３)への書込みが呼ばれると、最後ブロックＢ１のリンク先ブロックＢ２のデータワード（インデックス６）に値を書き込む。
（５）最後ブロックＢ１の初期値ワード(インデックス１４)への書込みが呼ばれると、最後ブロックＢ１のリンク先ブロックＢ２のデータワード（インデックス７）に値を書き込む。
（６）配列AR30の状態（ブロックＢ１とＢ２とが双方向リンク）で、リンク先ブロックＢ２（ＭＰ）への書込みが呼ばれると、配列AR31のように、エクステンドされ、リンク先ブロックＢ２のデータワード（インデックス５，６，７）の値を最後ブロックＢ１に書込み、エクステンド完了フラグEX_Cを値「１」に書き換える。また、ブロックＢ２の書込み先インデックスに値が書き込まれる。この時点で、全てのブロックがＭ領域の書込み済みブロックＭＳになり、これ以上エクステンドは呼ばれないので、ブロックＢ１に記憶している境界ポインタと初期値を削除しても問題はない。
（７）その後の書込みは、全て書込み先ブロックＢ１が書込み済みブロックＭＳになり、インデックスｉに値が書き込まれる。
【０１０９】
上記の初期化可能配列は、配列外の追加領域はエクステンド完了フラグEX_Cの１ビットのみであり、追加領域はＯ（１）で、しかも１ビットである。これは、第１、第２の実施の形態の配列の追加領域のサイズ、定数ワードＯ（ｌｏｇＮ）より小さい。
【０１１０】
［初期化時間と追加領域の比較］
図２９は、図３７−３９の４つの例と第３の実施の形態の比較表を示す図である。５つの配列について、それぞれtime complexityとspace complexityが示され、time complexityについてはread, write, initializeについて、space complexityについては追加領域（extra space）について、それぞれサイズのオーダＯが示される。
【０１１１】
図３７−３９の４つの例と第３の実施の形態全てで、read, writeは固定時間Ｏ（１）であり、図３８（Ｂ）、図３９、第３の実施の形態で、initializeは固定時間Ｏ（１）である。一方、追加領域サイズのオーダについては、図３７が固定サイズＯ（１）であるものの、図３８−３２の３つの例は固定サイズではないが、第３の実施の形態は、固定サイズＯ（１）で、しかも１ビットである。第１、第２の実施の形態でも、追加領域サイズのオーダはＯ（ｌｏｇＮ）と、図３７−３９の例よりも十分に小さい。
【０１１２】
結局、第３の実施の形態がread, write, initialize時間、追加領域サイズの全てが配列サイズＮに依存しない固定時間、固定サイズである。第１、第２の実施の形態が、追加領域サイズがＯ（ｌｏｇＮ）と固定ではないが十分に小さいサイズである。
【０１１３】
［第４の実施の形態の初期化可能配列］
第１乃至第３の実施の形態の初期化可能配列では、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰの数が同数（ＭＰ：ＷＰ＝１：１）になる位置で配列を二分割する。しかし、同数にすることは必ずしも必要ではなく、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰの数を１：２、１：３または１：ｋ（ｋ≧１の整数）、Ｌ：Ｋ（Ｌ，Ｋは１以上の整数）にしてもよい。
【０１１４】
図３０は、第４の実施の形態における初期化可能配列を示す図である。この初期化可能配列ARは、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰの数が１：２になる位置で配列を二分割する。この配列も、読み出しと書き込みが配列サイズに依存しない定数時間で行われ、初期化も定数時間で行われる。さらに、配列内に書込み済みか未書込みかの情報を含ませることができるので、管理のための追加領域も配列サイズに依存しない定数サイズである。
【０１１５】
図３０の配列ARは、インデックス０≦ｉ＜１７でＮ（＝１８）個の要素を有し、１個のアドレスワードAWDと２個のデータワードDWDを含む３個のワード（主領域の各要素に対応）をそれぞれ有する複数のブロック（図３０の例は５個）を連続して構成する。
【０１１６】
各ブロックには３個の要素（ワード）が含まれ、ブロック内の最小インデックスの要素は後述する循環リンクC_LNKのリンク先インデックスを書き込むアドレスワードAWD、その他のインデックスの要素は値を書き込むデータワードDWDである。但し、アドレスワードにもデータが書き込まれる。
【０１１７】
さらに、管理領域として、配列の複数のブロックの二分割位置を示す境界BDを記憶する境界ポインタBD_Pと、要素の初期値を記憶する初期値領域INTと、後述する端数ブロックWBの位置を記憶するWBポインタWB_Pとを有する。境界ポインタBD_Pには境界BDの右側のインデックス「６」が書き込まれている。初期値領域INTには一例として初期値「０」が書き込まれている。また、WBポインタWB_Pにはインデックス「１２」が書き込まれている。
【０１１８】
前述のとおり、本実施の形態では、配列ARを二分割する境界BDが、Ｍ領域の未書込みブロックＭＰの数と、Ｗ領域の書込み済みブロックＷＰの数とが１：２になる位置に選択される。そして、Ｍ領域の１個の未書込みブロックＭＰと、Ｗ領域の２個の書込み済みブロックＷＰとで循環するリンクC_LNKが作成される。図３０に示されるとおり、循環リンクを形成する３つのブロック（１個のＭＰと２個のＷＰ）のアドレスワードAWD（インデックス３、９、１５のワード）に、それぞれのリンク先のブロックのインデックス「９」「１５」「３」が記憶される。そして、３つのリンクC_LNKにより、１個のＭＰと２個のＷＰとが循環してリンクされ循環リンクを形成する。
【０１１９】
双方向リンクと同様に、循環リンクを形成した場合、Ｗ領域の書込み済みブロックＷＰのアドレスワードAWDには値を書き込むことができない。そこで、Ｗ領域の書込み済みブロックＷＰと循環リンクを形成するＭ領域の未書込みブロックＭＰのデータワードDWD（インデックス４、５）に、書込み済みブロックＷＰのアドレスワードAWD（インデックス９、１５）の値を書き込む。
【０１２０】
但し、本実施の形態では、未書込みブロックＭＰの数と書込み済みブロックＷＰの数が１：２になるように分割できない場合がある。例えば、Ｗ領域内に奇数個（例えば３個）の書込み済みブロックＷＰが存在する場合、Ｍ領域に１個の未書込みブロックＭＰが存在する位置に境界BDを設定すると、ＭＰの数とＷＰの数の比が１：３になり、一方、Ｍ領域に２個の未書込みブロックＭＰが存在する位置に境界BDを設定すると、ＭＰの数とＷＰの数の比が２：３になり、いずれも１：２にならない。Ｗ領域内に１個の書込み済みブロックＷＰが存在する場合も、同様にＭ領域の未書込みブロックＭＰとの間で１：２の関係にならない。このような場合に、Ｗ領域の高々１個のブロックを端数ブロックＷＢとして扱い、端数ブロックＷＢの位置を示すＷＢポインタWB_Pを追加の管理領域として設ける。
【０１２１】
そして、後述する通り、所定の書き込み時に端数ブロックＷＢが生成され初期値で初期化され、書込みの値が直接書き込まれる。つまり、端数ブロックＷＢは、Ｍ領域内の書込み済みブロックＭＳと同様に、Ｗ領域内のリンクされていない単独の書込み済みブロックとして扱われる。さらに、端数ブロックがｋ−１個生成されていると所定の書き込みにより循環リンクが生成される。逆に、所定のエクステンド時に端数ブロックが循環リンクに加えられ、端数ブロックが存在しないと循環リンクが解消され減少する。
【０１２２】
以上の通り、Ｍ領域内の未書込みブロックＭＰの数とＷ領域内の書込み済みブロックＷＰの数が１：２になるよう境界BDを管理し、１個のブロックＭＰと２個のブロックＷＰの間に循環リンクを形成することで、Ｍ領域の未書込みブロックＭＰとＷ領域の書込み済みブロックＷＰの管理情報を配列内に記憶する。また、1：２に分割できない場合に端数ブロックを利用する。
【０１２３】
［読み出しread(i)］
図３１は、第４の実施の形態の配列での読み出し制御を示す図である。読み出しは、１：１に分割した第１の実施の形態と同様である。つまり、未書込みブロックＭＰ，ＷＳの読み出しでは、初期値INTの値「０」が戻り値となる。また、書込み済みブロックＭＳの読み出しでは、読み出しread(i)のインデックスｉの値が戻り値となり、書込み済みブロックＷＰの読み出しでは、インデックスｉがアドレスワードの場合は循環リンクを形成するブロックＭＰのデータワードの値が戻り値、データワードの場合はインデックスｉの値が戻り値になる。さらに、端数ブロックＷＢの読み出しでは、インデックスｉの値が戻り値になる。
【０１２４】
［希望しないリンクの解消（非リンク）unlink］
図３２は、希望しないリンクの解消を行うアンリンク制御を示す図である。アンリンクも１：１に分割した第１の実施の形態と同様である。つまり、図３２のブロックＷＰのインデックス「９」と「１５」のワードに自分のインデックス「９」「１５」を書き込むことで、２つのリンクが削除される。これにより、循環リンクが解消される。
【０１２５】
［エクステンドextend()］
（１）第１に、境界に隣接するＷ領域のブロックの種別が未書込みブロックＷＳの場合、図１１に示した１：１に分割した例と同じ制御である。つまり、未書込みブロックＷＳに初期値「０」を書込み、境界を移動し、unlinkを使って書込み済みブロックＭＳにし、その書込み済みブロックＭＳが獲得した空きブロックとして戻り値になる。
【０１２６】
第２に、境界に隣接するＷ領域のブロックの種別が書込み済みブロックＷＰの場合、端数ブロックが存在する場合と、存在しない場合とで処理が異なる（以下のエクステンド処理（２）（３））。
【０１２７】
（２）図３３は、境界に隣接するＷ領域のブロックがＷＰの場合で端数ブロックが存在する場合のエクステンド処理を示す図である。配列ＡＲ４２には、循環リンクが形成され、境界BDに隣接するＷ領域のブロックＢ１が書込み済みブロックＷＰであり、端数ブロックＷＢが存在する。そこで、隣接ブロックＢ１（ＷＰ）に代えて、端数ブロックＷＢを循環リンクに加えて端数ブロックＷＢを書込み済みブロックＷＰに変更する。この処理で、インデックス「４」の値「ａ」を隣接ブロックＢ１（ＷＰ）のアドレスワード（インデックス「９」）に書き込み、境界BDを移動することで、書込み済みブロックＭＳに変更する。さらに、端数ブロックＷＢのインデックス「１２」の値「ｅ」をインデックス「４」に書込み、インデックス「１２」に「１５」を書込むことで、端数ブロックＷＢをＷＰに変更する。その結果、配列ＡＲ４３が形成される。
【０１２８】
この状態で、さらに、配列ＡＲ４３にエクステンドextend()を実行する。このエクステンドでは端数ブロックが存在しないので、図３２で後述する処理が行われ、空きブロックＭＳを獲得することができる。つまり、２回のエクステンドを実行して書き込むための空きブロックＭＳを獲得する。
【０１２９】
（３）図３４は、境界に隣接するＷ領域のブロックがＷＰの場合で端数ブロックが存在しない場合のエクステンド処理を示す図である。配列ＡＲ４４には、循環リンクが形成され、境界BDに隣接するＷ領域のブロックＢ１が書込み済みブロックＷＰであるが、端数ブロックＷＢは存在しない。この場合は、循環リンクを２個のブロックＭＳと１個の端数ブロックＷＢに分解する。この処理で、インデックス「４」の値「ａ」をインデックス「９」に書込み、境界BDを移動することで、隣接ブロックＢ１をＷＰから書込み済みブロックＭＳに変更する。さらに、インデックス「５」の値「ｂ」をインデックス「１５」に書込み、端数ブロックＷＢを生成し、循環リンクを形成していたインデックス「３」のブロックＭＰを初期値「０」で初期化して空きブロックＭＳ（Ｂ２）に変更する。
【０１３０】
（４）なお、境界に隣接するＷ領域のブロックが端数ブロックＷＢの場合、境界BDを移動してその端数ブロックＷＢを書込み済みブロックＭＳに変更し、再度エクステンドを実行する。この再度のエクステンドにより空きブロックＭＳを獲得する。
【０１３１】
上記のとおり、エクステンドにより、境界に隣接するブロックが書込み済みブロックＷＰの場合、端数ブロックが存在する場合はその端数ブロックが循環リンクに加わり端数ブロックが消滅し、端数ブロックが存在しない場合は循環リンク分解されて消滅する。これにより循環リンクの数が減少する。
【０１３２】
［書込みwrite(i)］
（１）インデックスｉの書込み先ブロックＢ１が書込み済みブロックＭＳ、ＷＰの場合、書き込み処理は、図１４に示した１：１に分割した例と同じである。さらに、書込み先ブロックＢ１が未書込みブロックＭＰの場合、書き込み処理は、図１５、図１７に示した１：１に分割した例と同じである。
【０１３３】
（２）書込み先ブロックＢ１が端数ブロックＷＢの場合、端数ブロックに直接書き込む。つまり、ブロックＭＳの場合と同じである。
【０１３４】
次に、書込み先ブロックＢ１が未書込みブロックＷＳの場合は、端数ブロックが存在しない場合と、存在する場合とで書込み処理が異なる（以下の書き込み処理（３）（４））。
【０１３５】
（３）図３５は、書込み先ブロックＢ１が未書込みブロックＷＳの場合で、端数ブロックＷＢが存在しない場合の書き込み処理を示す図である。この場合、書込み先ブロックＢ１である未書込みブロックＷＳを初期値「０」で初期化して端数ブロックＷＢに変更し、その端数ブロックＷＢのインデックスｉ（ｉ＝１３）に値Ｘを書き込む。この場合、エクステンドは行わない。また、端数ブロックが新たに生成され、循環リンクは生成されない。
【０１３６】
（４）図３６は、書込み先ブロックＢ１が未書込みブロックＷＳの場合で、端数ブロックＷＢが存在する場合の書き込み処理を示す図である。この場合、配列ＡＲ４８にエクステンドを実行し、空きブロックＢ２として初期化済み（書込み済み）ブロックＭＳを獲得する。そして、書込み先ブロックＢ１（ＷＳ）と、空きブロックＢ２（ＭＳ）と、端数ブロックＢ３（ＷＢ）とで循環リンクC_LNKを作成する。さらに、循環リンクされた書込み先ブロックＢ１（ＷＰ）のインデックスiに書込み値「Ｘ」を書き込む。
【０１３７】
但し、エクステンド後に書込み先ブロックＢ１がＷＳ以外になっていれば、そのブロックの種別に対応した書き込み処理を実行する。
【０１３８】
以上の通り、書込み先ブロックＢ１が未書込みブロックＷＳの場合、端数ブロックが存在しないなら端数ブロックＷＢを生成してＷＢに書込み、端数ブロックが存在するなら循環ブロックを作成してＢ１に書込み値「Ｘ」を書込む。つまり、ＭＰ：ＷＰ＝１：２であるので、一部の書込みで一度端数ブロックを生成し、循環リンクが生成される。これにより循環リンクの数が増加する。
【０１３９】
［１：ｋ（ｋ≧１の整数）］
上記の１：２の例で理解できるとおり、ＭＰ：ＷＰが１：３，１：４でも端数ブロックを利用して同様に未書込みブロックＭＰと書込み済みブロックＷＰとを1：３または1：４のリンクにより管理することができる。１：３ではＷ領域内に高々２ブロックを端数ブロックとして扱い、１：４ではＷ領域内に高々３ブロックを端数ブロックとして扱う。
【０１４０】
さらに、１：ｋではＷ領域内に高々ｋ−１個のブロックを端数ブロックとして扱い、エクステンドの回数は最大でｋ回となる。ｋが定数である限り、処理時間をＯ（１）にすることができる。例えば、書込みにより端数ブロックが生成されｋ−１個の端数ブロックが生成された後、さらに書き込みにより１個のＭＰとｋ個のＷＰを有する循環ブロックが生成される。また、エクステンドにより端数ブロックが循環ブロックに加えられて減少してなくなった後、さらにエクステンドにより循環ブロックが解消され減少する。
【０１４１】
ＭＰ：ＷＰが任意の整数比（Ｌ：Ｋ、Ｌ，Ｋは１以上の整数）でも、上記の1：ｋの例を拡張することで、上記と同様に未書込みブロックＭＰと書込み済みブロックＷＰを配列内の値により管理可能である。つまり、Ｍ領域のＬ個の未書込みブロックＭＰとＷ領域のＫ−１個の端数ブロックが形成された後、書き込みによりＬ：Ｋの循環ブロックが生成され、エクステンドにより循環ブロックが解消され、端数ブロックが消滅するとさらに循環ブロックが解消される。
【０１４２】
したがって、上記の実施の形態によれば、未書込みブロックＭＰと書込み済みブロックＷＰの数の比を任意の整数比になるよう二分割する管理を行い、処理時間を固定時間Ｏ（１）に、サイズを小さいサイズＯ（ｌｏｇＮ）または固定サイズＯ（１）にすることができる。
【０１４３】
以上の実施の形態をまとめると，次の付記のとおりである。
【０１４４】
（付記１）
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
前記処理は、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御プログラム。
【０１４５】
（付記２）
前記第２領域の前記書込み先ブロックに値を書き込む処理は、書込み先インデックスが前記データワードなら前記書込み先インデックスの要素に値を書込み、前記書き込み先インデックスが前記アドレスワードなら前記第２領域の前記書込み先ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードに値を書き込む、付記１に記載の配列制御プログラム。
【０１４６】
（付記３）
前記処理は、さらに、
初期化が呼ばれると、全てのブロックが前記第２領域の未書込みブロックになるよう前記境界の位置を初期化し、前記初期化の初期値を記憶する初期化することを有し、付記１に記載の配列制御プログラム。
【０１４７】
（付記４）
前記処理は、さらに、
読み出しが呼ばれると、
読み出し先ブロックが未書込みブロックの場合、前記初期値を返し、
前記第１領域の書込み済みブロックの場合、読み出し先インデックスの値を返し、
前記第２領域の書込み済みブロックの場合、前記読み出し先インデックスが前記データワードなら前記読み出し先インデックスの値を返し、前記読み出し先インデックスが前記アドレスワードなら前記読み出し先ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードのデータを返すことを有する、付記３に記載の配列制御プログラム。
【０１４８】
（付記５）
前記処理は、さらに、
アクセス先インデックスと前記境界とに基づいてアクセス先が前記第１領域のブロックかまたは第２領域のブロックかを判別し、アクセス先ブロックが前記リンクを形成するか否かに基づいて前記アクセス先が前記第１領域の未書込みブロックかまたは前記第２領域の書込み済みブロックかを判別することを有する、付記１に記載の配列制御プログラム。
【０１４９】
（付記６）
前記処理は、さらに、
前記リンクの形成を目的とせず前記第１領域の書込み済みブロックの値を書き換えた場合、前記第２領域の未書込みブロックのアドレスワードを、前記第１領域の書込み済みブロックとリンクが形成されないよう制御する非リンクすることを有する、付記１に記載の配列制御プログラム。
【０１５０】
（付記７）
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックであり、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じ場合、前記書込み先ブロックに値を書込み、前記書込み先ブロックの不要なリンクを切断する非リンクを行うことを有する、付記１に記載の配列制御プログラム。
【０１５１】
(付記８)
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第１領域の未書込みブロックの場合、
前記書込み先ブロックである前記第１領域の未書込みブロックの値を、前記エクステンド処理で生成した前記第１領域の初期化済み書込みブロックに書込んで、前記書込み先ブロックである前記第１領域の未書込みブロックのリンク先の第２領域の書込み済みブロックと前記エクステンド処理で生成した前記第１領域の初期化済み書込みブロックとの間にリンクを生成し、前記書込み先ブロックである前記第１領域の未書込みブロックに値を書き込むことを有する、付記１に記載の配列制御プログラム。
【０１５２】
（付記９）
前記初期化可能配列は、前記配列に加えて、前記境界を記憶する境界領域と、前記初期値を記憶する初期値領域とを有し、
前記初期化することは、前記境界領域に前記配列の一端のインデックスを書き込み、前記初期値を前記初期値領域に書き込むことを含む、付記３に記載の配列制御プログラム。
【０１５３】
（付記１０）
前記初期値は、インデックスに対応して初期値を返す初期化関数に対応付けられる、付記３に記載の配列制御プログラム。
【０１５４】
（付記１１）
前記初期化可能配列は、前記配列に加えて、前記エクステンド処理が完了したことを示すエクステンド完了フラグを記憶する領域を有し、
前記複数のブロックは、管理情報のワード数に前記アドレスワードとデータワードの２を加算した数以上のデータワードを有し、
前記初期化することは、最後に前記第１領域に変化する前記第２領域の最後ブロックの管理情報のワードに前記境界と初期値を書込むことと、前記エクステンド完了フラグを未完了状態にクリアすることを含み、
前記書込みすることは、書込み先インデックスが前記第２領域の最後ブロックの前記管理情報のワードの場合、前記第２領域の最後ブロックとリンクを形成する前記第１領域の未書込みブロックのデータワードに書込み値を書込むことを含み、
前記エクステンド処理をすることは、前記エクステンド処理で前記第２領域の最後ブロックが第１領域のブロックに変化する場合、前記エクステンド完了フラグを完了状態にセットすることを含む、付記３に記載の配列制御プログラム。
【０１５５】
(付記１２)
前記整数比は、１：ｋで、前記ｋは１以上の整数であり、
前記リンクは、１個の第１領域内の未書込みブロックとｋ個の第２領域内の書込み済みブロックを循環するリンクである、付記１に記載の配列制御プログラム。
【０１５６】
(付記１３)
前記整数比が、１：ｋで、前記ｋが２以上の整数であり、
前記第２領域の高々ｋ−１個のブロックが初期化済みの端数ブロックとして管理される、付記１に記載の配置制御プログラム。
【０１５７】
（付記１４）
前記処理は、
前記書込みの書込み先ブロックが前記第２領域の未書込みブロックの場合に、
更に前記端数ブロックがｋ−１個より少ない場合は、前記書込み先ブロックを初期化して端数ブロックに変更し、前記変更した端数ブロックに値を書込み、
更に前記端数ブロックがｋ−１個存在する場合は、エクステンド処理を実行して前記第１の領域に初期化済みブロックを生成し、前記書込み先ブロックと前記ｋ−１個の端数ブロックと前記初期化済みブロックとに循環リンクを生成し、前記書込み先ブロックに値を書き込む、付記１３に記載の配置制御プログラム。
【０１５８】
(付記１５)
前記整数比は、Ｌ：Ｋで、前記Ｌ，Ｋは１以上の整数であり、
前記リンクは、Ｌ個の第１領域内の未書込みブロックとＫ個の第２領域内の書込み済みブロックを循環するリンクである、付記１に記載の配列制御プログラム。
【０１５９】
（付記１６）
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する配列制御方法であって、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御方法。
【０１６０】
（付記１７）
少なくともアドレスワードとデータワードを含む２以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第１領域内の未書き込みブロックの数と、前記二分割された第２領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を記憶する記憶装置と、
前記記憶装置にアクセス可能なプロセッサとを有し、
前記プロセッサは、
前記第１領域の未書込みブロックまたは前記第２領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第１領域を拡張し前記第１領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第２領域の未書込みブロックの場合、前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスワードに、前記第２領域の前記書込み先ブロックのアドレスを記憶し、前記第２領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第１領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第２領域の前記書込み先ブロックに値を書き込む、
配列制御装置。
【符号の説明】
【０１６１】
AR：配置（Array）
BD：境界（Boundary）
BD_P：境界ポインタ（Boundary Pointer）
INT：初期値（Initial Value）
Ｍ：未書込みブロックを記憶するＭ領域、第１領域
ＭＰ：Ｍ領域の未書込みブロック
ＭＳ：Ｍ領域の書込み済みブロック
Ｗ：書込み済みブロックを記憶するＷ領域、第２領域
ＷＳ：Ｗ領域の未書込みブロック
ＷＰ：Ｗ領域の書込み済みブロック
EX_C：エクステンド完了フラグ
read：読み出し
write：書込み
extend：エクステンド、エクステンド処理
initialize：初期化する
【図１】
2018037010.tif 000003
【図２】
2018037010.tif 000004
【図３】
2018037010.tif 000005
【図４】
2018037010.tif 000006
【図５】
2018037010.tif 000007
【図６】
2018037010.tif 000008
【図７】
2018037010.tif 000009
【図８】
2018037010.tif 000010
【図９】
2018037010.tif 000011
【図１０】
2018037010.tif 000012
【図１１】
2018037010.tif 000013
【図１２】
2018037010.tif 000014
【図１３】
2018037010.tif 000015
【図１４】
2018037010.tif 000016
【図１５】
2018037010.tif 000017
【図１６】
2018037010.tif 000018
【図１７】
2018037010.tif 000019
【図１８】
2018037010.tif 000020
【図１９】
2018037010.tif 000021
【図２０】
2018037010.tif 000022
【図２１】
2018037010.tif 000023
【図２２】
2018037010.tif 000024
【図２３】
2018037010.tif 000025
【図２４】
2018037010.tif 000026
【図２５】
2018037010.tif 000027
【図２６】
2018037010.tif 000028
【図２７】
2018037010.tif 000029
【図２８】
2018037010.tif 000030
【図２９】
2018037010.tif 000031
【図３０】
2018037010.tif 000032
【図３１】
2018037010.tif 000033
【図３２】
2018037010.tif 000034
【図３３】
2018037010.tif 000035
【図３４】
2018037010.tif 000036
【図３５】
2018037010.tif 000037
【図３６】
2018037010.tif 000038
【図３７】
2018037010.tif 000039
【図３８】
2018037010.tif 000040
【図３９】
2018037010.tif 000041