図面 (/)

技術 配列制御プログラム、配列制御方法、配列制御装置

出願人 富士通株式会社
発明者 河東孝後藤啓介稲越宏弥
出願日 2016年9月2日 (5年3ヶ月経過) 出願番号 2016-171852
公開日 2018年3月8日 (3年9ヶ月経過) 公開番号 2018-037010
状態 特許登録済
技術分野 メモリシステム
主要キーワード 結果初期 論理配列 定数領域 未完了状態 最小インデックス 書込み要素 補助領域 空ブロック
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2018年3月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

配列の管理領域を記憶する追加領域を小さくする。

解決手段

アドレスワードデータワードを含む定数個のワードを有する複数のブロックを連続して構成する配列を有し、複数のブロックの二分割位置を示す境界と配列の要素の初期値とを記憶し、二分割された第1領域内の未書き込みブロックの数と二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を境界とする配列を制御する。ブロックに対する書込みが呼ばれると境界を移動して第1領域を拡張し第1領域内に初期化済み書込みブロックを生成する処理を行い、第2領域の未書込みブロックへの書込みの場合、第1領域の初期化済み書込みブロックのアドレスワードに、第2領域の書込み先ブロックのアドレスを記憶し、第2領域の書込み先ブロックのアドレスワードに第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、第2領域の書込み先ブロックに値を書き込む。

概要

背景

