JPH0285921A - 併合処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、電子計算機によるデータの分類併合処理装置
に関する。本発明はデータの順序整理を行うために利用
する。例えば、日付順の編集、ページ順の編集に利用す
る。

〔概要〕

本発明は、データファイルの併合処理手段において、 データファイルのレコードを二分探索して勝者を選択出
力する過程を専用の手段で繰返し実行することにより、 頻繁に行われる分類併合処理を計算機から切離すことが
できるようにしたものである。

〔従来の技術〕

計算機によるデータの分類併合処理は頻繁に行われ、常
に高速処理が要求される。従来の分類併合処理はソフト
ウェアで実現されていた。

〔発明が解決しようとする問題点〕

しかし、このような従来の分類併合処理は頻繁に行われ
、計算機のＣＰＵに負荷がかかる欠点があった。

本発明は、このような欠点を除去するもので、併合を専
門に行わすてＣＰＵの負荷を分散するとともに高速な分
類併合処理が実現できる併合処理装置を提供することを
目的とする。

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

本発明は、併合すべき複数個のデータファイルの内容を
格納するデータスタック手段と、上記複数個のエントリ
を有し、上記データスタック手段上のデータファイルの
それぞれからこのデータファイルを構成するレコードの
ひとつに付されたキー値が与えられる制御テーブル手段
と、上記制御テーブル手段上のキー値を二分探索し、併
合時に先行するレコードのキー値の順序に再配列する二
分探索手段と、この二分探索手段により上記制御テーブ
ル上に再配列されたレコードのキー値のうち併合時の順
序がもっとも先行するレコードのキー値と新たに上記制
御テーブルに与えられるレコードのキー値とを比較し、
この比較結果に基づき併合時の順序が先行するレコード
がいずれのレコードであるか否かを判定し、併合時の順
序が先行するレコードを上記データスタック手段から抽
出する比較手段とを備えたことを特徴とする。

〔作用〕

人力されたレコードを格納し、比較すべきレコードを二
分探索で選択し、比較結果の勝者を保持する。次の比較
対象レコードのキー値と保持されたレコードのキー値の
比較を行う。すなわち、格納した入力レコードを二分探
索することにより勝者を選択出力し、出力したデータフ
ァイルの次レコードを人力する過程を繰り返すことによ
り併合処理を行う。

〔実施例〕

以下、本発明の一実施例について図面を参照して説明す
る。

第１図はこの実施例の構成を示すブロック構成図である
。この実施例は、第１図に示すように、入出力制御手段
１と、データレコードスタック手段２と、二分探索制御
手段３とを備え、ここで、二分探索制御手段３は、バウ
ンダＩＪ　（ｂｏｕｎｄａｒｙ）制御レジスタ３１と、
ウィナ（ｗｉｎｎｅｒ）レジスタ３２と、カレント（ｃ
ｕｒｒｅｎｔ）　　レジスタ３３と、キー比較手段３４
と、二分探索制御テーブル３５とを含む。すなわち、こ
の実施例は、併合すべき複数個のデータファイルの内容
を格納するデータスタック手及２と、上記複数個のエン
トリを有し、データスタック手段２上のデータファイル
のそれぞれからこのデータファイルを構成するレコード
のひとつのレコードに付されたキー値が与えられる制御
テーブル手段である二分探索制御テーブル３５と、上記
制御テーブル手段上のキー値を二分探索し、併合時に先
行するレコードのキー値の順序に再配列する二分探索手
段であるバウンダリ制御レジスタ３１と、この二分探索
手段により上記制御テーブル上に再配列されたレコード
のキー値のうち併合時の順序がもっとも先行するレコー
ドのキー値と新たに上記制御テーブルに与えられるレコ
ードのキー値とを比較し、この比較結果に基づき併合時
の順序が先行するレコードがいずれのレコードであるか
否かを判定し、併合時の順序が先行するレコードを上記
データスタック手段２から抽出する比較手段であるウィ
ナレジスタ３２、カレントレジスタ３３およびキー比較
手段３４とを備える。

次に、この実施例の動作を説明する。

併合すべきデータファイルは入出力制御手段ｌから人力
され、データレコードスタック手段２に格納される。こ
のときに併合すべきデータファイルａＳｂ１　、ｎはそ
れぞれのデータファイルに対応してデータレコードスタ
ック手段２のデータ格納域ＡＳＢ、　、Ｎに格納される
。二分探索制御手段３の二分探索制御テーブル３５のエ
ントリ数はデータファイルの個数ｎに対応してｎエント
リがとられる。バウンダリ制御レジスタ３工はＬＢとＲ
Ｂの２個が用意され、ＬＢは二分探索制御テーブル３５
による二分探索の過程の左端のエン）　ＩＪを保持し、
またＲＢは右端のエントリを保持する。

二分探索の開始状態ではＬＢはエントリ１を示し、ＲＢ
はエントリｎを示す。ウィナレジスタ３２は二分探索の
過程でのキー比較による勝者を保持する。

また、カレントレジスタ３３はウィナレジスタ３２の指
すレコードと比較すべき次のレコードのエントリを保持
する。二分探索制御テーブル３５は常に左から右にかけ
て分類キー類に保持され、二分探索による勝者は二分探
索制御テーブル３５のエンｌ’１０に格納される。

