JPH02289005A - 計数情報の整列処理方式 - Google Patents
計数情報の整列処理方式Info
- Publication number
- JPH02289005A JPH02289005A JP1067011A JP6701189A JPH02289005A JP H02289005 A JPH02289005 A JP H02289005A JP 1067011 A JP1067011 A JP 1067011A JP 6701189 A JP6701189 A JP 6701189A JP H02289005 A JPH02289005 A JP H02289005A
- Authority
- JP
- Japan
- Prior art keywords
- information
- sorting
- sorted
- processing
- order
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Debugging And Monitoring (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
産業上の利用分野
本発明は、多数の計数情報の整列処理方式に関するもの
である。
である。
従来の技術
電子計算機上で取り扱う計数情報群が増大するにつれて
、計数情報を直接処理するのではなくて、分割処理や、
階層化処理と組み合わせることにより、取り扱う計数情
報を細分化して計算機コストを低減する方式がとられる
。このような計数情報の分割化や階層化による処理にお
いては、計数情報を予め昇順または、逆順等に並べ換え
る整列処理の技術が不可欠である。例えば、計算機幾何
学において、図形の重なりを調べる処理をおこなう場合
、対象とする幾何学計数情報の座標について予め整列処
理を行なうことにより検索効率が向上し、処理時間が短
縮できる。このように、処理効率を向上させるための整
列処理を含む処理ンステムについての計算機コストは、
計数情報の整列処理に要する計算機コストにより決定さ
れる。
、計数情報を直接処理するのではなくて、分割処理や、
階層化処理と組み合わせることにより、取り扱う計数情
報を細分化して計算機コストを低減する方式がとられる
。このような計数情報の分割化や階層化による処理にお
いては、計数情報を予め昇順または、逆順等に並べ換え
る整列処理の技術が不可欠である。例えば、計算機幾何
学において、図形の重なりを調べる処理をおこなう場合
、対象とする幾何学計数情報の座標について予め整列処
理を行なうことにより検索効率が向上し、処理時間が短
縮できる。このように、処理効率を向上させるための整
列処理を含む処理ンステムについての計算機コストは、
計数情報の整列処理に要する計算機コストにより決定さ
れる。
従来の電子計算機における計数情報の整列処理技術では
、例えば計数情報処理学会誌ＶＯＬ、２９Ｎ０．１１（
＋０５１−１０５７ページ！９８８年１１月）で解説さ
れているように、クイックソート方式が最も計算機コス
トが低いとされてきた。クイックソート方式は、与えら
れた計数情報を並べ換える基準となる項目（以下ソート
キーと呼ぶ）に対して、その項目の値が適当な判定値よ
りも大きいか小さいかを調べて二分割する処理を基本と
し、個々の基本情報単位に至るまでその処理を繰り返し
て整列化するものである。クイックソート方式を用いた
場合の計算機コストと、取り扱う基本情報単位の総数Ｎ
の関係は、 計算機コスト ｏｃＮｌｏｇ（Ｎ） ということがイ）かっている。
、例えば計数情報処理学会誌ＶＯＬ、２９Ｎ０．１１（
＋０５１−１０５７ページ！９８８年１１月）で解説さ
れているように、クイックソート方式が最も計算機コス
トが低いとされてきた。クイックソート方式は、与えら
れた計数情報を並べ換える基準となる項目（以下ソート
キーと呼ぶ）に対して、その項目の値が適当な判定値よ
りも大きいか小さいかを調べて二分割する処理を基本と
し、個々の基本情報単位に至るまでその処理を繰り返し
て整列化するものである。クイックソート方式を用いた
場合の計算機コストと、取り扱う基本情報単位の総数Ｎ
の関係は、 計算機コスト ｏｃＮｌｏｇ（Ｎ） ということがイ）かっている。
発明が解決しようとする課題
従来の電子計算機における計数情報の整列処理技術であ
るクイックソート方式では、計数情に！ｆｆ１Ｎが膨大
になるにつれて、電子計算機コストの増加がＮｌｏｇ（
Ｎ）に比例して増加するという問題があった。
るクイックソート方式では、計数情に！ｆｆ１Ｎが膨大
になるにつれて、電子計算機コストの増加がＮｌｏｇ（
Ｎ）に比例して増加するという問題があった。
本発明は、前記の従来の問題点を解決するもので、計数
情報ｆｆ１ＮのＲＱ加に対して計算機コストがＮに比例
する程度の増加で処理できる計数情報の整列処理方法を
提供することを目的とする。
情報ｆｆ１ＮのＲＱ加に対して計算機コストがＮに比例
する程度の増加で処理できる計数情報の整列処理方法を
提供することを目的とする。
課題を解決するための手段
本発明は」一連の課題を解決するため、計数情報の整列
処理に際し、整列処理対象となる計数情報の使用頻度を
求め、その頻度情報から積算情報を作成する手段と、前
記積算情報を用いて整列処理後の順序番号を作成する手
段と、前記順序番号から整列後の計数情報を作成する手
段を有するという構成を備えたものである。
処理に際し、整列処理対象となる計数情報の使用頻度を
求め、その頻度情報から積算情報を作成する手段と、前
記積算情報を用いて整列処理後の順序番号を作成する手
段と、前記順序番号から整列後の計数情報を作成する手
段を有するという構成を備えたものである。
作用
本発明は上述の構成によって、頻度情報が整列後の順番
情報の書き込み場所を指定することによって、処理の電
子計算機コストの目安である時間複雑度は、取り扱う単
位計数情報の総数をＮとして、時間複雑度 父 Ｎ である。従って、従来最も電子計算機コストの低い技術
であったクイックソー１・処理方式に比べて電子計算機
コストが遥に安価にできる。
情報の書き込み場所を指定することによって、処理の電
子計算機コストの目安である時間複雑度は、取り扱う単
位計数情報の総数をＮとして、時間複雑度 父 Ｎ である。従って、従来最も電子計算機コストの低い技術
であったクイックソー１・処理方式に比べて電子計算機
コストが遥に安価にできる。
実施例
第１図は、本発明の整列処理アルゴリズムを示す流れ図
である。整列処理アルゴリズムは、５ステツプから構成
されている。第１ステツプは、ソートキーの種類別頻度
情報格納用メモリアレイＳｂと、ソートキーの頻度積算
情報格納用メモリアレイＳ９および整列処理（以下ソー
ト処理と呼ぶ）後の順番格納用メモリアレイＳを計算機
上で確保する段階である。第２ステツプは、ソート処理
を行なう対象となる情報（以下被ソート情報と呼ぶ）を
読んでソートキーの種類別頻度情報をメモリアレイｓｈ
に作成する段階である。第３ステツプは、前記処理で生
成されたメモリアレイＳｈから、ソートキー頻度積算情
報をメモリアレイＳ、に作成する段階である。第４ステ
ツプは、被ソート情報とソートキー頻度積算情報から、
被ソート情報のソート後の順番情報をメモリアレイＳに
作成する段階である。第５ステツプは、ソート後の順番
情報を用いて、被ソート情報をソート済み情報に書き換
える段階である。
である。整列処理アルゴリズムは、５ステツプから構成
されている。第１ステツプは、ソートキーの種類別頻度
情報格納用メモリアレイＳｂと、ソートキーの頻度積算
情報格納用メモリアレイＳ９および整列処理（以下ソー
ト処理と呼ぶ）後の順番格納用メモリアレイＳを計算機
上で確保する段階である。第２ステツプは、ソート処理
を行なう対象となる情報（以下被ソート情報と呼ぶ）を
読んでソートキーの種類別頻度情報をメモリアレイｓｈ
に作成する段階である。第３ステツプは、前記処理で生
成されたメモリアレイＳｈから、ソートキー頻度積算情
報をメモリアレイＳ、に作成する段階である。第４ステ
ツプは、被ソート情報とソートキー頻度積算情報から、
被ソート情報のソート後の順番情報をメモリアレイＳに
作成する段階である。第５ステツプは、ソート後の順番
情報を用いて、被ソート情報をソート済み情報に書き換
える段階である。
以■本発明について第２図を用いて具体的に説明する。
第２図（ａ）〜（Ｃ）は、本発明の第１ステツプを説明
する図である。第２図（ａ）〜（Ｃ）はそれぞれソート
キーの種類別頻度情報１と、ソートキー１１１度積算情
報２およびソート後の順番３の内容を具体的に示す図で
ある。ここで、Ｍｋはソートキーの最大番号である。ま
た、Ｎは被ソート情報内の基本情報単位数である。第２
図（ｄ）は被ソート情報の一例を示し、被ソート情報４
は、ソートキー情報５と付随情報６から構成される基本
情報単位７の集合である。第２図（ｄ）中のｎは、被ソ
ート情報４の書き込み順番を示す。第２図（ｅ）は、本
発明における第２ステツプとなる、ソートキーの種類別
頻度情報１をメモリアレイｓｈに作成する段階である。
する図である。第２図（ａ）〜（Ｃ）はそれぞれソート
キーの種類別頻度情報１と、ソートキー１１１度積算情
報２およびソート後の順番３の内容を具体的に示す図で
ある。ここで、Ｍｋはソートキーの最大番号である。ま
た、Ｎは被ソート情報内の基本情報単位数である。第２
図（ｄ）は被ソート情報の一例を示し、被ソート情報４
は、ソートキー情報５と付随情報６から構成される基本
情報単位７の集合である。第２図（ｄ）中のｎは、被ソ
ート情報４の書き込み順番を示す。第２図（ｅ）は、本
発明における第２ステツプとなる、ソートキーの種類別
頻度情報１をメモリアレイｓｈに作成する段階である。
同処理は、ソートキーの種類をソートキー情報５から読
み取り、種類別関度情報１をメモリアレイｓｈに作成す
る。例えば、第２図（ｄ）においてソートキー情報５と
して「６」という数字は、３回出現する。従って、第２
図（ｅ）においてドロに相当する種類別頻度情報１は「
３」となる。第２図（ｆ）は、種類別頻度情！１７１か
ら、ソートキー頻度積算情報２をメモリアレイＳｔに作
成する第３ステツプの結果を示すものである。最初の順
番を「１」として、以下ドＩから１８まで、順次頻度を
加えていく。即ち、ドＩでは、５ｓ（１）：１．ｍ：２
では、ｍ＝１の頻度「２」を足してＳｓ （２）＝３と
なる。ｍ：３では、ｍ＝２の頻度「１」を足してＳｓ
（３）”４となる。ｍ＝４では、ド３の頻度「２」を足
して５ｓ（４）＝６となる。以下ド８まて繰り返すとソ
ートキー積算情報２は完成する。第２図（ｇ）〜（１）
は、ソート後の順番情Ｉ４７３をメモリアレイＳに作成
する第４ステツプを説明するものである。例えば、太線
で囲まれた被ソート情報４のｎ：１に書き込まれている
基本情報単位について、まずソートキー情報５は「８」
であるから、ソートキー積算情報２の５ｓ（８）に着目
する。５ｓ（８）の内容は「１１」である。そこで、ソ
ート後の順番情報５（１１）にソート前の被ソート情報
８４の順番「１」を書き込む。この時、ソートキー積算
情報２の５ｓ（８）に「１」を足して、「１２」に更新
する。以下同様に、被ソート情報４を調べていき、ソー
ト後の順番情報３を完成させる。第２図（ｊ）は、完成
したソート後の順番情報３を示す。第２図（ｋ）は、ソ
ート前と、ソート後の順番情報３から、被ソート情報４
を整列化し、ソート済み情報８を求める第５ステツプを
示す。
み取り、種類別関度情報１をメモリアレイｓｈに作成す
る。例えば、第２図（ｄ）においてソートキー情報５と
して「６」という数字は、３回出現する。従って、第２
図（ｅ）においてドロに相当する種類別頻度情報１は「
３」となる。第２図（ｆ）は、種類別頻度情！１７１か
ら、ソートキー頻度積算情報２をメモリアレイＳｔに作
成する第３ステツプの結果を示すものである。最初の順
番を「１」として、以下ドＩから１８まで、順次頻度を
加えていく。即ち、ドＩでは、５ｓ（１）：１．ｍ：２
では、ｍ＝１の頻度「２」を足してＳｓ （２）＝３と
なる。ｍ：３では、ｍ＝２の頻度「１」を足してＳｓ
（３）”４となる。ｍ＝４では、ド３の頻度「２」を足
して５ｓ（４）＝６となる。以下ド８まて繰り返すとソ
ートキー積算情報２は完成する。第２図（ｇ）〜（１）
は、ソート後の順番情Ｉ４７３をメモリアレイＳに作成
する第４ステツプを説明するものである。例えば、太線
で囲まれた被ソート情報４のｎ：１に書き込まれている
基本情報単位について、まずソートキー情報５は「８」
であるから、ソートキー積算情報２の５ｓ（８）に着目
する。５ｓ（８）の内容は「１１」である。そこで、ソ
ート後の順番情報５（１１）にソート前の被ソート情報
８４の順番「１」を書き込む。この時、ソートキー積算
情報２の５ｓ（８）に「１」を足して、「１２」に更新
する。以下同様に、被ソート情報４を調べていき、ソー
ト後の順番情報３を完成させる。第２図（ｊ）は、完成
したソート後の順番情報３を示す。第２図（ｋ）は、ソ
ート前と、ソート後の順番情報３から、被ソート情報４
を整列化し、ソート済み情報８を求める第５ステツプを
示す。
例えば、ソート後の順番情報３の５（１）は、 「５」
であるから、被ソート情報４の５番目の情報単位を１番
目に書き込む。次に、５（２）は、「ＩＯ」であるから
、被ソート情報４の１０番目の情報単位を２番目に書き
込む。以下同様に繰り返して、ソート済み情報８が得ら
れる。
であるから、被ソート情報４の５番目の情報単位を１番
目に書き込む。次に、５（２）は、「ＩＯ」であるから
、被ソート情報４の１０番目の情報単位を２番目に書き
込む。以下同様に繰り返して、ソート済み情報８が得ら
れる。
本処理の電子計算機コストである時間複雑度を調べると
、被整列処理計数情報の単位総数Ｎに関して固定回数の
処理のみ行なえばよい。従って、時間複雑度 父 Ｎ となる。
、被整列処理計数情報の単位総数Ｎに関して固定回数の
処理のみ行なえばよい。従って、時間複雑度 父 Ｎ となる。
なお整列処理において、必要とするメモリ名の変更や、
メモリアレイを瓜複利用によっても、本発明の本質的な
効果に変わりはない。なお本実施例では昇順の整列処理
を示したが、逆順の整列処理でも同様な効果ををする。
メモリアレイを瓜複利用によっても、本発明の本質的な
効果に変わりはない。なお本実施例では昇順の整列処理
を示したが、逆順の整列処理でも同様な効果ををする。
さらにソーｉ・キー情報は数字に限らず、文字列でも取
り扱えることは言うまでもない。
り扱えることは言うまでもない。
発明の効果
以上の説明から明らかなように本発明によれば、頻度情
報が整列後の順番情報の書き込み場所を指定し、計数情
報を昇順または逆順に整列処理をするので、処理の計算
機コストが、取り扱うｉｌｉ位計数情報の総数をＮとし
て、 時間複雑度 ＯＣＮ となる。これは、従来最も電子計算機コストが安価であ
ったクイックソート処理方式よりも安価であるため、非
常に有効である。
報が整列後の順番情報の書き込み場所を指定し、計数情
報を昇順または逆順に整列処理をするので、処理の計算
機コストが、取り扱うｉｌｉ位計数情報の総数をＮとし
て、 時間複雑度 ＯＣＮ となる。これは、従来最も電子計算機コストが安価であ
ったクイックソート処理方式よりも安価であるため、非
常に有効である。
第１図は本発明実施例における整列処理の流れを示す図
、第２図（ａ）〜（ｋ）は、本発明一実施例における整
列処理手順と生成される情報の内容を説明する図である
。 １・・・・ソートキー頻度情報、 ２・・・・ソートキ
ー積算情報、３・・・・ソート後の順番情報、４・・・
・被ソート情報、５・・・・ソートキー情報、６・・・
・付随情報、７・・・・基本情報単位、８・・・・ソー
ト済み情報。 代理人の氏名 弁理士 粟野重孝 はか１名−Ｉ 第 図 （勾 Ｃｅ）
、第２図（ａ）〜（ｋ）は、本発明一実施例における整
列処理手順と生成される情報の内容を説明する図である
。 １・・・・ソートキー頻度情報、 ２・・・・ソートキ
ー積算情報、３・・・・ソート後の順番情報、４・・・
・被ソート情報、５・・・・ソートキー情報、６・・・
・付随情報、７・・・・基本情報単位、８・・・・ソー
ト済み情報。 代理人の氏名 弁理士 粟野重孝 はか１名−Ｉ 第 図 （勾 Ｃｅ）
Claims (1)
- 電子計算機において、計数情報の整列処理に際し、整列
処理対象となる計数情報の使用頻度を求め、その頻度情
報から積算情報を作成する手段と、前記積算情報を用い
て整列処理後の整列順序番号を作成する手段と、前記整
列順序番号から整列計数情報を作成する手段を有するこ
とを特徴とする計数情報の整列処理方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1067011A JPH02289005A (ja) | 1989-03-17 | 1989-03-17 | 計数情報の整列処理方式 |
| US08/076,939 US5479657A (en) | 1989-03-17 | 1993-06-16 | System and method for sorting count information by summing frequencies of usage and using the sums to determine write addresses |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1067011A JPH02289005A (ja) | 1989-03-17 | 1989-03-17 | 計数情報の整列処理方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH02289005A true JPH02289005A (ja) | 1990-11-29 |
Family
ID=13332552
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1067011A Pending JPH02289005A (ja) | 1989-03-17 | 1989-03-17 | 計数情報の整列処理方式 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5479657A (ja) |
| JP (1) | JPH02289005A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03268133A (ja) * | 1990-03-19 | 1991-11-28 | Matsushita Electric Ind Co Ltd | 計数情報の整列処理方法 |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6493762B1 (en) * | 1995-05-08 | 2002-12-10 | International Business Machines Corporation | Index allocation for data broadcasting |
| US5806064A (en) * | 1995-11-21 | 1998-09-08 | Garza; Alberto Ortegon | Method for multi-field ordering of data base records with sequence variables |
| JP2002131395A (ja) * | 2000-10-18 | 2002-05-09 | Ando Electric Co Ltd | 半導体試験装置及びその制御方法 |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4031520A (en) * | 1975-12-22 | 1977-06-21 | The Singer Company | Multistage sorter having pushdown stacks with concurrent access to interstage buffer memories for arranging an input list into numerical order |
| US4295206A (en) * | 1979-06-06 | 1981-10-13 | Ncr Canada Ltd.-Ncr Canada Ltee | Document sorting method |
| NL8006163A (nl) * | 1980-11-12 | 1982-06-01 | Philips Nv | Inrichting voor het sorteren van datawoorden volgens de waarden van telkens daarbij behorende attribuutgetallen. |
| US4510567A (en) * | 1981-05-18 | 1985-04-09 | International Business Machines Corp. | Qualifying and sorting file record data |
| US4499555A (en) * | 1982-05-06 | 1985-02-12 | At&T Bell Laboratories | Sorting technique |
| US4611280A (en) * | 1984-03-12 | 1986-09-09 | At&T Bell Laboratories | Sorting method |
| US4809158A (en) * | 1985-10-23 | 1989-02-28 | Mccauley Peter B | Sorting method and apparatus |
| JP3070744B2 (ja) * | 1987-04-10 | 2000-07-31 | 株式会社日立製作所 | ベクトル処理装置 |
-
1989
- 1989-03-17 JP JP1067011A patent/JPH02289005A/ja active Pending
-
1993
- 1993-06-16 US US08/076,939 patent/US5479657A/en not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03268133A (ja) * | 1990-03-19 | 1991-11-28 | Matsushita Electric Ind Co Ltd | 計数情報の整列処理方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5479657A (en) | 1995-12-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4575798A (en) | External sorting using key value distribution and range formation | |
| CA2209549C (en) | Method and apparatus for loading data into a database in a multiprocessor environment | |
| US9658826B2 (en) | Sorting multiple records of data using ranges of key values | |
| US7451459B2 (en) | Systems, methods, and apparatus for indicating processor hierarchical topology | |
| JPH02178730A (ja) | 分割法を用いた内部ソート方式 | |
| US6424970B1 (en) | Sorting system and method executed by plural computers for sorting and distributing data to selected output nodes | |
| Lindstrom et al. | The design and analysis of bucketsort for bubble memory secondary storage | |
| US6269363B1 (en) | Method of accessing data using approximate data structures by relaxing the operations that define same | |
| JPH02289005A (ja) | 計数情報の整列処理方式 | |
| US6957216B2 (en) | Method and apparatus for finding nearest logical record in a hash table | |
| Lin | Sorting with associative secondary storage devices | |
| JP3198977B2 (ja) | 演算装置及び演算方法並びにそれを実行するプログラムを格納した記録媒体 | |
| Chang et al. | Parallel algorithms for wiring module pins to frame pads | |
| JP2989962B2 (ja) | ベクトル処理装置 | |
| JPS6266326A (ja) | 日本語デ−タ整列処理方式 | |
| JPS62226346A (ja) | フアイル管理方式 | |
| JPH0275018A (ja) | マージ処理方法 | |
| JPS62186328A (ja) | ソ−ト処理方式 | |
| JPH04264674A (ja) | ファイル検索方法及び装置 | |
| JPS63101976A (ja) | 縮小メモリアクセス装置 | |
| JPH02268368A (ja) | データ処理装置 | |
| JPS6339029A (ja) | デ−タベ−ス作成方法 | |
| JPH01204161A (ja) | 排他制御方式 | |
| JPH0474232A (ja) | タスク実行方法及びキャッシュ装置の割り当て方法 | |
| JPH04336324A (ja) | データ選択処理方法 |