配列(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に依存しない固定時間で行う必要がある場合に利用される。配列のデータ構造については以下の特許文献、非特許文献に記載がある。

概要

配列の管理領域を記憶する追加領域を小さくする。アドレスワードデータワードを含む定数個のワードを有する複数のブロックを連続して構成する配列を有し、複数のブロックの二分割位置を示す境界と配列の要素の初期値とを記憶し、二分割された第1領域内の未書き込みブロックの数と二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を境界とする配列を制御する。ブロックに対する書込みが呼ばれると境界を移動して第1領域を拡張し第1領域内に初期化済み書込みブロックを生成する処理を行い、第2領域の未書込みブロックへの書込みの場合、第1領域の初期化済み書込みブロックのアドレスワードに、第2領域の書込み先ブロックのアドレスを記憶し、第2領域の書込み先ブロックのアドレスワードに第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、第2領域の書込み先ブロックに値を書き込む。

目的

そこで,第1の側面の目的は,管理情報を記憶する追加領域のサイズを抑制する配列制御プログラム、配列制御方法、配列制御装置を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

少なくともアドレスワードデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、前記処理は、前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、前記第2領域の前記書込み先ブロックに値を書き込む、ことを有する配列制御プログラム。

請求項2

前記第2領域の前記書込み先ブロックに値を書き込む処理は、書込み先インデックスが前記データワードなら前記書込み先インデックスの要素に値を書込み、前記書き込み先インデックスが前記アドレスワードなら前記第2領域の前記書込み先ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードに値を書き込む、請求項1に記載の配列制御プログラム。

請求項3

前記処理は、さらに、初期化が呼ばれると、全てのブロックが前記第2領域の未書込みブロックになるよう前記境界の位置を初期化し、前記初期化の初期値を記憶する初期化することを有し、請求項1に記載の配列制御プログラム。

請求項4

前記処理は、さらに、読み出しが呼ばれると、読み出し先ブロックが未書込みブロックの場合、前記初期値を返し、前記第1領域の書込み済みブロックの場合、読み出し先インデックスの値を返し、前記第2領域の書込み済みブロックの場合、前記読み出し先インデックスが前記データワードなら前記読み出し先インデックスの値を返し、前記読み出し先インデックスが前記アドレスワードなら前記読み出し先ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードのデータを返すことを有する、請求項3に記載の配列制御プログラム。

請求項5

前記処理は、さらに、アクセス先インデックスと前記境界とに基づいてアクセス先が前記第1領域のブロックかまたは第2領域のブロックかを判別し、アクセス先ブロックが前記リンクを形成するか否かに基づいて前記アクセス先が前記第1領域の未書込みブロックかまたは前記第2領域の書込み済みブロックかを判別することを有する、請求項1に記載の配列制御プログラム。

請求項6

前記処理は、さらに、前記リンクの形成を目的とせず前記第1領域の書込み済みブロックの値を書き換えた場合、前記第2領域の未書込みブロックのアドレスワードを、前記第1領域の書込み済みブロックとリンクが形成されないよう制御する非リンクすることを有する、請求項1に記載の配列制御プログラム。

請求項7

前記処理は、さらに、前記書込みの書込み先ブロックが、前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックであり、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じ場合、前記書込み先ブロックに値を書込み、前記書込み先ブロックの不要なリンクを切断する非リンクを行うことを有する、請求項1に記載の配列制御プログラム。

請求項8

前記処理は、さらに、前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第1領域の未書込みブロックの場合、前記書込み先ブロックである前記第1領域の未書込みブロックの値を、前記エクステンド処理で生成した前記第1領域の初期化済み書込みブロックに書込んで、前記書込み先ブロックである前記第1領域の未書込みブロックのリンク先の第2領域の書込み済みブロックと前記エクステンド処理で生成した前記第1領域の初期化済み書込みブロックとの間にリンクを生成し、前記書込み先ブロックである前記第1領域の未書込みブロックに値を書き込むことを有する、請求項1に記載の配列制御プログラム。

請求項9

前記初期値は、インデックスに対応して初期値を返す初期化関数対応付けられる、請求項3に記載の配列制御プログラム。

請求項10

前記初期化可能配列は、前記配列に加えて、前記エクステンド処理が完了したことを示すエクステンド完了フラグを記憶する領域を有し、前記複数のブロックは、管理情報ワード数に前記アドレスワードとデータワードの2を加算した数以上のデータワードを有し、前記初期化することは、最後に前記第1領域に変化する前記第2領域の最後ブロックの管理情報のワードに前記境界と初期値を書込むことと、前記エクステンド完了フラグを未完了状態クリアすることを含み、前記書込みすることは、書込み先インデックスが前記第2領域の最後ブロックの前記管理情報のワードの場合、前記第2領域の最後ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードに書込み値を書込むことを含み、前記エクステンド処理することは、前記エクステンド処理で前記第2領域の最後ブロックが第1領域のブロックに変化する場合、前記エクステンド完了フラグを完了状態にセットすることを含む、請求項3に記載の配列制御プログラム。

請求項11

前記整数比は、1:kで、前記kは1以上の整数であり、前記リンクは、1個の第1領域内の未書込みブロックとk個の第2領域内の書込み済みブロックを循環するリンクである、請求項1に記載の配列制御プログラム。

請求項12

前記整数比が、1:kで、前記kが2以上の整数であり、前記第2領域の高々k−1個のブロックが初期化済みの端数ブロックとして管理される、請求項1に記載の配置制御プログラム

請求項13

前記処理は、前記書込みの書込み先ブロックが前記第2領域の未書込みブロックの場合に、更に前記端数ブロックがk−1個より少ない場合は、前記書込み先ブロックを初期化して端数ブロックに変更し、前記変更した端数ブロックに値を書込み、更に前記端数ブロックがk−1個存在する場合は、エクステンド処理を実行して前記第1の領域に初期化済みブロックを生成し、前記書込み先ブロックと前記k−1個の端数ブロックと前記初期化済みブロックとに循環リンクを生成し、前記書込み先ブロックに値を書き込む、請求項12に記載の配置制御プログラム。

請求項14

少なくともアドレスワードとデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する配列制御方法であって、前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、前記第2領域の前記書込み先ブロックに値を書き込む、ことを有する配列制御方法。

請求項15

少なくともアドレスワードとデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を記憶する記憶装置と、前記記憶装置にアクセス可能プロセッサとを有し、前記プロセッサは、前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、前記第2領域の前記書込み先ブロックに値を書き込む、配列制御装置。

技術分野

0001

本発明は,配列制御プログラム、配列制御方法、配列制御装置に関する。

背景技術

0002

配列(array)は、データ集計等で使用する基本的なデータ構造の一つである。配列はインデックスに対応してデータである値を記憶する記憶領域(主領域)を有する。配列は、インデックス0≦i<Nに対して、読み出し(read)と書込み(write)を実行し、あるインデックスiに対して読み出しを行うとインデックスiの主領域に最後に書き込まれた値を返す。通常の配列の初期化は、全てインデックスの主領域に初期値を書き込む初期化処理を行うため、配列サイズNに比例した初期化時間がかかる。

0003

一方、初期化可能配列(initializable array)というデータ構造は、上記の読み出し(read)と書込み(write)に加えて、初期化(initialize)を行うと全てのインデックス0≦i<Nの値を初期値にする。初期化可能配列は、初期化を特別にサポートする構成を有し、初期化処理を配列サイズNにかかわらず一定時間で行う。例えば、word RAM(Random Access Machine)モデルにおいて、初期化initialize(x)が呼ばれた時に初期値xを記憶しておき、各インデックスiに書込み(write)されたかどうかを示す管理情報を記憶しておき、書込みが行われていないインデックスに読み出し(read)が呼ばれた場合は初期化で記憶した初期値xを返す技術が知られている。

0004

このような初期化可能配列のデータ構造は、例えば、リアルタイムで動作しなければならないアプリケーションプログラムにおいて、初期化処理を配列のサイズNに依存しない固定時間で行う必要がある場合に利用される。配列のデータ構造については以下の特許文献、非特許文献に記載がある。

0005

特開平05−158783号公報
特開2002−207634号公報
特開2004−30353号公報
特表2009−521049号公報

先行技術

0006

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

発明が解決しようとする課題

0007

しかしながら、従来の初期化可能配列は、インデックスに書込みが行われたか否かを示す管理情報を記憶するための追加領域が、配列の主領域に加えて必要である。

0008

そこで,第1の側面の目的は,管理情報を記憶する追加領域のサイズを抑制する配列制御プログラム、配列制御方法、配列制御装置を提供することにある。

課題を解決するための手段

0009

第1の側面は,少なくともアドレスワードデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
前記処理は、
前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第2領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御プログラム、である。

発明の効果

0010

第1の側面によれば,配列の管理情報を記憶する追加領域のサイズを抑制することができる。

図面の簡単な説明

0011

初期化可能配列と配列制御プログラムの一例を示す図である。
配列制御装置の構成例を示す図である。
本実施の形態における初期化可能配列を示す図である。
図3の配列の値の保存場所を説明する図である。
初期化と非リンクの制御を示すフローチャート図である。
初期化処理を示す図である。
読み出しの制御を示すフローチャート図である。
読み出し制御を示す図である。
非リンクの制御を示す図である。
エクステンドextend()の制御のフローチャート図である。
境界に隣接するW領域のブロックB1の種別がWSの場合のエクステンド制御E1を示す図である。
境界に隣接するW領域のブロックB1の種別がWPの場合のエクステンド制御E2を示す図である。
書込みwrite(i,x)の制御を示すフローチャート図である。
書込みの処理W1を示す図である。
書き込み処理W2−1を示す図である。
書き込み処理W2−2を示す図である。
書き込み処理W2−3を示す図である。
初期化可能配列ARの具体例と、初期化を示す図である。
図16で説明した書込みW2−2の具体例を示す図である。
図16で説明した書込みW2−2の具体例を示す図である。
図16で説明した書込みW2−3の具体例を示す図である。
図16で説明した書込みW2−1の具体例を示す図である。
図16で説明した書込みW1の具体例を示す図である。
読み出しreadの3種類の具体例を示す図である。
読み出しreadの2種類の具体例と初期化initializeの具体例を示す図である。
第2の実施の形態における初期化可能配列を示す図である。
第2の実施の形態の配列の具体例を示す図である。
第3の実施の形態における初期化可能配列を示す図である。
図37−39の4つの例と第3の実施の形態の比較表を示す図である。
第4の実施の形態における初期化可能配列を示す図である。
第4の実施の形態の配列での読み出し制御を示す図である。
希望しないリンクの解消を行うアンリンク制御を示す図である。
境界に隣接するW領域のブロックがWPの場合で端数ブロックが存在する場合のエクステンド処理を示す図である。
境界に隣接するW領域のブロックがWPの場合で端数ブロックが存在しない場合のエクステンド処理を示す図である。
書込み先ブロックB1が未書込みブロックWSの場合で、端数ブロックWBが存在しない場合の書き込み処理を示す図である。
書込み先ブロックB1が未書込みブロックWSの場合で、端数ブロックWBが存在する場合の書き込み処理を示す図である。
配列の第1の例を示す図である。
初期化可能配列の2つの例を示す図である。
図38の2つの配列をハイブリッド化した配列の例である。

実施例

0012

図1は、初期化可能配列と配列制御プログラムの一例を示す図である。図1には、配列制御プログラムが初期化可能配列に対して行う制御が示される。図1中、処理制御部2は、処理対象データ1について所定の処理を実行し、その所定の処理に伴って初期化可能配列4に初期化(initialize)、読み出し(read)、書込み(write)を実行する。そして、配列制御部3は、初期化可能配列に対する初期化処理、書き込み処理、読み出し処理などの制御を実行する。初期化可能配列4には、配列の要素の初期値と、配列の書込み済み(または未書込み)インデックスなどの管理情報を記憶する管理領域5が設けられる。

0013

初期化可能配列4は、配列の要素のデータ(値)を記憶するメモリなどの記憶装置である。また、管理領域5は、初期値や書込み済み(または未書込み)インデックスなどの管理情報を記憶するメモリなどの記憶装置である。

0014

そして、処理制御部2は、コンピュータのプロセッサがあるアプリケーションプログラム(以下単にアプリケーション)を実行することにより構築される。また、配列制御部3は、プロセッサが配列制御プログラムを実行することにより構築される。

0015

図2は、配列制御装置の構成例を示す図である。配列制御装置は、プロセッサであるCPU(Central Processing Unit)10と、CPUによりアクセスされるRAM(Random Access Memory)などのメインメモリ12と、外部とのインターフェース14とを有し、それらがバス28を介して接続される。また、バス28には大容量の補助記憶装置20−26がCPUからアクセス可能に設けられる。補助記憶装置には、基本プログラムであるOS(Operating System)や各種ミドルウエアを格納する記憶装置20と、アプリケーションプログラム(以下、アプリケーションと称する)22と、処理対象データ23と、配列制御プログラム24とを記憶する記憶装置とを有する。さらに、CPUが配列制御プログラム24を実行して、記憶装置26内に記憶した初期化可能配列に対してアプリケーション22からの初期化処理、書き込み処理、読み出し処理を行う。記憶装置26内には初期化可能配列の主領域に加えて、その管理データを記憶する管理領域が記憶される。

0016

ここで、初期化可能配列について一例に基づいて説明する。配列はインデックスに対応してデータを記憶する複数の要素を含む主領域を有する。そして、配列の「初期化」とは全ての要素を初期値で初期化することで、「書込み」とは初期化された要素に書込み値上書きすることで、「未書込み」とは初期化されたままの要素で未だ書込み値が上書きされていないことをそれぞれ意味する。

0017

図37は、配列の第1の例を示す図である。配列ARは、インデックスに対応してデータ(値)をそれぞれ記憶する複数の要素を含む主領域を有する。図37の配列ARは、主領域にインデックス0−7それぞれに対応する8つの要素を有する。また、主領域に加えて、ある集計値を記憶する集計値領域AGを有する。例えば、プロセッサがアプリケーションを実行して、8名のユーザのうちサーバに1日3回以上アクセスしたユーザ数をリアルタイムに集計する場合を想定する。つまり、配列ARのインデックス0−7は8名のユーザに対応し、各要素には各ユーザのアクセス回数が書き込まれる。そして、アクセス回数が3回以上のユーザ数が、集計値として集計値領域AGに記憶される。

0018

配列AR1は、初期化した状態を示す。すなわち、アプリケーションからの初期化処理の呼び出し応答して、プロセッサは配列制御プログラムを実行して、配列AR1の全ての要素に初期値0(アクセス数0回)を、集計値領域AG1には初期値0(0人)をそれぞれ書き込む。そして、配列AR2では、インデックス2に対応するユーザがアクセスしたことに伴い、アプリケーションによりインデックス2の要素の値「2」が加算されて「3」が書き込まれる。同時に、集計値領域AG1の値「3」が加算されて「4」が書き込まれる。最後に、アプリケーションにより、要求された任意のタイミングで、配列AR3に対応する集計値領域AG3の値「4」が読み出される。そして、毎日所定のタイミングで、配列が初期化処理される。上記の初期化処理、配列の要素の値の読み出し処理、書込み処理は、配列制御プログラムによりプロセッサが実行する。

0019

図37の例では、初期化処理では、全てのインデックスに初期値「0」を書き込む必要がある。したがって、初期化処理は、配列サイズNに比例した時間O(N)がかかり、初期化処理中は配列に対して書込みや読み出しを実行できない。一方、読み出しと書込みは定数時間O(1)で可能である。図37の配列は、リアルタイムのサーバへのアクセス回数を記録するアプリケーションには不向きである。なお、前記Oはオーダー頭文字である。

0020

図38は、初期化可能配列の2つの例を示す図である。初期化可能配列とは、初期化を高速に行うことができるデータ構造である。初期化可能配列がサポートする機能には、次のものがある。
(1)読み出しread(i)では、インデックスiの要素の値を返す。
(2)書込みwrite(i,x)では、インデックスiの要素にxを書き込む。
(3)初期化initialize(x)では、全てのインデックス0≦i<Nの要素にxを書き込む。

0021

そして、プロセッサは、配列制御プログラムを実行することにより、初期化initialize(x)が呼ばれたとき、配列の全ての要素に初期値xを書き込まず単に初期値xを記憶し、各インデックスについて書込みされたか否かの管理情報を記憶する。そして、書き込みされてないインデックスiへの読み出しread(i)が呼ばれた場合、初期化で記憶した初期値xを返す。これにより、初期化処理を配列のサイズNに依存しない固定時間で行う。

0022

図38(A)の配列では、インデックス0−15のN=16の要素を有する配列ARが、4要素ずつのブロック0−3に分割され、管理領域として、各ブロックの未書込みと書込み済みを区別するビットマップBT_MPと、配列の全要素の初期値を記憶する初期値領域INTとを有する。プロセッサが配列制御プログラムを実行し、初期化が呼ばれると初期値領域INTに初期値「0」が書き込まれ、ビットマップブロックに「0」が書き込まれる。初期化では全インデックスに初期値を書き込むことは行わない。書き込みが呼ばれると、そのブロックの書込み先インデックスに書込み値が書き込まれ残りのインデックスに初期値「0」が書き込まれ、ビットマップの対応するブロックに書込み済みを示す「1」が書き込まれる。ビットマップは、書込みが行われたブロックには「1」を、未書込みのブロックには「0」を記憶し、書込み済みブロックと未書込みブロックの管理情報を記憶する。

0023

図38(A)の配列では、初期化は図37の配列より短い時間O(N/logN)で完了するが、ビットマップを初期化する必要があるので初期化時間は配列サイズNに依存する時間o(N)である。なお、時間o(N)=O(N/logN)は、時間O(N)より短いことを意味し、logは底を2とする二進対数である。但し、管理情報として初期値INTに加えてビットマップBT_MPが含まれるので、管理にO(N/logN)=o(N)の追加領域が必要になる。つまり、ビットマップはブロック毎の要素を有するので、配列サイズNに依存した領域O(N)より小さいが領域o(N)が必要である。

0024

図38(B)の配列は、インデックス0−15のN=16の要素を有する配列ARに加えて、管理情報を記憶するための補助領域AUX、スタック領域ST、スタックポインタ領域ST_P、初期値領域INTを有する。補助領域とスタック領域は共に16の要素を有する。この配列では、配列制御プログラムを実行するプロセッサが、配列ARのあるインデックスに書込みを行うと、補助領域の同じインデックスの要素とスタック領域の最小未書込み要素とに互いのインデックスを書き込んで双方向リンクを生成する。双方向リンクの生成とともに、スタックポインタが最大書込み要素のインデックスに更新される。

0025

図38(B)の例では、配列ARには5つのインデックスの要素に書込みが行われ、補助領域AUXの同じ5つのインデックスの要素とスタック領域の要素との間に双方向リンクが形成されている。例えば、配列のインデックス3には値「0」が書き込まれ、補助領域の同じインデックス3の値「4」に対応するスタック領域のインデックス4には補助領域のインデックス「3」が書き込まれ、補助領域とスタック領域との間で双方向リンクが形成されている。また、スタックポインタの値「4」は、スタック領域内の双方向リンクが形成されている最大インデックスを指している。

0026

読み出しが呼ばれると、プロセッサは、読み出し先インデックスiの補助領域の要素が双方向リンクを形成していれば、配列の読み出し先インデックスの値を返し、形成されていなければ初期値領域INTの値を返す。

0027

この配列において、初期化が呼ばれると初期値領域INTに初期値「0」を書込み、スタックポインタST_Pに最小インデックス「0」を書き込む。したがって、初期化に要する時間は配列サイズNに依存せず定数時間O(1)である。しかし、管理領域は配列の主領域の200%程度を要し、追加領域は配列サイズNに依存するO(N)である。

0028

図39は、図38の2つの配列をハイブリッド化した配列の例である。図39では、図38(A)と同様の配列ARの主領域とビットマップBT_MPを有する。さらに、ビットマップについて、図38(B)と同様の補助領域AUX、スタックST、スタックポインタST_Pを有する。ビットマップが配列ARの主領域より小さいサイズであり、その分管理領域を小さくできる。

0029

この例では、初期化が定数時間O(1)で可能である。一方、管理情報を記憶する管理領域にO(N/logN)=o(N)の追加領域が必要である。一般に、図38(A)のビットマップ法の3倍程度の追加領域になる。

0030

図37図38(A),図38(B),図39まとめると図37の配列は、初期化時間は配列サイズNに依存する(O(N))が、管理の追加領域は定数サイズ(O(1))である。図38(A)の配列は、初期化時間は配列サイズNに依存する時間よりも短く(O(N/logN)=o(N))、管理の追加領域も同様である(O(N/logN)=o(N))。図38(B)の配列は初期化時間は定数時間(O(1))であるが、管理の追加領域は配列サイズNに依存するサイズ(O(N))。そして、図39の配列は、初期化時間は定数時間(O(1))、管理の追加領域は配列サイズに依存するサイズより小さい(O(N/logN)=o(N))。

0031

以下説明する本実施の形態の配列は、初期化時間も定数時間、管理の追加領域も定数領域である。

0032

[第1の実施の形態の初期化可能配列]
図3は、本実施の形態における初期化可能配列を示す図である。この初期化可能配列は、読み出しと書き込みが配列サイズに依存しない定数時間で行われ、初期化も定数時間で行われる。さらに、管理の追加領域も配列サイズに依存しない定数サイズである。

0033

図3の配列ARは、インデックス0≦i<16でN(=16)個の要素を有し、アドレスワードとデータワードを含む2以上の定数個(図3の例は2個)のワード(主領域の各要素に対応)をそれぞれ有する複数(図3の例は8個)のブロックを連続して構成する。

0034

図3の例では、各ブロックには2個の要素(ワード)が含まれ(1ブロックが2ワードを含む)、ブロック内の最小インデックスの要素は後述する双方向リンクのリンク先インデックスを書き込むアドレスワード、その他のインデックスの要素は値を書き込むデータワードである。但し、アドレスワードにもデータが書き込まれる。

0035

ここで、値が書き込まれる要素をワードと称する理由は、要素に書き込まれる値が32ビット、64ビットなどのワードであることに起因する。

0036

さらに、配列の複数のブロックの二分割位置を示す境界BDを記憶する境界ポインタBD_Pと、要素の初期値を記憶する初期値領域INTとを有する。境界ポインタBD_Pには境界BDの右側のインデックス「6」が書き込まれている。初期値領域INTには一例として初期値「0」が書き込まれている。

0037

境界で二分割された左側の第1領域は未書込みブロックの数が記憶されるM領域と、右側の第2領域は書込みブロックの数が記憶されるW領域と、それぞれ称する。分割方法は、M領域の未書込みブロック(MPと称する)の数と、W領域の書込み済みブロック(WPと称する)の数とが同数になる位置に境界BDを選択することである。この境界は一意に定まる。

0038

さらに、M領域の未書込みブロックMPとW領域の書込み済みブロックWPとを一対一対応付ける。一対一の対応付けは、両ブロックMP,WP間に双方向リンクを形成することで行われる。図中、双方向リンクは実線の矢印で示される。

0039

具体的には、インデックス0,1の未書込みブロックMPとインデックス12,13の書込み済みブロックWPの場合、未書込みブロックMPのアドレスワードAWD(インデックス0の要素)には書込み済みブロックWPのインデックス「12」が書き込まれ、書込み済みブロックWPのアドレスワードAWD(インデックス12の要素)には未書込みブロックMPのインデックス「0」が書き込まれる。インデックス2,3のブロックMPとインデックス8,9のブロックWPも同様に双方向リンクを形成する。M領域内の未書込みブロックMPの数とW領域内の書込み済みブロックWPの数が同じになるよう境界BDを管理し、両ブロックMP、WPの間に双方向リンクを形成することで、M領域の未書込みブロックMPとW領域の書込み済みブロックWPを管理情報として記憶し、両ブロックの数を同数に管理する。

0040

双方向リンクを形成するとW領域の書込み済みブロックWPのアドレスワードAWD(インデックス12の要素)には値を書き込むことができない。そこで、W領域の書込み済みブロックWPのリンク先のM領域の未書込みブロックMPのデータワードDWD(インデックス1の要素)に値を書き込む。この点については後で詳述する。

0041

一方、M領域の書込み済みブロックMSとW領域の未書込みブロックWSとが、一対一に対応付けされないように、つまり上記の双方向リンクができないように、W領域のブロックのアドレスワードにM領域の書込みブロックMSのインデックスが格納されないよう制御する。

0042

具体的には、インデックス4,5の書込み済みブロックMSのアドレスワードには「14」が書き込まれているので、インデックス14,15のブロックに片方リンクを形成している。そこで、インデックス14,15のブロックのアドレスワードにはM領域のインデックスが記憶されないようにする。図3の例では、インデックス14,15のブロックのアドレスワードには自分のインデックス「14」が書き込まれている。また、インデックス6,7のブロックWS、インデックス10,11のブロックWSは、未書込みブロックであり記憶されている値は読み出しでは参照されず(図中?で示す。)、初期値領域INTの値「0」が読み出される。

0043

ブロックの種別は、対応付けのあるブロックをP(pair)ブロック、対応付けのないブロックをS(single)ブロックと称する。したがって、M領域とW領域にそれぞれPブロックとSブロックが存在しうるので、ブロックの種別は以下の4種類になる。
M領域
MP:未書込みブロック、WPと双方向リンクが形成される。
MS:書込み済みブロック、W領域のブロックと双方向リンクは形成されない。
W領域
WP:書込み済みブロック、MPと双方向リンクが形成される。
WS:未書込みブロック、M領域のブロックと双方向リンクは形成されない。

0044

図4は、図3の配列の値の保存場所を説明する図である。図4の配列ARは図3の配列ARと同じである。まず、M領域の書込み済みブロックMSには、そのブロックの2つのワードに値を保存する。例えば、インデックス4,5のブロックMSが例である。

0045

次に、W領域の書込み済みブロックWPには、そのブロックWPのデータワードDWDと、ブロックWPと双方向リンクするM領域の未書込みブロックMPのデータワードDWDとに2つの値を保存する。つまり、M領域の未書込みブロックMPとW領域の書込み済みブロックWPは双方向リンクを形成するためにアドレスワードAWDにはリンク先インデックスが互いに書き込まれる。したがって、アドレスワード以外のワードに値を保存する。例えば、ブロックWPのインデックス8に保存する値「0」はリンク先ブロックMPのインデックス3のデータワードDWDに保存される。また、ブロックWPのインデックス12に保存される値「0」はリンク先ブロックMPのインデックス1のデータワードDWDに保存される。なお、1つのブロックの最小インデックスはアドレスワードであり、残りのインデックスはデータワードである。1ブロックのワード数をb≧2とすると、対応付けられた1対のブロックの2*bワードのうち、2ワードがアドレスワードに、2*b−2のワードがデータワードとして使用される。

0046

最後に、未書込みブロックMP、WSは、初期値が保存されているとみなし、初期値領域INTに値が保存され、ブロックMP,WSのワードには書込み値は保存されない。たとえば、インデックス14,15のブロックWSの値は、初期値領域INTの値である。

0047

図4には、実際に保存されている値が示される実配列ARに対応して、保存されているインデックスと値を論理的に示した論理配列L_ARが示されている。特にインデックス8,12に書き込まれた値「9」「0」は、それぞれインデックス3,1に保存されていることが論理配列L_ARに示される。

0048

図3の初期化可能配列は、以下のような特徴を有する。

0049

(1)配列の未だ書き込みが行われていない主領域に、書込み済み領域(ブロックWP)と未書込み領域(ブロックMP)を区別する管理情報(双方向リンク)を保存することで、管理の追加領域を境界ポインタBD_Pと初期値領域INTにする。したがって、管理の追加領域は配列サイズNに依存するオーダより小さいO(logN)に、または後述する実施の形態のように固定サイズO(1)にする。

0050

(2)配列の主領域の書込み済み領域と未書込み領域を区別する管理情報として、書込み済み領域のインデックスを記憶すると、書込みが進むに従い配列内の未書込み領域が減少するので、管理情報を保存できる領域が不足する。一方、管理情報として未書込み領域を記憶すると、初期化処理で全ての領域が未書込み領域になるので、初期化処理が配列サイズに依存する時間を要し定数時間で完了できない。そこで、書込み済み領域を記憶することと未書込み領域を記憶することをハイブリッド化する。すなわち、配列の主領域を、未書込み領域を管理するM領域と、書込み領域を管理するW領域とに分割し、初期化ではM領域のサイズを0にし、書込みが進むにつれてW領域のサイズが減少しM領域のサイズが増加するようにする。それにより、初期化時間を定数時間で完了し(境界ポインタをインデックス0にし初期値xを初期値領域に書き込む)、書込みが進むにつれて管理するW領域の書込み済み領域WPの数を減らして管理情報(双方向リンク)が減少するよう制御する。また、書き込み時に管理情報(境界BD、双方リンク)の変更を行う。

0051

(3)管理情報は配列の未書込み領域に保存するが、ユーザがどこに書き込むかどこに書き込まないかを決定するので、未書込み領域が断片化してしまう。そこで、配列の主領域をアドレスワードとデータワードを持つブロック単位で管理し、1対のブロックのアドレスワードを利用して双方向リンクを生成して管理情報を保存し、ユーザデータの一部を双方向リンク先のブロックのデータワードに保存する。

0052

[配列制御プログラム]
次に、プロセッサにより実行される配列制御プログラムの処理、初期化可能配列の初期値xによる初期化initialize(x)、インデックスiの読み出しread(i)、インデックスiに値xを書き込む書込みwrite(i,x)と、書込み機能を実現するための補助機能であるインデックスiのブロックの非リンクunlink(i)、境界BDをシフトしてM領域を拡張するエクステンドextend()、それぞれの制御方法を説明する。

0053

まず、プロセッサは、配列制御プログラムを実行して、初期化initialize(x)が呼ばれると以下の初期化処理を行い、読み出しread(i)が呼ばれるとインデックスiの値を読み出して返し、書込みwrite(i,x)が呼ばれるとインデックスiに値xを書き込む。

0054

[初期値xによる初期化initialize(x)]
図5は、初期化と非リンクの制御を示すフローチャート図である。図6は、初期化処理を示す図である。初期化initialize(x)が呼ばれると、配列制御プログラムを実行するプロセッサは、初期値領域INTに初期値xを保存し(S1)、境界ポインタBD_Pにインデックス0を保存して境界を左端に移動して初期化する(S2)。境界ポインタBD_Pには境界の右側のインデックスが保存される。境界の初期化により配列ARの主領域は全てW領域になり、双方向リンクはなくなり、W領域は全て未書込みブロックWSになる。図5の非リンクは後述する。

0055

[インデックスiの読み出しread(i)]
図7は、読み出しの制御を示すフローチャート図である。図8は、読み出し制御を示す図である。ここでは読み出し先インデックスiのブロックをB1と称する。

0056

読み出しread(i)が呼ばれると、配列制御プログラムを実行するプロセッサは、インデックスiのブロックB1の種別をチェックする(S21)。ブロックの種別の判別は、インデックスiが境界ポインタより小さいか(M領域)以上か(W領域)の判定と、インデックスiのブロックが双方向リンクを持つか否か(双方向リンクならMP,WP、それ以外ならMS,WS)により行う。インデックスiのブロックB1の種別がM領域の未書込みブロックMPまたはW領域の未書込みブロックWSの場合(S21のMPまたはWS)、初期値領域INT内の初期値を返して終了する(S22)。図8中のA:read(14)が一例である。

0057

インデックスiのブロックB1の種別がM領域の書込み済みブロックMSの場合(S21のMS)、インデックスiに保存されている値を返して終了する(S23)。図8中のB:read(4)が一例である。

0058

インデックスiのブロックB1の種別がW領域の書込み済みブロックWPの場合(S21のWP)、インデックスiがデータワードの場合(S24のYES)、インデックスiに保存されている値を返して終了する(S23)。図8中のc-1:read(9)が一例である。逆に、インデックスiがアドレスワードの場合(S24のNO)、ブロックB1に対応付けられた(双方向リンクされた)ブロックMPの該当するデータワードに保存されている値を返して終了する(S25)。図8中のc-2:read(8)が一例である。図8の例ではブロックのデータワードは1個しかないので、インデックス2のブロックMPのインデックス3のデータワードの値を返す。1つのブロックが複数のデータワードを有する場合、あらかじめ決められたデータワードに双方向リンク先のアドレスワードに書き込まれる値が保存される。

0059

次に、書込みwrite(i,x)が呼ばれると、以下の非リンクunlink(i)と、境界をシフトするエクステンドextend()とを適宜呼んで、インデックスiに値xを書き込む処理が行われる。エクステンドextendは2種類のエクステンド処理E1,E2がある。書込みwriteは4種類の書込み処理W1、W2−1,W2−2,W2−3がある。また、それぞれの処理で、意図しないリンクが形成されたM領域のブロックのリンクを切断して種別MSにする非リンクunlink処理が行われる。つまり、エクステンドextendと非リンクunlinkは、書き込みの補助機能である。

0060

[インデックスiのブロックの非リンクunlink(i)]
図5は、非リンクの制御を示すフローチャート図である。図9は、非リンクの制御を示す図である。非リンクunlinkは、種別MSのブロックの値を書き替えた時にW領域のブロックと偶然双方向リンクができてしまう場合、意図してないリンクを切断して種別MSを維持するなどの目的で使用する。非リンクは、偶然生成された双方向リンクのW領域側のブロックのアドレスワードを自身のインデックスで書き換えることで行われる。

0061

非リンクunlink(i)が呼ばれると、配列制御プログラムを実行するプロセッサは、M領域のインデックスiのブロックB1に双方向リンクが形成されたW領域のブロックB2が存在するかチェックし(S11)、存在する場合、W領域のブロックB2のアドレスワードをM領域のブロック以外のインデックスに書き換える(S12)。具体的には、例えばW領域のブロックB2のアドレスワードを自身のインデックスに書き換える。

0062

図9の具体例では、配列AR1でブロックB1がM領域の書込み済みブロックMSであり、一方W領域内の未書込みブロックWS(B2)のアドレスワードに偶然「2」が保存されていたとする。配列AR2にて、インデックス2に値「10」が書き込まれると、偶然にM領域の書込み済みブロックB1とW領域の未書込みブロックB2との間に意図しない双方向リンクが発生する。そこで、非リンクunlink(2)を呼び出し、W領域のブロックB2のアドレスワードに自身のインデックス「10」を書き込んで意図しないリンクを切断する。非リンクにはW領域のインデックスを書き込めばよいが、前述のように自身のインデックスを書き込んでも良い。

0063

[エクステンドextend()]
エクステンドextendは、未書込みブロックMPまたはWSに書込みが行われる場合、未書込みのブロックのうち一つのブロックに初期値を書込み、初期化された種別MSのブロックを生成し返す処理である。そして、書込みwrite処理では、この初期化済みブロックMSに書込みが行われるか、初期化済みブロックMSの位置をユーザの書込み先に実質的に移動させ移動した初期化済みブロックに書込みが行われる。1つのブロックは2つ以上のワードを有しそのうち1つのワードに書込みが行われる。したがって、予め全ワードに初期値を書き込んだ初期化済みブロックMSを取得し、その初期化済みブロックMSの1つのワードに書込み値を書き込む(または移動した初期化済みブロックの1つのワードに書込み値を書き込む)。

0064

別の言葉で説明すると、未書込みブロックMPまたはWSに書込みが行われると、未書込みブロックMPまたはWSが1つ減り、書込み済みブロックMSまたはWPが1つ増加する。そこで、エクステンドextend処理は、M領域のブロックMSとW領域のブロックWPの数を等しく保つための処理を行う。

0065

図10は、エクステンドextend()の制御のフローチャート図である。図11は、境界に隣接するW領域のブロックB1の種別がWSの場合のエクステンド制御E1を示す図である。図12は、境界に隣接するW領域のブロックB1の種別がWPの場合のエクステンド制御E2を示す図である。

0066

図10のフローチャートに示されるとおり、エクステンドextend()が呼ばれると、配列制御プログラムを実行するプロセッサは、境界に隣接するW領域のブロックB1(境界ポインタのインデックスのブロック)の種別を判定する(S31)。

0067

(E1)図11に示されるとおり、境界右ブロックB1が種別WSの場合(S31のWS)、プロセッサは、この未書込みブロックWS(B1)に初期値「0」を書込み(S32)、境界をシフトしてM領域を1ブロック分拡張し(S33)、必要な場合非リンクunlink処理してブロックB1の種別をMSにする(S34)。この初期化済み(初期値書込み済み)ブロックMSが、書き込み対象空ブロックMSとしてリターンされる(S35)。つまり、この処理では、境界右ブロックWS(B1)を直接初期化済みMSに変更し、直接境界右ブロックWS(B1)を1減らしMS(B1)を1増やし、MPとWPの数に変動がなく、MPとWPの数が等しい状態を維持する。

0068

(E2)一方、図12に示されるとおり、境界右ブロックB1が種別WPの場合(S31のWP)、プロセッサは、この書込み済みブロックWP(B1)のアドレスワードにそのリンク先ブロックMP(B2)のデータワードに書き込んでいたデータを書込み(コピー)(S36)、リンク先ブロックMP(B2)の全てのワードに初期値を書込む(S37)。そして、境界をシフトしてM領域を1ブロック拡張し(S38)、必要な非リンクunlink処理し(S39)、境界右ブロックWP(B1)とそのリンク先ブロックMP(B2)を共に書込み済みMSにする。この初期化済み(初期値書込み済み)ブロックMS(B2)がリターンされる(S40)。つまり、この処理では、エクステンドによりWP(B1)が1減るので、MP(B2)を1減らしMSを1増やすことで、MPとWPの数が等しい状態を維持する。但し、境界右ブロックWP(B1)のリンク先のMP(B2)を初期化済みMSに変更することができないので、境界右ブロックWP(B1)にそのリンク先MP(B2)のデータを書き込んでMSに変更し、リンク先MP(B2)に初期値を書き込んで初期化済みMSを生成する。これにより、M領域のMPとW領域のWPの数を等しく保つ数合わせを行う。

0069

上記のとおり、エクステンドextend処理の意味は次の通りである。例えば、未書込みブロックMPに書込みが行われて書込み済みMSに変更されるとM領域のMPが減少し、一方、未書込みブロックWSに書込みが行われて書込み済みブロックWPに変更されるとW領域のWPが増加し、M,W領域の管理対象ブロックMP,WPのうちMPの減少またはWPの増加になる。その結果、MP,WPの数を同じに保つという条件を維持するために、境界を右側にシフトさせて、MPの減少にはMPの追加を行い、WPの増加にもMPの追加を行うことが必要になる。

0070

この数合わせのために、エクステンドextend処理を行う。上記の通り、エクステンドextend処理では、境界を右シフトし初期化済み(初期値書込み済み)MSを生成する。そして、以下に説明するwrite処理では、この初期化済みMSに書込み値が直接書き込まれるか、初期化済みMSの位置を変更して変更後のブロックに書込み値が書き込まれる。

0071

[インデックスiに値xの書込みwrite(i,x)]
図13は、書込みwrite(i,x)の制御を示すフローチャート図である。また、図14は、書込みの処理W1を示す図である。図15図16図17は、書き込み処理W2−1,W2−2,W2−3をそれぞれ示す図である。ここでは、書込み先インデックスのブロックをB1、エクステンドextendにより取得するブロックをB2、ブロックB1と対応付けられているブロックをB3と称する。

0072

書込みwrite(i,x)の呼び出しがあると、配列制御プログラムを実行中のプロセッサは、書込み先インデックスiのブロックB1の種別を判別する(S51)。

0073

(W1)図14に示されるとおり、書込み先のインデックスiのブロックB1の種別が書込み済みブロックMSまたはWPの場合(S51のMSまたはWP)、読み出しread処理と同じ方法で書込み先を特定し、その書込み先に書込み値xを書き込む。例えば、インデックスiのブロックB1がMSの場合、インデックスiのブロックB1(MS)に書込み値を書込み(S52)、非リンクunlinkを使って意図しないリンクを切断する(S53)。また、インデックスiのブロックB1がWPの場合、インデックスiがデータワードなら(S54のYES)、インデックスiに書込み値xを書込み(S55)、アドレスワードなら(S54のNO)、書込み先のブロックWP(B1)のリンク先ブロックMPのデータワードに値xを書き込む(S56)。図14には、write(0,12)が工程S52で書き込まれ、write(9,12)が工程S55で書き込まれ、write(8,12)が工程S56で書き込まれることが示される。

0074

(W2)書込み先のインデックスiのブロックB1の種別が未書込みブロックMPまたはWSの場合、エクステンドextend処理を行って初期化済みブロックB2(MS)を取得する(S57)。

0075

(W2−1)図15に示すとおり、書込み先ブロックB1と初期化済みブロックB2とが同じブロックの場合(S58のYES)、書込み先ブロックB1が初期化済みMSであるので、書込み先がMSの場合と同様にインデックスiに値xを書込み(S52)、必要なunlink処理をして意図しないリンクを切断してMSを維持する(S53)。図15では、write(2,12)について、extendで書込み先ブロックB1(MP)がMSに変更され、代わりにインデックス6のブロックがB1のリンク先ブロックWPのリンク先に変更されている。そして、MSに変更された書込み先ブロックB1に値「12」が書き込まれ、unlink(2)によりリンクが切断されている。

0076

つまり、書込みW2−1では、エクステンド処理で取得した初期化済みブロックB2(MS)が書込み先ブロックB1と一致したので、書込み先インデックスiに値を書き込む。

0077

(W2−2)図16に示す通り、書込み先ブロックB1と初期化済みブロックB2とが異なるブロックで(S58のNO)、B1の種別がWSの場合(S59のWS)、書込み先ブロックB1(WS)とエクステンドで生成した初期化済みブロックB2(MS)の間に双方向リンクを作成して対応付け(S60)、書込み先ブロックB1(リンク付けでWSから変更したWP)に初期値を書込む(S61)。そして、書込み先ブロックB1がWPの場合と同様に書込み値を書き込む(S54,55,56)。図16では、write(10,12)について、書込み先インデックス10がアドレスワードであるため、書込み先ブロックB1(WP)のリンク先ブロックB2(MP)のデータワード(インデックス3)に書込み値「12」が書き込まれている。

0078

つまり、書込み先ブロックB1をWSから初期化済みWPに変更して書き込む必要があるので、extendで取得した初期化済みブロックB2(MS)を上記初期化済みWPのリンク先ブロックMPに変更する。この変更は、実質的に、extend処理で取得した初期化済みブロックB2(MS)の位置を、書込み先ブロックB1(初期化済みWP)に移動させたことを意味する。

0079

(W2−3)図17に示す通り、書込み先ブロックB1と初期化済みブロックB2とが異なるブロックで(S58のNO)、B1の種別がMPの場合(S59のMP)、書込み先ブロックB1(MP)のデータワードの値を初期化済みブロックB2(MS)に書き込んで(S62)、書込み先ブロックB1(MP)のリンク先ブロックB3(WP)と初期化済みブロックB2間にリンクを張る(S63)。この結果初期化済みブロックB2はMSからMPに変更される。そして、書込み先ブロックB1に初期値を書込んで(S64)初期化済みブロックMSとする。これによりextend処理で取得したブロックB2(初期化済みMS)が実質的に書込み先ブロックB1に移動する。そして、書込み先ブロックB1がMSの場合と同様に値を書き込む(S52,S53)。すなわち、書込み先ブロックB1に書込み値を書込み(S52)、unlink処理で意図しないリンクを切断する(S53)。

0080

つまり、書込み先ブロックB1をMPから初期化済みMSにして書き込む必要があるので、エクステンドで生成した初期化済みブロックB2(MS)を、書込み先ブロックB1の代えて、ブロックB3(WP)のリンク先MPに変更する。これにより、実質的に、extendで取得したブロックB2(初期化済みMS)を、書込み先B1(MS)のリンク先だったB3(WP)のリンク先に変更し、書込み先ブロックB1を初期化済みMSに変更してそこに値を書き込む。

0081

[初期化、書込み、読み出しの具体例]
次に、初期化、書込み、読み出しを具体例に沿って説明する。以下の具体例では、初期化状態後の書き込みにより、未書込みブロックWSに書込みして書込み済みブロックWPが1増加し双方向リンクも増加し、境界右ブロックがWPの場合のエクステンドにより書込み済みブロックWPが1減少することを示す。また、エクステンドによりM領域が増加し、W領域が減少することを示す。さらに、W領域が少なくなると双方向シフトの数が減少し管理情報量が減少することを示す。

0082

図18は、初期化可能配列ARの具体例と、初期化を示す図である。配列AR0は、配列の長さ16、1ブロックが2ワードを含む初期化可能配列である。境界ポインタBD_Pの値「12」により境界BDがインデックス11と12の間にあることが示され、初期値領域INTの値「13」が初期値であることが示される。したがって、配列の主領域の値は、境界ポインタの値が「0」の初期状態では不定値であり、境界ポインタの値が「0」より大きいと書込み済みブロックMS、WP内の値は真の値である。また、ブロックの種別MS,MP,WS,WPは実際に値が保存されているわけではない。ブロックの種別は、ブロックのインデックスi、境界ポインタBD_P、ブロック内のアドレスワードの値により定数時間で計算可能である。

0083

初期化initialize(0)が呼ばれると、プロセッサは、配列制御プログラムを実行して、初期値「0」を設定する。具体的には、プロセッサは、配列AR1で、境界ポインタBD_Pの値を「0」に書き換え(図5のS1)、初期値INTに初期値「0」を書き込む(S2)。境界ポインタが「0」になるので、全てのブロックの種別は未書込みブロックWSになる。また、全インデックスの値は不定値となる。

0084

図19は、図16で説明した書込みW2−2の具体例を示す図である。配列AR2は初期状態の配列AR1と同じである。配列AR2で、書込みwrite(5,9)が呼ばれてプロセッサがインデックス5に値「9」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックWSであり、境界BDに隣接するW領域のブロックの種別はWSである。

0085

そこで、配列AR3では、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「2」に書き換えて境界BDをシフトし、M領域内に初期化済み(初期値「0」が書き込まれた)ブロックMS(B2)を生成する(S57)。このエクステンドextendは図11の処理E1である。さらに、配列AR4では、プロセッサが書込み先ブロックB1と初期化済みブロックMS(B2)との間に双方向リンクを作成し(S60)、書込み先インデックス5に書込み値「9」を書込む(S55)。このように、境界BDに隣接するW領域のブロック以外の未書込みブロックWSへの書込みが発生すると、エクステンドで境界がシフトしてM領域が増加しW領域が減少し、双方リンクが1増加する。

0086

図20は、図16で説明した書込みW2−2の具体例を示す図である。配列AR5(=AR4)で、書込みwrite(10,8)が呼ばれてプロセッサがインデックス10に値「8」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックWSであり、境界BDに隣接するW領域のブロックの種別はWSである。

0087

そこで、配列AR6で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「4」に書き換えて境界BDをシフトし、M領域内に初期化済み(初期値「0」が書き込まれた)ブロックMS(B2)を生成する(S57)。このエクステンドextendは図11の処理E1である。さらに、配列AR7では、プロセッサが書込み先ブロックB1と初期化済みブロックMS(B2)との間に双方向リンクを作成し(S60)、書込み先インデックス10がアドレスワードであるので、書込み先ブロックB1のリンク先ブロックB2のデータワード(インデックス3)に書込み値「8」を書込む(S56)。図19と同様に、境界BDに隣接するW領域のブロック以外の未書込みブロックWSへの書込みが発生すると、境界がシフトしてM領域が増加しW領域が減少し、双方リンクが1増加する。

0088

図21は、図16で説明した書込みW2−3の具体例を示す図である。配列AR8(=AR7)で、書込みwrite(2,14)が呼ばれ、プロセッサがインデックス2に値「14」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックMPであり、境界BDに隣接するW領域のブロックの種別はWPである。

0089

そこで、配列AR9で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「6」に書き換えて境界BDをシフトし、M領域内に初期化済み(初期値「0」が書き込まれた)ブロックMS(B2)を生成する(S57)。このエクステンドは図12の処理E2である。さらに、配列AR10で、プロセッサが書込み先ブロックB1(MP)の内容を初期化済みブロックB2(MS)に書込み(S62)、書込み先ブロックB1のリンク先ブロックB3(WP)のアドレスワードにB2のインデックス0を書き込んで双方向リンクを変更する(S63)。また、書込み先ブロックB1に初期値を書き込んで初期化済みブロックMSに変更する(S64)。その後、配列AR11で、プロセッサが書込み先インデックス2に書込み値「14」を書込み(S52)、配列AR12で書込み先ブロックB1に生成された意図しないリンクを切断する(S53)。この場合、エクステンドextendによりM領域が増加しW領域が減少し、さらに書込み済みブロックWPが1減少し、双方向リンクも1減少している。

0090

図22は、図16で説明した書込みW2−1の具体例を示す図である。配列AR13(=AR12)で、書込みwrite(6,10)が呼ばれ、プロセッサがインデックス6に値「10」を書き込む。この書込みの場合、書き込むブロックの種別は未書込みブロックWSであり、境界BDに隣接するW領域のブロックの種別はWSである。

0091

そこで、配列AR14で、プロセッサが、エクステンドextendにより境界ポインタBD_Pを「8」に書き換えて境界BDをシフトし、M領域内に初期化済み(初期値「0」が書き込まれた)ブロックMS(B2)を生成する(S57)。このエクステンドは図12の処理E1である。そして、配列AR14では、書込み先ブロックB1とエクステンドで生成した初期化済みブロックMS(B2)とが一致している(S58のYES)。そこで、配列AR15で、プロセッサが書込み先ブロックB1(MS)のインデックス6に値「10」を書込み(S52)、書込み先ブロックB1に意図しないリンクが発生しないことを確認する(S53)。この場合、エクステンドextendによりM領域が増加しW領域が減少し、しかし未書込みブロックMPと書込み済みブロックWPの数は不変で、双方向リンク数も不変である。

0092

図23は、図16で説明した書込みW1の具体例を示す図である。配列AR16(=AR15)で、書込みwrite(4,12)が呼ばれ、プロセッサがインデックス4に値「12」を書き込む。この書込みの場合、書き込むブロックの種別は書込み済みブロックMSである(S51のMS)。書込み済みブロックに書き込むので、エクステンドextendにより境界をシフトして初期化済みブロックMSを生成する必要はない。

0093

そこで、配列AR17で、プロセッサが書込み先ブロックB1(MS)のインデックス4に値「12」を書込む(S52)。この書き込みにより、書込み先ブロックB1にインデックス8のブロックとの間に意図しないリンクが発生している。そこで、配列AR18で、インデックス8に自身のインデックス8を書き込んで意図しないリンクを切断する(S53)。この場合、M領域とW領域の数は不変で、未書込みブロックMPと書込み済みブロックWPの数も不変、双方向リンク数も不変である。

0094

以上のとおり、配列への書込みが繰り返されると境界が徐々にシフトしていく。初期化直後は双方向リンク数が少ないので、M領域のブロック数が少なくても少ない管理情報(双方向リンクの情報)を配列の主領域に保存することができる。その後、未書込みブロックWSへの書込みにより境界がシフトし徐々に双方向リンク数が増えるが、M領域のブロック数も増えるので増加する管理情報(双方向リンクの情報)を配列の主領域に保存できる。そして、境界がW領域の最大インデックスに近づいてくると、書込み済みブロックWPがエクステンドにより書込み済みブロックMSに変更されるなどにより双方向リンク数が減ってくる。その結果、W領域のブロック数が少なくても減少した管理情報を保存することができる。つまり、M領域の未書込みブロック数とW領域の書込み済みブロック数を管理するというハイブリッド的管理により、双方向リンクの最大数を抑制し、且つ合計書き込み数が少ないほど及び合計書き込み数が多いほど双方向リンクの数が少なく、配列内に双方向リンクの管理情報を保存することができる。

0095

図24は、読み出しreadの3種類の具体例を示す図である。配列AR19(=AR18)で、読み出しread(1)が呼ばれ、プロセッサがインデックス1の値を読み出す。読み出し先ブロックの種別が未書込みブロックMPであるので(S21のMP)、プロセッサは初期値INTの値「0」を読み出して返す(S22)。

0096

配列AR20で、読み出しread(2)が呼ばれ、プロセッサがインデックス2の値を読み出す。読み出し先ブロックの種別が書込み済みブロックMSであるので(S21のMS)、プロセッサはインデックス2の値「14」を読み出して返す(S23)。

0097

配列AR21で、読み出しread(8)が呼ばれ、プロセッサがインデックス8の値を読み出す。読み出し先ブロックの種別が未書込みブロックWSであるので(S21のWS)、プロセッサは初期値INTの値「0」を読み出して返す(S22)。

0098

図25は、読み出しreadの2種類の具体例と初期化initializeの具体例を示す図である。配列AR22(=AR21)で、読み出しread(10)が呼ばれ、プロセッサがインデックス10の値を読み出す。読み出し先ブロックの種別が書込み済みブロックWPであり(S21のWP)、読み出し先インデックスがアドレスワードであるので(S24のNO)、プロセッサは読み出し先ブロックWPのリンク先の未書込みブロックMPのデータワードの値「8」(インデックス1の値)を読み出して返す(S25)。

0099

配列AR23で、読み出しread(11)が呼ばれ、プロセッサがインデックス11の値を読み出す。読み出し先ブロックの種別が書込み済みブロックWPであり(S21のWP)、読み出し先インデックスがデータワードであるので(S24のYES)、プロセッサは読み出し先インデックス11の値「0」を読み出して返す(S23)。

0100

最後に、配列AR24では、初期化initialize(7)が呼ばれ、プロセッサにより初期値7で初期化されている。すなわち、プロセッサは境界ポインタBD_Pの値を「0」に書き換え(S2)、初期値領域INTを初期値「7」に書き換える(S1)。この結果、境界BDは配列の左端に移動し全てのブロックが未書込みブロックWSになる。

0101

[第2の実施の形態]
図26は、第2の実施の形態における初期化可能配列を示す図である。配列ARは、初期値領域INTに初期化関数func(i)を設定する。それ以外は、第1の実施の形態と同じである。

0102

初期化関数func(i)の例30では、初期化関数func(i)が呼ばれるとインデックスiの2倍の値「2*i」を返す。したがって、配列の未書込みブロックのインデックス6,7,10,11,14,15の読み出しread(i)が呼び出されると、プロセッサは、配列制御プログラムを実行して、初期値領域INTの初期化関数func(i)をコールし、値「2*i」を返す。その結果、インデックスiの2倍の値がリターンされる。

0103

図27は、第2の実施の形態の配列の具体例を示す図である。この具体例は、例えば、サーバの設定ファイルを配列で定義し、プロトタイプオブジェクト40を初期値関数func(i)として生成しておく。そして、複数のインスタンスの設定ファイルの配列40_1,40_2を生成する場合、配列を初期化することでオブジェクト40の複製をインスタンス40_1,40_2の配列として生成し、それぞれの配列の一部のみ書き換える。これにより、初期化と書込みを固定時間で行うことができ、複数のインスタンスの設定ファイルの作成を設定ファイルのサイズに依存しない固定時間で完了することができる。

0104

図中、30は初期化関数func(i)の一例である。例えば、インスタンスの設定ファイル40_1,40_2を参照する場合、書き換えたインデックスを除くインデックスiの読み出しread(i)が呼び出されると、初期化関数func(i)が呼び出され、各インデックスiに対応して設定項目設定値、例えばversion=4, sevice=2など、が返される。

0105

[第3の実施の形態]
図28は、第3の実施の形態における初期化可能配列を示す図である。第1、第2の実施の形態の配列は、境界ポインタBD_Pと初期値INTの管理情報を配列外の追加領域に保存する。したがって、管理情報のための追加領域のサイズは定数ワードO(logN)になる。logは底を2とする二進対数である。例えば、境界ポインタは配列のサイズNの桁数ビット数)の値を保存するので、logNに依存するオーダO(logN)になる。