第２図は二分探索制御手段３の行う制御を示す流れ図で
ある。二分探索制御手役３での処理は、初期設定ステッ
プＳ１と、二分探索制御テーブル３５のエントリ０の次
レコードの人力ステップＳ２と、人力レコードの識別の
ウィナレジスタ３２への設定ステップＳ３と、二分探索
制御テーブル３５のエントリ１のカレントレジスタ３３
への設定ステップＳ４と、ウィナレジスタ３２七カレン
トレジスタ３３との指すレコードのキー比較ステップＳ
５と、キー比較の判定ステップＳ６と、ＬＢレジスタの
エントリ１への設定ステップＳ７と、ＬＢとＲＢの中間
エントリのカレントレジスタ３３への設定ステップＳ８
と、ウィナレジスタ３２とカレントレジスタ３３との指
すレコードのキー比較ステップＳ９と、その結果の判定
ステップ３１０と、結果がウィナレジスタ３２の指すレ
コードが勝者になった場合のＲＢの更新ステップ３１１
と、ウィナレジスタ３２の指すレコードが敗者となった
場合のＬＢの更新ステップ３１２と、二分探索の終了判
定ステップＳ１３と、二分探索制御テーブル３５のエン
トリのシフトステップＳ１４と、カレントレジスタ３３
の内容の二分探索制御テーブル３５への設定ステップＳ
１５と、二分探索制御テーブル３５のエンドＩＪ　Ｏの
内容のウィナレジスタ３２への設定ステップＳ１７と、
ウィナレジスタ３２の指すレコードの出力ステップ３１
７とからなる。

第３図は、この実施例で具体的なデータをもとにデータ
ファイルをキーの昇順に併合する例である。この説明で
は、データレコードと併合キー値とを一致させである。

■では、すべてのデータファイルの先頭レコードが人力
された時点での二分探索制御テーブル３５の内容であり
、キー比較によって二分探索制御テーブル３５のエン）
　ＩＪは左からキー類に並んでいる。この時点でのデー
タのキー比較による勝者としてファイルａのレコードＡ
ｌがステップ５１７により出力される。レコードＡ１の
出力された後に、■に示すように、ステップＳ２により
データレコードスタック手段２にファイルａの次レコー
ドＢ１が人力され、ステップＳ３、Ｓ４およびＳ５によ
り二分探索制御テーブルの２番目のエントリ１のレコー
ドＢ２と比較される。

その結果として、レコードＢ１が勝者としてステップＳ
６で判定され、ステップＳ１７に制御がわたって出力さ
れる。次に、■に示すように、再びステップＳ２でファ
イルａの次レコードＤＩが人力さる。レコードＤ１は前
記手順と同様に２番目のエントリ上のレコードＢ２と比
較されるが、今度はレコードＢ２の方が勝者となり、ス
テップＳ７からステップ３１２までの手順に従い二分探
索によりレコードＤ１の入るべきエントリが探索される
。

その結果として、ステップ３１４からステップＳ１６ま
での手順でレコードＤ１は二分探索制御テーブル３５の
該当エントリに格納される。また、ステップＳ１７によ
り二分探索制御テーブル３５のエン）　ＩＪＯにきたフ
ァイルｂのレコードＢ２が勝者と・して出力される。次
に■に示すように、ファイルｂの次レコードＣ２が人力
される。これらの処理手順を繰り返すことにより、出力
ファイルにデータの昇順に併合された結果が得られる。

〔発明の効果〕

本発明は、以上説明したように、電子計算機で行われて
いた分類併合処理を専門装置で行わせるので、高速な併
合処理が可能になり、また、ＣＰＵの負荷を軽減できる
効果がある。

【図面の簡単な説明】

第１図は本発明実施例の構成を示すブロック構成因。 第２図は二分探索制御手段の行う制御を示す図。 第３図は本発明実施例の動作と、人力および出力データ
の関連を示す動作説明図。 １・・・人出力制御手段、２・・・データレコードスタ
ック手段、３・・・二分探索制御手段、３１・・・バウ
ンダリ制御し゛ジスタ、３２・・・ウィナレジスタ、３
３・・・カレントレジスタ、３４・・・キー比較手段、
３５・・・二分探索制御テーブル。

Claims (1)

1. 【特許請求の範囲】 １、併合すべき複数個のデータファイルの内容を格納す
   るデータスタック手段と、 上記複数個のエントリを有し、上記データスタック手段
   上のデータファイルのそれぞれからこのデータファイル
   を構成するレコードのひとつに付されたキー値が与えら
   れる制御テーブル手段と、上記制御テーブル手段上のキ
   ー値を二分探索し、併合時に先行するレコードのキー値
   の順序に再配列する二分探索手段と、 この二分探索手段により上記制御テーブル上に再配列さ
   れたレコードのキー値のうち併合時の順序がもっとも先
   行するレコードのキー値と新たに上記制御テーブルに与
   えられるレコードのキー値とを比較し、この比較結果に
   基づき併合時の順序が先行するレコードがいずれのレコ
   ードであるか否かを判定し、併合時の順序が先行するレ
   コードを上記データスタック手段から抽出する比較手段
   と を備えたことを特徴とする併合処理装置。