JPH04127321A - 相対キーを利用したカウント分類法によるソート方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要］ 相対キーを利用したカウント分類法によるソート方式に
関し、 ハードウェア量を少なくシ、且つ、高速に、多量のレコ
ードを、キー値の順にソートする方式を提供することを
目的とし、 複数個のレコードを格納する入力用バッファと出力用バ
ッファと、該複数個の入力レコードの作業領域と、各レ
コードの順番を付けるカウンタ領域と備えて、該入力用
バッファに格納されたレコードのキー値の順にソートし
て出力用バッファに格納するのに、上記カウンタ領域を
、唯１つ設けて、上記入力用バッファに入力される複数
個のレコードに対して、特定のレコードのキー値を基準
値として設定し、そのキー値を′０゛とし、その他のレ
コードのキー値に対して、上記基準値のキーとの相対値
である相対キーを、相対キー＝（変換前のキー）−（基
準値のキー）で算出して、各レコードの相対キーを上記
作業領域に格納し、該格納した作業領域の相対キーが「
負」であるならば、上記カウンタ領域に“‘１’を加算
し、該相対キーが「正Ｊ、又は、「０」ならば、その儘
にする処理を繰り返し、上記入力用バッファの全レコー
ドに対して終了したとき、上記カウンタ領域に設定され
ている値だけ「空き」の出力用バッファをスキップした
場所に、上記基準値として設定したレコードを転送する
ことを繰り返してソートするように構成する。

〔産業上の利用分野〕

本発明は、相対キーを利用したカウント分類法によるソ
ート方式に関する。

最近、各種の分野において、計算機システムによるデー
タ処理が行われているが、該データが多量のレコードか
ら構成されている場合、該レコード中の特定の情報をキ
ーとしてソートすることが行われる。

この場合、できる限り、少ないノへ−ドウェア量（例え
ば、メモリ量）で、高速にソートできることが要求され
る。

〔従来の技術と発明が解決しようとする課題〕第２図は
従来のカウント分類法によるソート方式を説明する図で
あり、（ａ）はノー−ドウニア構成ノ例ヲ示し、（ｂｌ
）〜（ｂ４）は、カウント分類法によるソート方式を模
式的示している。

カウント分類法によって、複数個のレコードをソートす
る場合には、（ａ）図に示したように、入力用バッファ
１と、出力用バッファ２と、入力レコードの作業領域３
と、各レコードの順番を付けるカウンタ領域（以下、カ
ウンタということがある）４とを必要とする。

以下、カウント分類法によるソート方式の手順を（ｂｌ
）〜（ｂ４）によって説明する。

１）先ず、カウンタ４の値を°０゛にし、最初のレコー
ド（レコード１）のキ一部のキー値（８”）を作業領域
３に入力し、入力用バッファ　１をポイントするが、そ
れ以外は何も行わない。（（ｂｌ）図参照） ２）次のレコードのキー値を、該作業領域３に入力し、
既に、入力済みのレコードのキー値との検査を行う。該
検査は、以下の規則により行い、その結果に基づいて、
カウンタ４の値を調整する。

（イ）すでに入力済みのレコードのキー値が、最新のレ
コードのキー値より小さい（キー値として強い）時、最
新のレコードのカウンタ４にｌ゛を加える。

（ロ）すでに入力済みのレコードのキー値が、最新のレ
コードのキー値より大きい（キー値として弱い）時、入
力済みのレコードのカウンタ４に°１°を加える。

３）　上記２）の処理を、入力用バッファ１に入力され
ている全てのレコード（本例では、レコード１〜４）に
ついて繰り返す。

具体例で説明すると、レコード２のキー値（’３’）を
作業領域３に入力したとき、すでに、入力済みのレコー
ドｌのキー値（’８’）　　との間で上記の検査を行う
。

該入力済みのレコード１のキー値が、最新のレコード２
のキー値より弱い（具体的には、キー値が大きい）ので
、上記（ロ）の規則に従って、入力済みのレコードのカ
ウンタ４に°１”が加算される結果、該カウンタ４は（
ｂ２）図に示した通りとなる。

次に、最新のレコード３のキー値（°２”）が作業領域
３に入力された時点では、該レコード３のキー値と、入
力済みのレコード１．２の各キー値との間で上記の検査
が行われるが、上記（ロ）の規則に従う結果、各レコー
ド１，２．３のカウンタ４の値は、「２」　「１」　「
０」となる。