0106

それに対して、第3の実施の形態の初期化可能配列は、境界ポインタBD_Pと初期値INTも配列内に保存し、代わりに1ビットのエクステンド完了フラグEX_Cを配列外に保存する。配列AR30に示されるとおり、エクステンドが繰り返されて最後にM領域になるW領域のブロックB1(最後ブロック)のアドレスワードAWD(インデックス12)にもデータワードDWD(インデックス15)にも使われないワード(インデックス13,14)に、定数ワードの管理情報として境界ポインタBD_Pと初期値INTを記憶する。

0107

それに伴い、ブロックサイズを、管理情報の定数ワード数+2ワード(アドレスワード+リンク先ブロックのアドレスワードの値を記憶するデータワード)にする。配列AR30の最後ブロックB1は、インデックス12−15が順にアドレスワードAWD、境界ポインタBD_P、初期値INT、データワードDWDの合計4ワードを持つ。

0108

具体的な制御は次の通りである。
(1)初期化で境界ポインタBD_P=0と初期値xをインデックス13,14に書込む。
(2)書込みが呼ばれてエクステンドするたびに境界ポインタBD_Pを書き換える。
(3)最後ブロックB1のアドレスワードAWD(インデックス12)への書込みが呼ばれると、最後ブロックB1のリンク先ブロックB2のデータワード(インデックス5)に値を書き込む。
(4)最後ブロックB1の境界ポインタワード(インデックス13)への書込みが呼ばれると、最後ブロックB1のリンク先ブロックB2のデータワード(インデックス6)に値を書き込む。
(5)最後ブロックB1の初期値ワード(インデックス14)への書込みが呼ばれると、最後ブロックB1のリンク先ブロックB2のデータワード(インデックス7)に値を書き込む。
(6)配列AR30の状態(ブロックB1とB2とが双方向リンク)で、リンク先ブロックB2(MP)への書込みが呼ばれると、配列AR31のように、エクステンドされ、リンク先ブロックB2のデータワード(インデックス5,6,7)の値を最後ブロックB1に書込み、エクステンド完了フラグEX_Cを値「1」に書き換える。また、ブロックB2の書込み先インデックスに値が書き込まれる。この時点で、全てのブロックがM領域の書込み済みブロックMSになり、これ以上エクステンドは呼ばれないので、ブロックB1に記憶している境界ポインタと初期値を削除しても問題はない。
(7)その後の書込みは、全て書込み先ブロックB1が書込み済みブロックMSになり、インデックスiに値が書き込まれる。

