(57)【要約】【課題】ソート（並び替え）手法・アルゴリズムを高速かつ安定的にする。【解決手段】処理効率の良いソートキーを新たに生成し、データに付加する。ハッシュテーブルを用意して、ソートキーを元にデータのグループ化を行う。グループが最適グループ数以下になるまで、ソートキーの分割を繰り返す。グループ内のデータ数が最適データ数よりも多くなる場合は、グループ内で再帰的にグループ化を行う。グループ内のデータは後方への追加、先頭データへのポインタが容易に得られる後方追加−循環型でリンクする。分割されたソートキーの上位桁の値でデータ全体をグループ化し、グループのソートを行い、ソートキーの下位桁の値でグループ内のデータのソートを行う。【選択図】図８
2006039894.tif 000002
【特許請求の範囲】
【請求項１】
ソートキーを２分割し、その上位桁の値でデータ全体をグループ化し、グループのソートを行い、ソートキーの下位桁の値でグループ内のデータをソートすることを特徴とするソート（並べ替え）手法・アルゴリズム。
【請求項２】
１グループ当たりのデータ数は１〜２００データが適しており、最適グループ数を格納できるハッシュテーブルを用意してソートキー全体でグループ化を始め、最適グループ数よりもグループ数が多くなる場合は、グループ化の作業を中断し、ソートキーにあらかじめ決められた係数を除してソートキーの長さを短くする操作を繰り返し、グループ内のデータ数が最適データ数よりも多くなる場合は、グループ内で請求項１の分割を再帰的に行うことを特徴とする請求項１記載のソート（並べ替え）手法・アルゴリズム。
【請求項３】
グループ内のデータは、最後尾のデータをポイントした循環型（最後尾のデータのポインタは最初のデータを指す）リンクで保持することを特徴とする請求項１記載のソート（並べ替え）手法・アルゴリズム。
【請求項４】
ソートキー項目は、項目の最大長で固定長とし、数値項目は右詰で一文字格納単位に２桁で格納し、サイン付きの場合は、一文字格納単位の前半に全てのビットを１にしたものを追加し、それが負数の場合は、その項目の全てのビットを反転させ、文字項目の場合は左詰で格納し、さらに項目の並び順が降順であれば、その項目の全てのビットを反転させることによって、ソートキー全体を文字列型単一項目であるかのような比較をすることが可能になる処理効率の良いソートキーを付加することを特徴とするソート（並べ替え）手法・アルゴリズム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート（並び替え）手法・アルゴリズムに関するものである。
【背景技術】
【０００２】
メモリの大容量化に伴い、数千万単位のデータを高速にソート（並び替え）処理することが要求されている。
【０００３】
データの並びがあらかじめ分かっていたり、既にデータが全て順番に並んでいるような特別な場合には、高速にソート（並び替え）処理する手法はあるが、データがランダムに並んでいるような場合は処理が遅くなる。ランダムに並んでいるようなデータに対して高速にソート処理する現在の最速ソート（並び替え）手法アルゴリズムであるクイックソートの平均計算量は
【数１】
2006039894.tif 000003
であるが、これが最小の平均計算量というわけではない。更にもっと少ない手法、考え方を提示することができる。また、クイックソートではレコード順の安定性にも問題がある。同じソートキーを持つレコードが２つ以上含まれる場合、最初の並びが保持されるアルゴリズムを安定であるという。一般に、遅いアルゴリズムは安定で、高速なアルゴリズムは安定でない。クイックソートでは先に投入されたレコードが先に順位付けられる保証がない。つまり安定でない。これを避けるために本来のソートキーにサブキーとしてレコード位置を付加し、安定にすることができるが、ソートキーのサイズが大きくなり、処理速度を損なうことになる。
【０００４】
以上に述べた通り、更に高速にソート（並べ替え）処理し、安定な手法が求められている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述したように、現在の最速ソート（並べ替え）手法・アルゴリズムであるクイックソートよりも、更に少ないソートキーの比較回数手法、考え方を提示することができる。また、クイックソートではレコード順の安定性にも問題がある。
【０００６】
本発明は上記事情を考慮してなされたものでその目的は、高速で安定的なソート（並び替え）手法・アルゴリズムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明のソート（並べ替え）手法・アルゴリズムは、ソートキーを２分割し、その上位桁の値でデータ全体をグループ化し、グループのソートを行い、ソートキーの下位桁の値でグループ内のデータをソートすることを特徴とする。ここで、ソートキーの上位桁の値でデータ全体をグループ化した後、ソートキーの下位桁の値でグループ内のデータをソートしてから、ソートキーの上位桁の値でグループのソートを行ってもよい。
【０００８】
ここで、グループ数は、多すぎても、少なすぎてもよくなく、最適値がある。これを最適グループ数とする。また、１グループ当たりのデータ数はソート対象データ数によって異なるが、１〜２００データが適しており、最適グループ数を格納できるハッシュテーブルを用意してソートキー全体でグループ化を始め、最適グループ数よりもグループ数が多くなる場合は、グループ化の作業を中断し、ソートキーにあらかじめ決められた係数を除してソートキーの長さを短くする操作を繰り返し、グループ内のデータ数が最適データ数よりも多くなる場合は、グループ内で再帰的に請求項１の分割を行う構成とするとよい。
【０００９】
また、グループ内のデータは、最後尾のデータをポイントした循環型（最後尾のデータのポインタは最初のデータを指す）リンクで保持する構成とするとよい。これにより、効率的にデータの順序を安定的に保持できる。
【００１０】
ソートキーは、何回か使われるので、処理効率の良い生成されたソートキーを、新たにデータに付加する。ソートキーの生成は次のように行う。ソートキー項目は、項目の最大長で固定長とし、数値項目は右詰で一文字格納単位に２桁で格納する。それがサイン付きの場合は、一文字格納単位の前半に全てのビットを１にしたものを追加し、それが負数の場合は、その項目の全てのビットを反転させる。文字項目の場合は左詰で格納する。その上で、項目の並び順が降順であれば、その項目の全てのビットを反転させることによって、ソートキー全体を文字列型単一項目であるかのような比較をすることが可能となる。
【発明の効果】
【００１１】
上記のように構成された本発明のソート（並び替え）手法・アルゴリズムによれば、グループ化後のグループのソートは、ソートキーが全て異なるので、安定でない高速ソートのクイックソートを用いても、安定なソートをすることができ、同じソートキーを持つレコードがある場合が多いグループ内のソートは、少数のデータでソートを行うので、高速ソートでなくても、安定な低速ソートでも処理速度に大きな差はない。そのため、総合的に安定的な高速なソートを行うことができる。  
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態について図面を参照して説明する。図１は本発明の一実施形態を示すソート（並べ替え）手法・アルゴリズムのシステム概要図である。
【００１３】
図１に示すシステム概要図は、命令ファイルコマンド部Ｓ１、入力ファイルＳ２、中間ファイルデータベース部Ｓ３、出力ファイルＳ４、本システムＳ５から構成される。図１のシステム概要図を図２のフローチャートを適宜参照して説明する。
【００１４】
本システムＳ５は、命令ファイルコマンド部Ｓ１からテキストファイルであるコマンドファイルを読み込む（Ｓ６）。次に、記載されたコマンドに従って入力ファイルＳ２を読み込む（Ｓ７）。次に、入力ファイルＳ２のデータを、コマンドに従ってソート（並び替え）する（Ｓ８）。入力ファイル２のデータがメモリに一度に格納できるサイズの場合、入力ファイル２のデータをメモリに読み込み、メモリの中でソート（並び替え）を行い、出力ファイルＳ４に書き出す（Ｓ９）。入力ファイルＳ２のデータがメモリに一度に格納できないサイズの場合、入力ファイルＳ２のデータをコマンドに指定された使用メモリサイズの上限まで読み、ソート（並び替え）を行い、中間ファイルデータベース部Ｓ３の中間ファイルに書き込む（Ｓ１０）。全てのデータの読み込みが完了するまで、この処理を繰り返し、完了した時点で、複数の中間ファイルを１レコードずつ読み込み、ソートキーの順番に出力ファイルＳ４に書き出す（Ｓ１１）。
【００１５】
次に図１の本システムＳ５について図３〜図８を適宜参照して説明する。まず初めに、新たにデータに付加する、処理効率の良いソートキーを生成する。ソートキーの生成は図３の手順で行う。
【００１６】
ソートキーの各項目のサイズは、項目毎に最大長を求め（Ｓ１２）、最大長で固定する（Ｓ１３）。ソートキー項目が数値の場合（Ｓ１４）は、右詰で一文字格納単位に２桁で格納する。さらに、サイン付の場合で正の数の場合（Ｓ１５）は、一文字格納単位の前半に全てのビットを１にしたものを追加する。負の数の場合（Ｓ１６）は、一文字格納単位の前半に全てのビットを１にしたものを追加し、さらに、その項目の全てのビットを反転させる。ソートキー項目が文字の場合（Ｓ１７）は、左詰（データに右詰で格納されている場合は右詰）で一文字格納単位に２桁で格納する。その上で、それぞれの項目の並び順が降順であれば、その項目の全てのビットを反転させる。
【００１７】
このように生成されたソートキーを新たに付加することによって、通常、必要となる処理、例えば、ソートキー項目が数値であるか、文字であるかのチェックやソートキー項目が昇順であるか、降順であるかのチェックやソートキーが複数あるかのチェックを省略でき、ソートキー全体を文字列型単一項目であるかのように比較することが可能となり、処理効率が良くなる。
【００１８】
図３のソートキー生成手順に基づいて作成されたソートキーを図４の様に新たにデータに付加し、グループ化を行う。グループ化は図５の手順で行う。
【００１９】
新たに付加したソートキーを元にデータのグループ化を行う。グループ数には最適値があり、１グループ当たりのデータ数は１〜２００データが適している。まず、最適グループ数を格納できるハッシュテーブルを用意して、ソートキー全体でグループ化を始める。この時点で最適なグループ数を得られた場合、グループ化を終了する。グループ数が最適グループ数よりも多くなる場合の手順を図６に示す。この場合、グループ化の作業を中断し、ソートキーにあらかじめ決められた係数を除してソートキーの長さを短くする（ソートキー分割）。この操作を最適なグループ数を得るまで繰り返す。グループ内のデータ数が最適データ数より多くなる場合は、グループ内で再帰的に請求項１の分割を行う。
【００２０】
このようにグループ化することによって、グループ化後のグループのソートはソートキーが全て異なり、安定かつ高速ソートが可能となる。また、グループ内では、１グループ当たりのデータ数が少ないため、比較回数が少なくなり、高速に処理することができる。
【００２１】
グループ内のデータは、元のデータ順を保持する必要がある為、図７の通り、後方追加型のリンクで保持する。先頭からも取り出す必要がある為、最後尾のデータをポイントした、循環型（最後尾のデータのポインタは最初のデータを指す）のリンクを用いる。このようなリンクでデータをリンクすることによって、データの後方への追加、先頭データへのポインタも容易に得ることができる。
【００２２】
このように後方追加-循環型のリンクを用いることにより、データ順を保持することとなり、安定なアルゴリズムとなる。
【００２３】
最終的に図８の様にデータ全体をソートキーの上位桁の値でグループ化し、グループのソートを行い、ソートキーの下位桁の値でグループ内のデータをソートする。ソートキーの上位桁の値でデータ全体をグループ化した後、ソートキーの下位桁の値でグループ内のデータをソートしてから、ソートキーの上位桁の値でグループのソートを行ってもよい。
【００２４】
このようにして、データの最後まで上記の処理が実行されると、図１の本システムの処理は終了となり、出力ファイルにソート（並び替え）されたデータが出力される。
【実施例】
【００２５】
説明を簡単にするため、データ数はｎ、データ上のソートキー数は１つ、全てのソートキーは異なるものとする。これは、ソートに関して大きく一般性を欠くものではない。
【００２６】
ソートキーを２分割し、その上位桁の値で、データ全体をｍ個のグループに分けた場合の平均計算量は、上位桁の処理と下位桁の処理の和となり、
【数２】
2006039894.tif 000004
となる。これは、
【数３】
2006039894.tif 000005
となり、平均計算量はｎ＝ｍか、または、ｍ＝１の場合以外はクイックソートより小さくなる。ただし、本発明でｎ＝ｍ、ｍ＝１となることはない。
【００２７】
ハッシング手法でグループ化する場合に、適当な大きさのハッシュテーブルを用意することにより、平均計算量は１．５×ｎ程度となる。したがって、これも加えれば、平均計算量は、
【数４】
2006039894.tif 000006
となる。データ数１００万、グループ数１０万とすると、
【数５】
2006039894.tif 000007
となる。クイックソートの場合は、
【数６】
2006039894.tif 000008
となり、本発明の平均計算量はクイックソートの平均計算量の１／３弱となった。
【００２８】
全てのソートキーが異なるものとして説明したが、一般的には同じソートキーを持つ場合も多い。この場合の問題点はレコード順の安定性ということである。クイックソートは安定でない。本発明の場合、グループ化によって、グループ毎のソートキーは全て異なることから、ソートキー上位桁の値の処理は、高速なクイックソートを使用することができる。グループ内の処理、つまりソートキー下位桁の値の処理は、一般的に同じソートキーを持つレコードがある場合が多いのでクイックソートを使用することはできないが、比較的少数のデータで行うので、高速なソートでなくても、低速で安定なソートを使用しても問題でない。
【図面の簡単な説明】
【００２９】
【図１】本発明の一実施形態を示すソート（並べ替え）手法・アルゴリズムのシステム概要図である。
【図２】同実施形態におけるソート（並べ替え）手法・アルゴリズムの処理全体の流れを示すフローチャートである。
【図３】新たにデータに付加するソートキーを生成する手順を説明するための図である。
【図４】データにソートキーを付加する手順を説明するための図である。
【図５】データのグループ化の手順を説明するための図である。
【図６】グループ数が最適グループ数よりも多くなる場合の手順を説明するための図である。
【図７】グループ内のデータをリンクさせる例を示す図である。
【図８】データ全体をグループ化する手順を説明するための図である。
【符号の説明】
【００３０】
Ｓ１    命令ファイルコマンド部
Ｓ２    入力ファイル
Ｓ３    中間ファイルデータベース部
Ｓ４    出力ファイル
Ｓ５    本システム
Ｓ６    コマンドファイル読み込み
Ｓ７    入力ファイル読み込み
Ｓ８    ソート（並び替え）
Ｓ９    出力ファイルに書き出し
Ｓ１０  中間ファイルに書き出し
Ｓ１１  中間ファイルを併合し出力ファイルに書き出し
Ｓ１２  各ソートキー項目サイズの最大長を求める
Ｓ１３  各ソートキー項目のサイズを最大長に固定する
Ｓ１４  ソートキー項目が数値項目  
Ｓ１５  ソートキー項目がサイン付き正の数値項目
Ｓ１６  ソートキー項目がサイン付き負の数値項目
Ｓ１７  ソートキー項目が文字項目
【図１】
2006039894.tif 000009
【図２】
2006039894.tif 000010
【図３】
2006039894.tif 000011
【図４】
2006039894.tif 000012
【図５】
2006039894.tif 000013
【図６】
2006039894.tif 000014
【図７】
2006039894.tif 000015
【図８】
2006039894.tif 000016