次に、最新のレコード４のキー値（’７’）が作業領域
３に入力され、該レコード３のキー値と、入力済みのレ
コード１，２の各キー値との間で上記の検査が行われる
場合、レコードｌとの間では、上記規則（ロ）に従い、
レコード２，３との間では、上記規則（イ）に従う結果
、レコード１のカウンタ３の値は“２°→“３′　とな
り、レコード２゜３のカウンタ３の値は、その優となり
、レコード４のカウンタ３には、ｒ＋１＋１・２」とな
って、結局、（ｂ３）図に示したようになる。

４）入力用バッファ１に入力されている全てのレコード
のキー値に対する上記検査が終了したら、各レコードの
カウンタの値より、例えば、“ｌ゛大きい位置の出力用
バッファ２に転送する。（（ｂ４）図参照） 上記の処理を、ソート対象の全てのレコードにツイテ、
例エバ、入力用バッファ　１のレコード数を単位にして
繰り返す。

上記、従来のカウンタ分類法でソートを行う場合、入力
用バッファ１を構成している個数と同じ数のカウンタ４
を必要とする問題と、該入力用バッファｌに入力されて
いる全てのレコードに対する検査が終了するまで、出力
用バッファ２にレコードを転送することができない問題
と、該ソートの手順には、レコード間のキー値を比較す
る命令を実行する必要があり、時間がかかる問題があっ
た。

本発明は上記従来の欠点に鑑み、相対キーを利用したカ
ウント分類法によってソートを行うのに、ハードウェア
量を少なくシ、且つ、高速に、多量のレコードを、キー
値の順にソートする方式を捉供することを目的とするも
のである。

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

上記の問題点は下記の如くに構成した相対キーを利用し
たカウント分類法によるソート方式によって解決される
。

複数個のレコードを格納する入力用バッファと出力用バ
ッファと、該複数個の入力レコードの作業領域と、各レ
コードの順番を付けるカウンタ領域と備えて、該入力用
バッファに格納されたレコードのキー値の順にソートし
て出力用バッファに格納する方式であって、 上記カウンタ領域を、唯１つ設けて、 上記入力用バッファに入力される複数個のレコードに対
しで、特定のレコードのキー値を基準値として設定し、
そのキー値を°０゛とし、その他のレコードのキー値に
対して、上記基準値のキーとの相対値である相対キーを
、相対キー＝（変換前のキー）−（基準値のキー）で算
出して、各レコードの相対キー値を上記作業領域に格納
し、 該格納した作業領域の相対キーが「負」であるならば、
上記カウンタ領域に°‘１’を加算し、該相対キーが「
正」、又は、「０」ならば、その侭にする処理を繰り返
し、上記入力用バッファの全レコードに対して終了した
とき、上記カウンタ領域（４ａ）に設定されている値だ
け「空き」の出力用バッファをスキップした場所に、上
記基準値として設定したレコードを転送することを繰り
返してソートするように構成する。

〔作用〕

即ち、本発明によれば、複数個のレコードを格納する入
力用バッファと出力用バッファと、該複数個の入力レコ
ードの作業用領域と、各レコードの順番を付けるカウン
タ領域と備えて、該入力用バッファに格納されたレコー
ドのキー値の順にソートして出力用バッファに格納する
のに、唯１つのカウンタを設けて、例えば、入力用バッ
ファの最初に入力されているレコードのキー値を基準値
として、該基準値のレコードのキー値と各レコードのキ
ー値との差を 相対キー＝（変換前のキー）＝（基準値のキー）として
計算し、その相対キーが、「負」であるならば、上記カ
ウンタに′１′を加算し、該相対キーが、「正」、又は
、「０」であるときは、該カウンタの値をその優とする
処理を、該入力用バッファに格納されている全てのレコ
ードに対して行う。

この処理により、基準キーより強いキー値（具体的には
、キー値が小さい）を持つレコードが存在すると、その
レコードの数が、カウンタでは計数されることになるの
で、該基準キーを有するレコードを、その数だけ弱い方
向にスキップして転送することを繰り返すことでソート
を行うことができる。

更に、このソート方式では、レコード間の演算は、従来
のカウント分類法の比較演算ではなく、単なる減算で済
むので、それだけ、高速にソートを行うことができる。