0109

上記の初期化可能配列は、配列外の追加領域はエクステンド完了フラグEX_Cの1ビットのみであり、追加領域はO(1)で、しかも1ビットである。これは、第1、第2の実施の形態の配列の追加領域のサイズ、定数ワードO(logN)より小さい。

0110

[初期化時間と追加領域の比較]
図29は、図37−39の4つの例と第3の実施の形態の比較表を示す図である。5つの配列について、それぞれtime complexityとspace complexityが示され、time complexityについてはread, write, initializeについて、space complexityについては追加領域(extra space)について、それぞれサイズのオーダOが示される。

0111

図37−39の4つの例と第3の実施の形態全てで、read, writeは固定時間O(1)であり、図38(B)、図39、第3の実施の形態で、initializeは固定時間O(1)である。一方、追加領域サイズのオーダについては、図37が固定サイズO(1)であるものの、図38−32の3つの例は固定サイズではないが、第3の実施の形態は、固定サイズO(1)で、しかも1ビットである。第1、第2の実施の形態でも、追加領域サイズのオーダはO(logN)と、図37−39の例よりも十分に小さい。

0112

結局、第3の実施の形態がread, write, initialize時間、追加領域サイズの全てが配列サイズNに依存しない固定時間、固定サイズである。第1、第2の実施の形態が、追加領域サイズがO(logN)と固定ではないが十分に小さいサイズである。