又、カウンタは、１組の入力用バッファに対して、唯１
個で済み、ハードウェア量を削減することができ、それ
だけ、多くのレコードを処理することができる。又、こ
のカウント分類法は、入力レコードを全て入力用バッフ
ァに読み込んでソートする内部ソート技法（即ち、入力
用バッファに入力レコードを全て読み込んでソートする
技法）であるが、前述のように、入力用バッファに入力
された最初の基準レコードに対して、他の全てのレコー
ドとの相対キーを求めた時点で、該基準となったレコー
ドを出力用バッファに転送でき、その空いた入力用バッ
ファに後続する新たなレコードを入力することができる
ので、レコードの移動とキー作成、即ち、入力用バッフ
ァへの新たなレコードの入力と、該レコードのキー値、
又は、相対キー値を作業領域に転送し、入力用バッファ
をポイントする処理が並行して行える。その結果、入力
レコードが、該入力用バッファより多くて、上記内部ソ
ート技法を利用できない場合に行う、所謂、外部ソート
技法において、該入力用バッファ分のソート結果である
ストリングを生成する時に、本発明のカウント分類法を
活用することができる効果が得られる。

〔実施例〕

以下本発明の実施例を図面によって詳述する。

第１図が本発明の一実施例を示した図であって、（ａ）
は構成例を示し、（ｂｌ）〜（ｂ６）は本発明のカウン
ト分類法によるソートの動作を模式的に示している。

本発明においては、複数個のレコードを格納する入力用
バッファ１と出力用バッファ２と、該複数個の入力レコ
ードの作業領域３と、各レコードの順番を付けるカウン
タ領域４ａとを備えて、該入力用バッファ１に格納され
たレコードのキー値の順にソートして出力用バッファ２
に格納するのに、上記カウンタ領域４ａを、唯１つ設け
て、上記入力用バッファ１に入力される複数個のレコー
ドに対して、特定のレコードのキー値を基準値として設
定し、そのキー値を°０゛とじ、その他のレコードのキ
ー値に対して、上記基準値のキーとの相対値である相対
キーを、 相対キー＝（変換前のキー）−（基準値のキー）で算出
して、各レコードを上記作業領域３に格納し、該格納し
た作業領域の相対キーが「負」であるならば、上記カウ
ンタ領域４に“１“を加算し、該相対キーが「正ｊ、又
は、「０」ならば、その儘にする処理を繰り返し、上記
入力用バッファｌの全レコードに対して終了したとき、
上記カウンタ領域４ａに設定されている値だけ「空き」
の出力用バッファ２をスキップした場所に、上記基準値
として設定したレコードを転送することを繰り返してソ
ートする手段が、本発明を実施するのに必要な手段であ
る。尚、全図を通して同じ符号は同じ対象物を示してい
る。

以下、第１図に従って、本発明による相対キーを利用し
たカウント分類法によるソート方式を説明する。

本発明においては、（ａ）図に示したように、入力用バ
ッファｌ、出力用バッファ２．入力レコードのキー値を
格納する作業領域３と、唯一つのカウンタ領域（カウン
タ）　４ａを設ける。

（１）先ず、カウンタ４ａの値を′Ｏ°にし、最初のレ
コードｌのキ一部のキー値を相対キーの基準値として、
作業領域３に該キー値を格納し、該最初のレコードの格
納されている入力用バッファ１をポイントする。　　（
（ｂｌ）図参照）（２）次のレコード２のキ一部と、上
記基準値となっているレコード１のキ一部を利用して、
相対キーを、 相対キー−（変換前のキー）−（基準値のキー）の算出
式で生成し、作業領域３に格納する。（（ｂ２）図参照
） （３）このとき、該作業領域３に格納した相対キーが「
負」ならば、カウンタ４ａを°＋１′シ、該相対キーが
「正」、又は、「０」ならば、該カウンタ４ａは、その
侭にしておく。

（４）上記（２）　、　（３）の処理を、入力用バッフ
ァ１に格納されている全てのレコード（本実施例では、
レコード１〜４）に対して行う。（（ｂ３）　、　（ｂ
４）図参照） （５）全てのレコードに対して、上記の処理が終了した
とき、カウンタ４ａの値だけ、空きの出力用バッファ２
をスキップして、その場所に、上記基準値として設定し
たレコード（レコード１）を転送する。

何故ならば、該カウンタ４ａの値は、上記基準値となっ
ているキー値を持つレコードより強いキー値（具体的に
は、キー値が小さい）を持つレコードの数を示している
からである。（（ｂ５）図参照）（６）最初のレコード
１の転送が終了したら、２番目に入力したレコード２を
次の基準値を持つレコードとして設定し、上記カウンタ
４ａの値を“０′にして、上記（２）〜（６）を繰り返
す。（（ｂ６）図参照） 最後のレコード（本実施例では、レコード４）を、その
時点で空いている場所に転送して、該入力用バッファ１
に格納されていたレコード１〜４に対するソート処理を
終了する。