0113

[第4の実施の形態の初期化可能配列]
第1乃至第3の実施の形態の初期化可能配列では、M領域の未書込みブロックMPとW領域の書込み済みブロックWPの数が同数(MP:WP=1:1)になる位置で配列を二分割する。しかし、同数にすることは必ずしも必要ではなく、M領域の未書込みブロックMPとW領域の書込み済みブロックWPの数を1:2、1:3または1:k(k≧1の整数)、L:K(L,Kは1以上の整数)にしてもよい。

0114

図30は、第4の実施の形態における初期化可能配列を示す図である。この初期化可能配列ARは、M領域の未書込みブロックMPとW領域の書込み済みブロックWPの数が1:2になる位置で配列を二分割する。この配列も、読み出しと書き込みが配列サイズに依存しない定数時間で行われ、初期化も定数時間で行われる。さらに、配列内に書込み済みか未書込みかの情報を含ませることができるので、管理のための追加領域も配列サイズに依存しない定数サイズである。

0115

図30の配列ARは、インデックス0≦i<17でN(=18)個の要素を有し、1個のアドレスワードAWDと2個のデータワードDWDを含む3個のワード(主領域の各要素に対応)をそれぞれ有する複数のブロック(図30の例は5個)を連続して構成する。

0116

各ブロックには3個の要素(ワード)が含まれ、ブロック内の最小インデックスの要素は後述する循環リンクC_LNKのリンク先インデックスを書き込むアドレスワードAWD、その他のインデックスの要素は値を書き込むデータワードDWDである。但し、アドレスワードにもデータが書き込まれる。