若し、ソート対象のレコードの数が、上記入力用バッフ
ァ１の数より多いとき、上記（５）の転送処理後に空い
た入力用バッファ１に、次のブロックの最初のレコード
（本実施例では、レコード５〜）から入力して、最初の
レコードでは、そのキー値を、次のレコード以降では、
該ブロックの最初のレコードを基準値とした相対キーを
生成して、作業領域３に格納し、カウンタ４ａを上記の
ように調整することを繰り返し、該入力用バッファに一
杯になった時点で、上記基準値のレコードを出力用バッ
ファに転送することを繰り返してソートを行う。

この繰り返し処理で生成されるソート結果（これを、前
述のように、ストリングという）が全て集まった時点で
、各ストリングの先頭のレコードを生成順に取り出し、
並び変えて１本のストリングを生成することにより、該
入力用バッファ　ｌの数より多いレコードに対するソー
トを行うことができる。このソート技法を、前述のよう
に、外部ソート技法という。

本発明の相対キーを利用したカウント分類法によるソー
ト方式は、上記のように、外部ソート技法のストリング
生成にも活用することができるのである。

〔発明の効果〕

以上、詳細に説明したように、本発明の相対キーを利用
したカウント分類法によるソート方式は、従来のカウン
ト分類法が、入力用バッファに入力されているルコード
に対して１つのカウンタ領域（カウンタ）を必要とした
のに対して、相対キーを利用することにより、カウンタ
領域が１つで済むことになり、それだけ、多くのレコー
ドを処理することができる。又、該カウント分類法は内
部ソート技法であるが、相対キーを導入することにより
、残りの全レコードに対して、相対キーを作成した時点
で、基準値としたレコードを出力用バッファに移動する
ことができるため、該レコードの移動と、次のブロック
の最初のレコードを該入力用バッファに入力し、且つ、
作業領域に、該レコードのキー値の設定、相対キーの設
定といったキー作成を並行して行うことができる。従っ
て、前述のように、外部ソート技法のストリング生成に
、本発明の相対キーを利用したカウント分類法によるソ
ート技法を活用することができる効果がある。又、相対
キーの利用により、従来のカウント分類法で必要であっ
た比較命令を極力抑えることができ、ソート実行時間を
削減することができる。

【図面の簡単な説明】

第１図は本発明の一実施例を示した図。 第２図は従来のカウント分類法によるソーを説明する図
。 である。 ト方式 図面において、 １は入力用バッファ、　２は出力用バッファ。 ３は作業領域。 ４．４ａはカウンタ領域（カウンタ）。 をそれぞれ示す。 入力用バッファ 作業領域 カウンタ領域 出力用バッファ （ｂ３） 入力用バッファ 作業領域 カウンタ領域 出力用バンファ （ｂ４） 第 図 （その２） 入力用バッファ イ１ヨｉβ１１域 （ａ） 入力用バッファ 作業領域 （ｂｌ 入力用バッファ 作業領域 （ｂ２： カウンタ領域 出力用バッファ カウンタ領域 出力用バッファ カウンタ領域 出力用バッファ

Claims (1)

1. 【特許請求の範囲】 　複数個のレコードを格納する入力用バッファ（１）と
   出力用バッファ（２）と、該複数個の入力レコードの作
   業領域（３）と、各レコードの順番を付けるカウンタ領
   域（４ａ）と備えて、該入力用バッファ（１）に格納さ
   れたレコードのキー値の順にソートして出力用バッファ
   （２）に格納する方式であって、上記カウンタ領域（４
   ａ）を、唯１つ設けて、上記入力用バッファ（１）に入
   力される複数個のレコードに対して、特定のレコードの
   キー値を基準値として設定し、そのキー値を‘０’とし
   、その他のレコードのキー値に対して、上記基準値のキ
   ーとの相対値である相対キーを、 相対キー＝（変換前のキー）−（基準値のキー）で算出
   して、各レコードの相対キー値を上記作業領域（３）に
   格納し、 該格納した作業領域の相対キーが「負」であるならば、
   上記カウンタ領域（４）に‘１’を加算し、該相対キー
   が「正」、又は、「０」ならば、その儘にする処理を繰
   り返し、上記入力用バッファ（１）の全レコードに対し
   て終了したとき、上記カウンタ領域（４ａ）に設定され
   ている値だけ「空き」の出力用バッファ（２）をスキッ
   プした場所に、上記基準値として設定したレコードを転
   送することを繰り返してソートすることを特徴とする相
   対キーを利用したカウント分類法によるソート方式。