0117

さらに、管理領域として、配列の複数のブロックの二分割位置を示す境界BDを記憶する境界ポインタBD_Pと、要素の初期値を記憶する初期値領域INTと、後述する端数ブロックWBの位置を記憶するWBポインタWB_Pとを有する。境界ポインタBD_Pには境界BDの右側のインデックス「6」が書き込まれている。初期値領域INTには一例として初期値「0」が書き込まれている。また、WBポインタWB_Pにはインデックス「12」が書き込まれている。

0118

前述のとおり、本実施の形態では、配列ARを二分割する境界BDが、M領域の未書込みブロックMPの数と、W領域の書込み済みブロックWPの数とが1:2になる位置に選択される。そして、M領域の1個の未書込みブロックMPと、W領域の2個の書込み済みブロックWPとで循環するリンクC_LNKが作成される。図30に示されるとおり、循環リンクを形成する3つのブロック(1個のMPと2個のWP)のアドレスワードAWD(インデックス3、9、15のワード)に、それぞれのリンク先のブロックのインデックス「9」「15」「3」が記憶される。そして、3つのリンクC_LNKにより、1個のMPと2個のWPとが循環してリンクされ循環リンクを形成する。

0119

双方向リンクと同様に、循環リンクを形成した場合、W領域の書込み済みブロックWPのアドレスワードAWDには値を書き込むことができない。そこで、W領域の書込み済みブロックWPと循環リンクを形成するM領域の未書込みブロックMPのデータワードDWD(インデックス4、5)に、書込み済みブロックWPのアドレスワードAWD(インデックス9、15)の値を書き込む。

0120

但し、本実施の形態では、未書込みブロックMPの数と書込み済みブロックWPの数が1:2になるように分割できない場合がある。例えば、W領域内に奇数個(例えば3個)の書込み済みブロックWPが存在する場合、M領域に1個の未書込みブロックMPが存在する位置に境界BDを設定すると、MPの数とWPの数の比が1:3になり、一方、M領域に2個の未書込みブロックMPが存在する位置に境界BDを設定すると、MPの数とWPの数の比が2:3になり、いずれも1:2にならない。W領域内に1個の書込み済みブロックWPが存在する場合も、同様にM領域の未書込みブロックMPとの間で1:2の関係にならない。このような場合に、W領域の高々1個のブロックを端数ブロックWBとして扱い、端数ブロックWBの位置を示すWBポインタWB_Pを追加の管理領域として設ける。

0121

そして、後述する通り、所定の書き込み時に端数ブロックWBが生成され初期値で初期化され、書込みの値が直接書き込まれる。つまり、端数ブロックWBは、M領域内の書込み済みブロックMSと同様に、W領域内のリンクされていない単独の書込み済みブロックとして扱われる。さらに、端数ブロックがk−1個生成されていると所定の書き込みにより循環リンクが生成される。逆に、所定のエクステンド時に端数ブロックが循環リンクに加えられ、端数ブロックが存在しないと循環リンクが解消され減少する。

0122

以上の通り、M領域内の未書込みブロックMPの数とW領域内の書込み済みブロックWPの数が1:2になるよう境界BDを管理し、1個のブロックMPと2個のブロックWPの間に循環リンクを形成することで、M領域の未書込みブロックMPとW領域の書込み済みブロックWPの管理情報を配列内に記憶する。また、1:2に分割できない場合に端数ブロックを利用する。

0123

[読み出しread(i)]
図31は、第4の実施の形態の配列での読み出し制御を示す図である。読み出しは、1:1に分割した第1の実施の形態と同様である。つまり、未書込みブロックMP,WSの読み出しでは、初期値INTの値「0」が戻り値となる。また、書込み済みブロックMSの読み出しでは、読み出しread(i)のインデックスiの値が戻り値となり、書込み済みブロックWPの読み出しでは、インデックスiがアドレスワードの場合は循環リンクを形成するブロックMPのデータワードの値が戻り値、データワードの場合はインデックスiの値が戻り値になる。さらに、端数ブロックWBの読み出しでは、インデックスiの値が戻り値になる。

0124

[希望しないリンクの解消(非リンク)unlink]
図32は、希望しないリンクの解消を行うアンリンク制御を示す図である。アンリンクも1:1に分割した第1の実施の形態と同様である。つまり、図32のブロックWPのインデックス「9」と「15」のワードに自分のインデックス「9」「15」を書き込むことで、2つのリンクが削除される。これにより、循環リンクが解消される。

0125

[エクステンドextend()]
(1)第1に、境界に隣接するW領域のブロックの種別が未書込みブロックWSの場合、図11に示した1:1に分割した例と同じ制御である。つまり、未書込みブロックWSに初期値「0」を書込み、境界を移動し、unlinkを使って書込み済みブロックMSにし、その書込み済みブロックMSが獲得した空きブロックとして戻り値になる。

0126

第2に、境界に隣接するW領域のブロックの種別が書込み済みブロックWPの場合、端数ブロックが存在する場合と、存在しない場合とで処理が異なる(以下のエクステンド処理(2)(3))。

0127

(2)図33は、境界に隣接するW領域のブロックがWPの場合で端数ブロックが存在する場合のエクステンド処理を示す図である。配列AR42には、循環リンクが形成され、境界BDに隣接するW領域のブロックB1が書込み済みブロックWPであり、端数ブロックWBが存在する。そこで、隣接ブロックB1(WP)に代えて、端数ブロックWBを循環リンクに加えて端数ブロックWBを書込み済みブロックWPに変更する。この処理で、インデックス「4」の値「a」を隣接ブロックB1(WP)のアドレスワード(インデックス「9」)に書き込み、境界BDを移動することで、書込み済みブロックMSに変更する。さらに、端数ブロックWBのインデックス「12」の値「e」をインデックス「4」に書込み、インデックス「12」に「15」を書込むことで、端数ブロックWBをWPに変更する。その結果、配列AR43が形成される。

0128

この状態で、さらに、配列AR43にエクステンドextend()を実行する。このエクステンドでは端数ブロックが存在しないので、図32で後述する処理が行われ、空きブロックMSを獲得することができる。つまり、2回のエクステンドを実行して書き込むための空きブロックMSを獲得する。

0129

(3)図34は、境界に隣接するW領域のブロックがWPの場合で端数ブロックが存在しない場合のエクステンド処理を示す図である。配列AR44には、循環リンクが形成され、境界BDに隣接するW領域のブロックB1が書込み済みブロックWPであるが、端数ブロックWBは存在しない。この場合は、循環リンクを2個のブロックMSと1個の端数ブロックWBに分解する。この処理で、インデックス「4」の値「a」をインデックス「9」に書込み、境界BDを移動することで、隣接ブロックB1をWPから書込み済みブロックMSに変更する。さらに、インデックス「5」の値「b」をインデックス「15」に書込み、端数ブロックWBを生成し、循環リンクを形成していたインデックス「3」のブロックMPを初期値「0」で初期化して空きブロックMS(B2)に変更する。

0130

(4)なお、境界に隣接するW領域のブロックが端数ブロックWBの場合、境界BDを移動してその端数ブロックWBを書込み済みブロックMSに変更し、再度エクステンドを実行する。この再度のエクステンドにより空きブロックMSを獲得する。

0131

上記のとおり、エクステンドにより、境界に隣接するブロックが書込み済みブロックWPの場合、端数ブロックが存在する場合はその端数ブロックが循環リンクに加わり端数ブロックが消滅し、端数ブロックが存在しない場合は循環リンク分解されて消滅する。これにより循環リンクの数が減少する。

0132

[書込みwrite(i)]
(1)インデックスiの書込み先ブロックB1が書込み済みブロックMS、WPの場合、書き込み処理は、図14に示した1:1に分割した例と同じである。さらに、書込み先ブロックB1が未書込みブロックMPの場合、書き込み処理は、図15図17に示した1:1に分割した例と同じである。

0133

(2)書込み先ブロックB1が端数ブロックWBの場合、端数ブロックに直接書き込む。つまり、ブロックMSの場合と同じである。

0134

次に、書込み先ブロックB1が未書込みブロックWSの場合は、端数ブロックが存在しない場合と、存在する場合とで書込み処理が異なる(以下の書き込み処理(3)(4))。

0135

(3)図35は、書込み先ブロックB1が未書込みブロックWSの場合で、端数ブロックWBが存在しない場合の書き込み処理を示す図である。この場合、書込み先ブロックB1である未書込みブロックWSを初期値「0」で初期化して端数ブロックWBに変更し、その端数ブロックWBのインデックスi(i=13)に値Xを書き込む。この場合、エクステンドは行わない。また、端数ブロックが新たに生成され、循環リンクは生成されない。

0136

(4)図36は、書込み先ブロックB1が未書込みブロックWSの場合で、端数ブロックWBが存在する場合の書き込み処理を示す図である。この場合、配列AR48にエクステンドを実行し、空きブロックB2として初期化済み(書込み済み)ブロックMSを獲得する。そして、書込み先ブロックB1(WS)と、空きブロックB2(MS)と、端数ブロックB3(WB)とで循環リンクC_LNKを作成する。さらに、循環リンクされた書込み先ブロックB1(WP)のインデックスiに書込み値「X」を書き込む。

0137

但し、エクステンド後に書込み先ブロックB1がWS以外になっていれば、そのブロックの種別に対応した書き込み処理を実行する。

0138

以上の通り、書込み先ブロックB1が未書込みブロックWSの場合、端数ブロックが存在しないなら端数ブロックWBを生成してWBに書込み、端数ブロックが存在するなら循環ブロックを作成してB1に書込み値「X」を書込む。つまり、MP:WP=1:2であるので、一部の書込みで一度端数ブロックを生成し、循環リンクが生成される。これにより循環リンクの数が増加する。

0139

[1:k(k≧1の整数)]
上記の1:2の例で理解できるとおり、MP:WPが1:3,1:4でも端数ブロックを利用して同様に未書込みブロックMPと書込み済みブロックWPとを1:3または1:4のリンクにより管理することができる。1:3ではW領域内に高々2ブロックを端数ブロックとして扱い、1:4ではW領域内に高々3ブロックを端数ブロックとして扱う。

0140

さらに、1:kではW領域内に高々k−1個のブロックを端数ブロックとして扱い、エクステンドの回数は最大でk回となる。kが定数である限り、処理時間をO(1)にすることができる。例えば、書込みにより端数ブロックが生成されk−1個の端数ブロックが生成された後、さらに書き込みにより1個のMPとk個のWPを有する循環ブロックが生成される。また、エクステンドにより端数ブロックが循環ブロックに加えられて減少してなくなった後、さらにエクステンドにより循環ブロックが解消され減少する。

0141

MP:WPが任意の整数比(L:K、L,Kは1以上の整数)でも、上記の1:kの例を拡張することで、上記と同様に未書込みブロックMPと書込み済みブロックWPを配列内の値により管理可能である。つまり、M領域のL個の未書込みブロックMPとW領域のK−1個の端数ブロックが形成された後、書き込みによりL:Kの循環ブロックが生成され、エクステンドにより循環ブロックが解消され、端数ブロックが消滅するとさらに循環ブロックが解消される。

0142

したがって、上記の実施の形態によれば、未書込みブロックMPと書込み済みブロックWPの数の比を任意の整数比になるよう二分割する管理を行い、処理時間を固定時間O(1)に、サイズを小さいサイズO(logN)または固定サイズO(1)にすることができる。

0143

以上の実施の形態をまとめると,次の付記のとおりである。

0144

(付記1)
少なくともアドレスワードとデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する処理をコンピュータに実行させる配列制御プログラムであって、
前記処理は、
前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第2領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御プログラム。

0145

(付記2)
前記第2領域の前記書込み先ブロックに値を書き込む処理は、書込み先インデックスが前記データワードなら前記書込み先インデックスの要素に値を書込み、前記書き込み先インデックスが前記アドレスワードなら前記第2領域の前記書込み先ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードに値を書き込む、付記1に記載の配列制御プログラム。

0146

(付記3)
前記処理は、さらに、
初期化が呼ばれると、全てのブロックが前記第2領域の未書込みブロックになるよう前記境界の位置を初期化し、前記初期化の初期値を記憶する初期化することを有し、付記1に記載の配列制御プログラム。

0147

(付記4)
前記処理は、さらに、
読み出しが呼ばれると、
読み出し先ブロックが未書込みブロックの場合、前記初期値を返し、
前記第1領域の書込み済みブロックの場合、読み出し先インデックスの値を返し、
前記第2領域の書込み済みブロックの場合、前記読み出し先インデックスが前記データワードなら前記読み出し先インデックスの値を返し、前記読み出し先インデックスが前記アドレスワードなら前記読み出し先ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードのデータを返すことを有する、付記3に記載の配列制御プログラム。

0148

(付記5)
前記処理は、さらに、
アクセス先インデックスと前記境界とに基づいてアクセス先が前記第1領域のブロックかまたは第2領域のブロックかを判別し、アクセス先ブロックが前記リンクを形成するか否かに基づいて前記アクセス先が前記第1領域の未書込みブロックかまたは前記第2領域の書込み済みブロックかを判別することを有する、付記1に記載の配列制御プログラム。

0149

(付記6)
前記処理は、さらに、
前記リンクの形成を目的とせず前記第1領域の書込み済みブロックの値を書き換えた場合、前記第2領域の未書込みブロックのアドレスワードを、前記第1領域の書込み済みブロックとリンクが形成されないよう制御する非リンクすることを有する、付記1に記載の配列制御プログラム。

0150

(付記7)
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックであり、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じ場合、前記書込み先ブロックに値を書込み、前記書込み先ブロックの不要なリンクを切断する非リンクを行うことを有する、付記1に記載の配列制御プログラム。

0151

(付記8)
前記処理は、さらに、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第1領域の未書込みブロックの場合、
前記書込み先ブロックである前記第1領域の未書込みブロックの値を、前記エクステンド処理で生成した前記第1領域の初期化済み書込みブロックに書込んで、前記書込み先ブロックである前記第1領域の未書込みブロックのリンク先の第2領域の書込み済みブロックと前記エクステンド処理で生成した前記第1領域の初期化済み書込みブロックとの間にリンクを生成し、前記書込み先ブロックである前記第1領域の未書込みブロックに値を書き込むことを有する、付記1に記載の配列制御プログラム。

0152

(付記9)
前記初期化可能配列は、前記配列に加えて、前記境界を記憶する境界領域と、前記初期値を記憶する初期値領域とを有し、
前記初期化することは、前記境界領域に前記配列の一端のインデックスを書き込み、前記初期値を前記初期値領域に書き込むことを含む、付記3に記載の配列制御プログラム。

0153

(付記10)
前記初期値は、インデックスに対応して初期値を返す初期化関数に対応付けられる、付記3に記載の配列制御プログラム。

0154

(付記11)
前記初期化可能配列は、前記配列に加えて、前記エクステンド処理が完了したことを示すエクステンド完了フラグを記憶する領域を有し、
前記複数のブロックは、管理情報のワード数に前記アドレスワードとデータワードの2を加算した数以上のデータワードを有し、
前記初期化することは、最後に前記第1領域に変化する前記第2領域の最後ブロックの管理情報のワードに前記境界と初期値を書込むことと、前記エクステンド完了フラグを未完了状態クリアすることを含み、
前記書込みすることは、書込み先インデックスが前記第2領域の最後ブロックの前記管理情報のワードの場合、前記第2領域の最後ブロックとリンクを形成する前記第1領域の未書込みブロックのデータワードに書込み値を書込むことを含み、
前記エクステンド処理をすることは、前記エクステンド処理で前記第2領域の最後ブロックが第1領域のブロックに変化する場合、前記エクステンド完了フラグを完了状態にセットすることを含む、付記3に記載の配列制御プログラム。

0155

(付記12)
前記整数比は、1:kで、前記kは1以上の整数であり、
前記リンクは、1個の第1領域内の未書込みブロックとk個の第2領域内の書込み済みブロックを循環するリンクである、付記1に記載の配列制御プログラム。

0156

(付記13)
前記整数比が、1:kで、前記kが2以上の整数であり、
前記第2領域の高々k−1個のブロックが初期化済みの端数ブロックとして管理される、付記1に記載の配置制御プログラム

0157

(付記14)
前記処理は、
前記書込みの書込み先ブロックが前記第2領域の未書込みブロックの場合に、
更に前記端数ブロックがk−1個より少ない場合は、前記書込み先ブロックを初期化して端数ブロックに変更し、前記変更した端数ブロックに値を書込み、
更に前記端数ブロックがk−1個存在する場合は、エクステンド処理を実行して前記第1の領域に初期化済みブロックを生成し、前記書込み先ブロックと前記k−1個の端数ブロックと前記初期化済みブロックとに循環リンクを生成し、前記書込み先ブロックに値を書き込む、付記13に記載の配置制御プログラム。

0158

(付記15)
前記整数比は、L:Kで、前記L,Kは1以上の整数であり、
前記リンクは、L個の第1領域内の未書込みブロックとK個の第2領域内の書込み済みブロックを循環するリンクである、付記1に記載の配列制御プログラム。

0159

(付記16)
少なくともアドレスワードとデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を制御する配列制御方法であって、
前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第2領域の前記書込み先ブロックに値を書き込む、
ことを有する配列制御方法。

0160

(付記17)
少なくともアドレスワードとデータワードを含む2以上の定数個のワードをそれぞれ有する複数のブロックを連続して構成する配列を有し、前記配列の複数のブロックの二分割位置を示す境界と前記配列の要素の初期値とを記憶し、前記二分割された第1領域内の未書き込みブロックの数と、前記二分割された第2領域内の書込み済みブロックの数とが整数比になる位置を前記境界とする初期化可能配列を記憶する記憶装置と、
前記記憶装置にアクセス可能なプロセッサとを有し、
前記プロセッサは、
前記第1領域の未書込みブロックまたは前記第2領域の未書込みブロックに対する書込みが呼ばれると、前記境界を移動して前記第1領域を拡張し前記第1領域内に初期化済み書込みブロックを生成するエクステンド処理を行い、
前記書込みの書込み先ブロックが、前記エクステンド処理で生成した初期化済み書込み済みブロックと同じではなく、前記第2領域の未書込みブロックの場合、前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスワードに、前記第2領域の前記書込み先ブロックのアドレスを記憶し、前記第2領域の前記書込み先ブロックのアドレスワードに前記エクステンド処理で生成した第1領域の初期化済み書込みブロックのアドレスを記憶して、リンクを形成し、
前記第2領域の前記書込み先ブロックに値を書き込む、
配列制御装置。

0161

AR:配置(Array)
BD:境界(Boundary)
BD_P:境界ポインタ(Boundary Pointer)
INT:初期値(Initial Value)
M:未書込みブロックを記憶するM領域、第1領域
MP:M領域の未書込みブロック
MS:M領域の書込み済みブロック
W:書込み済みブロックを記憶するW領域、第2領域
WS:W領域の未書込みブロック
WP:W領域の書込み済みブロック
EX_C:エクステンド完了フラグ
read:読み出し
write:書込み
extend:エクステンド、エクステンド処理
initialize:初期化する

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