(57)【要約】【課題】データに偏りがある場合に、ソートを高速化すること。【解決手段】サンプリング部が、入力データからランダムにデータをサンプリングしてサンプリングデータとする。そして、ブロックソート部が、各サンプリングデータからブロック幅ｔの範囲をブロックとして、ブロックに含まれるブロックデータをバケツソート部を用いてバケツソートする。そして、入力データからブロックデータを除いた残データを残データソート部がマージソート部を用いてマージソートする。【選択図】図１３
2020123035.tif 000002
【特許請求の範囲】
【請求項１】
複数の整数データを含むデータ集合のソート方法であって、
前記データ集合からランダムに選択した要素それぞれについて、要素から所定の数値範囲の要素についてバケツソートを実行し、
バケツソートした要素以外の要素についてバケツソート以外のソートを実行する
処理をコンピュータが実行することを特徴とするソート方法。
【請求項２】
バケツソートした要素とバケツソート以外でソートした要素をバケツソート以外でソートする処理を前記コンピュータにさらに実行させることを特徴とする請求項１に記載のソート方法。
【請求項３】
ランダムに選択した要素の数は、前記データ集合に含まれる要素の数と比較して十分に小さく、ランダムに選択した要素の数と前記所定の数値範囲との積は前記データ集合に含まれる要素の値域範囲と比較して十分に小さいことを特徴とする請求項１又は２に記載のソート方法。
【請求項４】
前記バケツソートを実行する処理は、ランダムに選択した要素から該要素に所定の正数を加えた値までのブロック範囲に含まれる要素についてバケツソートを実行することを特徴とする請求項１、２又は３に記載のソート方法。
【請求項５】
前記バケツソートを実行する処理は、ランダムに選択した要素から該要素に所定の正数を加えた値までのブロック範囲に含まれる最も大きな要素である最大数から該最大数に前記正数を加えた値までの拡張範囲に要素が閾値個数以上ある場合には、前記ブロック範囲を前記拡張範囲まで拡張し、拡張したブロック範囲の拡張範囲の要素数が前記閾値個数未満になるまでブロック範囲を拡張することを特徴とする請求項４に記載のソート方法。
【請求項６】
前記バケツソート以外のソートはマージソートであることを特徴とする請求項１〜５のいずれか１つに記載のソート方法。
【請求項７】
複数の整数データを含むデータ集合をソートするソートプログラムであって、
前記データ集合からランダムに選択した要素それぞれについて、要素から所定の数値範囲の要素についてバケツソートを実行し、
バケツソートした要素以外の要素についてバケツソート以外のソートを実行する
処理をコンピュータに実行させることを特徴とするソートプログラム。
【請求項８】
複数の整数データを含むデータ集合をソートするソート装置であって、
前記データ集合からランダムに選択した要素それぞれについて、要素から所定の数値範囲の要素についてバケツソートを実行する第１ソート部と、
前記第１ソート部によりバケツソートされた要素以外の要素についてバケツソート以外のソートを実行する第２ソート部と
を有することを特徴とするソート装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート方法、ソートプログラム及びソート装置に関する。
【背景技術】
【０００２】
整数をソートする技術としてバケツソート、マージソート等がある。図１６は、ソートの例を示す図である。図１６では、ｎ＝８としてｎ個の整数ｘ１、ｘ２、．．．、ｘｎが昇順にソートされる。各整数の値は、１以上Ｎ以下である。ソート装置は、８個の整数９０、９３、８４、８７、８６、１、８、９２を入力し、昇順にソートして、１、８、８４、８６、８７、９０、９２、９３を出力する。
【０００３】
図１７は、バケツソートを説明するための図である。図１７に示すように、バケツソートでは、ソート装置は、長さＮの配列Ａを用意し、各配列要素Ａ［ｉ］（ｉ＝１〜Ｎ）を０で初期化する。そして、ソート装置は、入力の各ｘｉを読み、対応する配列要素でｘｉの数をカウントする。すなわち、ソート装置は、Ａ［ｘｉ］＋＝１（Ａ［ｘｉ］＝Ａ［ｘｉ］＋１）とする。そして、ソート装置は、配列Ａの先頭から順にＡ［ｉ］＞０となるｉをＡ［ｉ］回出力する。
【０００４】
図１７では、９０が読み込まれてＡ［９０］＝１となり、９３が読み込まれてＡ［９３］＝１となり、８４が読み込まれてＡ［８４］＝１となり、８７が読み込まれてＡ［８７］＝１となる。同様に、８６が読み込まれてＡ［８６］＝１となり、１が読み込まれてＡ［１］＝１となり、８が読み込まれてＡ［８］＝１となり、９２が読み込まれてＡ［９２］＝１となる。
【０００５】
そして、ソート装置は、１をＡ［１］＝１回出力し、８をＡ［８］＝１回出力し、８４をＡ［８４］＝１回出力し、８６をＡ［８６］＝１回出力する。さらに、ソート装置は、８７をＡ［８７］＝１回出力し、９０をＡ［９０］＝１回出力し、９２をＡ［９２］＝１回出力し、９３をＡ［９３］＝１回出力する。このように、ソート装置は、配列Ａの先頭から順にＡ［ｉ］＞０となるｉをＡ［ｉ］回出力することで、ソート結果として、１、８、８４、８６、８７、９０、９２、９３を出力する。
【０００６】
バケツソートの計算時間は、Ａ［１］〜Ａ［Ｎ］を読むため、Ｏ（Ｎ）である。ここで、「Ｏ」はオーダーを示す。値域Ｎが個数ｎに比べて大きくない場合、すなわち、データｘｉがＡに占める密度が大きい場合には、バケツソートは高速である。逆に、値域Ｎが個数ｎに比べて大きい場合、すなわち、データｘｉがＡに占める密度が小さい場合には、バケツソートは低速である。
【０００７】
図１８は、マージソートを説明するための図である。図１８に示すように、マージソートでは、ソート装置は、要素数ｉ個の隣接する２つのソート済み要素を結合して、要素数２ｉ個の新しいソート済み要素を作成する操作をｉ＝１からｌｏｇｎ回繰り返す。
【０００８】
図１８では、ソート装置は、ｉ＝１とし、（９０）と（９３）を結合して（９０，９３）を作成し、（８４）と（８７）を結合して（８４，８７）を作成し、（８６）と（１）を結合して（１，８６）を作成し、（８）と（９２）を結合して（８，９２）を作成する。そして、ソート装置は、ｉ＝２とし、（９０，９３）と（８４，８７）を結合して（８４，８７，９０，９３）を作成し、（１，８６）と（８，９２）を結合して（１，８，８６，９２）を作成する。そして、ソート装置は、ｉ＝４とし、（８４，８７，９０，９３）と（１，８，８６，９２）を結合して（１，８，８４，８６，８７，９０，９２，９３）を作成する。
【０００９】
マージソートの計算時間は、Ｏ（ｎ）かかるマージをＯ（ｌｏｇｎ）回繰り返すので、計算時間はＯ（ｎｌｏｇｎ）である。したがって、マージソートの計算時間はＮに依存しない。Ｎが小さい場合は、マージソートよりバケツソートの方が速い。
【００１０】
データｘｉがＡに占める密度が大きい場合には、バケツソートが高速であるため、入力の偏りがある範囲のみバケツソートを行い、他の範囲をマージソートすることで、ソートを高速化することができる。図１９は、バケツソートとマージソートを単純に組み合わせた単純組み合わせソートを説明するための図である。
【００１１】
単純組み合わせソートでは、ソート装置は、ブロック幅ｔと閾値を設定する。そして、ソート装置は、図１９に示すように、値域をＮ／ｔ個のブロックに分割し、各ブロックが含む入力値の頻度を計算して、頻度が閾値以上であればバケツソートを行い、頻度が閾値以上でなければマージソートを行う。
【００１２】
頻度大のブロック数をｍとすると、単純組み合わせソートの計算時間は、Ｏ（ｎ＋Ｎ／ｔ＋ｍｔ＋（ｎ−ｍ）ｌｏｇ（ｎ−ｍ））である。ここで、（ｎ＋Ｎ／ｔ）の部分は前処理としての頻度の計算に基づき、（ｍｔ）の部分はバケツソートに基づき、（（ｎ−ｍ）ｌｏｇ（ｎ−ｍ））の部分はマージソートに基づく。単純組み合わせソートでは、ブロック幅ｔがデータが密な分布幅より小さい場合には、前処理時間を含めてもソートは高速になる。一方、ブロック幅ｔがデータが密な分布幅より大きい場合には、前処理時間の分だけソートは低速になる。
【００１３】
なお、ソートに関する従来技術としては、ソート対象のデータ列を検索してソート処理不要な部分集合を抽出し、抽出した部分集合をソート済み並びとして併合する所定のマージ処理を行って、該データ列をソートすることで、ソートを高速化する技術がある。
【００１４】
また、共有メモリ上に、正の整数データが格納された第１の配列と該正の整数データの最大値と同一の数だけの要素を有する第２の配列とを備え、ベクトル演算プロセッサが第１及び第２の配列を用いて正の整数データのバケツソートを行う技術がある。この技術によれば、バケツソートを高速化することができる。
【００１５】
その他、映像や音楽等の各種データの内容に対応させて高精度な分類を行う従来技術がある。この従来技術では、データ分類装置は、入力データに関連する学習データを入力して復元抽出でランダムサンプルすることにより１又は複数のクラスに分類し、分類されたクラスに対して予め設定された数のデータ集合を生成する。そして、データ分類装置は、生成したデータ集合を決定木により学習し、学習結果を用いて、入力データの入力に対して、複数の異なる分類のうち何れか１つに分類分けする。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開平８−２２１２５４号公報
【特許文献２】特開平９−１９０３３６号公報
【特許文献３】特開２０１０−４４６７４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１７】
図１９に示した単純組み合わせソートは、頻度分布において頻度大の部分の分布幅がブロック幅に比較して小さいと、ブロック単位では頻度大でなくなり、バケツソートするブロックがなくなるので、全体をマージソートするのと同じになる。図２０は、頻度分布において頻度大の部分の分布幅がブロック幅に比較して小さい場合を示す図である。図２０に示すように、頻度分布において頻度大で分布が密である部分９の分布幅がブロック幅に比較して小さいと、ブロック全体では頻度小と判断される。
【００１８】
分布が密である部分９の分布幅がブロック幅に比較して小さくなるのを避けるためブロック幅を小さくすると、ブロック数（Ｎ／ｔ）が多くなり、高速化することができない。ブロック幅を小さくすると、全体をバケツソートすることと同じになる。
【００１９】
分布が密である部分を事前に特定することができれば、分布が密である部分だけバケツソートを行い、他の部分をマージソートすることで高速化することが可能だが、分布が密である部分を事前に特定することはできない。
【００２０】
このように、図１９に示した単純組み合わせソートには、データに偏りがあり、頻度が閾値以上のブロックが少なく、ｍが小さい場合には、計算時間≒Ｏ（ｎｌｏｇｎ）となり、マージソートとほぼ同じになるという問題がある。
【００２１】
本発明は、１つの側面では、偏りのあるデータを高速にソートすることを目的とする。
【課題を解決するための手段】
【００２２】
１つの態様では、ソート方法は、複数の整数データを含むデータ集合をソートする。前記ソート方法では、前記データ集合からランダムに選択した要素それぞれについて、要素から所定の数値範囲の要素についてバケツソートを実行する処理をコンピュータが実行する。そして、前記ソート方法では、バケツソートした要素以外の要素についてバケツソート以外のソートを実行する処理を前記コンピュータが実行する。
【発明の効果】
【００２３】
１つの側面では、本発明は、偏りのあるデータを高速にソートすることができる。
【図面の簡単な説明】
【００２４】
【図１】図１は、実施例に係るソート装置によるソート方法を説明するための図である。
【図２】図２は、実施例に係るソート装置の機能構成を示す図である。
【図３】図３は、ソート装置によるソート処理のフローを示すフローチャートである。
【図４】図４は、入力されるデータとソートに用いられる配列の初期状態を示す図である。
【図５】図５は、データを入力してデータ数をカウントする状態を示す図である。
【図６】図６は、データの入力が完了した状態を示す図である。
【図７】図７は、サンプリングデータのマージソートを示す図である。
【図８】図８は、ブロックデータのバケツソートを示す図である。
【図９】図９は、ｙ１＝８をＴから削除した状態を示す図である。
【図１０】図１０は、配列Ｙ２に含まれるデータをＴから削除した状態を示す図である。
【図１１】図１１は、Ｚの作成を示す図である。
【図１２】図１２は、ＹとＺのマージソートを示す図である。
【図１３】図１３は、ソート装置の効果を示す図である。
【図１４】図１４は、範囲の拡張を説明するための図である。
【図１５】図１５は、実施例に係るソートプログラムを実行するコンピュータのハードウェア構成を示す図である。
【図１６】図１６は、ソートの例を示す図である。
【図１７】図１７は、バケツソートを説明するための図である。
【図１８】図１８は、マージソートを説明するための図である。
【図１９】図１９は、バケツソートとマージソートを単純に組み合わせた単純組み合わせソートを説明するための図である。
【図２０】図２０は、頻度分布において頻度大の部分の分布幅がブロック幅に比較して小さい場合を示す図である。
【発明を実施するための形態】
【００２５】
以下に、本願の開示するソート方法、ソートプログラム及びソート装置の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例】
【００２６】
まず、実施例に係るソート装置によるソート方法について説明する。図１は、実施例に係るソート装置によるソート方法を説明するための図である。実施例に係るソート装置は、入力データからｓ個のデータをランダムサンプリングし、サンプリングしたデータｙｉ（ｉ＝１〜ｓ）から右側にｔの範囲のブロック［ｙｉ．．．ｙｉ＋ｔ］をバケツソートし、残りの範囲のデータをマージソートする。ここで、入力データ数をｎとすると、ｓ＜＜ｎであり、ｓｔ＜＜Ｎである。また、［ｙｉ．．．ｙｉ＋ｔ］は、ｙｉから（ｙｉ＋ｔ）までのブロックを表す。
【００２７】
図１では、３つのブロック［ｙ１．．．ｙ１＋ｔ］、［ｙ２．．．ｙ２＋ｔ］、［ｙ３．．．ｙ３＋ｔ］がバケツソートされ、残りの範囲のデータはマージソートされる。入力データからランダムにデータをサンプリングすると、サンプリングされたデータの近傍はデータの頻度が大である可能性が高い。例えば、ｙ１は頻度がピーク向かっている途中の値であり、［ｙ１．．．ｙ１＋ｔ］にピークがある。また、ｙ２は頻度がピークの値より少し小さい値であり、［ｙ２．．．ｙ２＋ｔ］にピークがある。一方、ｙ３の付近にはピークがないため、［ｙ３．．．ｙ３＋ｔ］にはピークは含まれないが、ランダムにサンプリングすると、ｙ３がサンプリングされる可能性は小さい。
【００２８】
このように、実施例に係るソート装置は、入力データからｓ個のデータをランダムサンプリングし、サンプリングしたデータｙｉから右側にｔの範囲のブロックをバケツソートの対象とすることで、頻度大である可能性が高いブロックをバケツソートする。したがって、実施例に係るソート装置は、頻度に偏りがあるデータを高速にソートすることができる。
【００２９】
なお、実施例に係るソート装置は、例えば、データベースシステムにおいて、データを検索する場合に用いられる。あるいは、実施例に係るソート装置は、売上の集計を行う売上集計装置やバッチ処理を行うバッチ処理装置の一部として用いられる。
【００３０】
次に、実施例に係るソート装置の機能構成について説明する。図２は、実施例に係るソート装置の機能構成を示す図である。図２に示すように、実施例に係るソート装置１０は、記憶部１１と、入力部１２と、マージソート部１３と、バケツソート部１４と、サンプリング部１５と、ブロックソート部１６と、残データソート部１７と、全体マージ部１８と、出力部１９とを有する。
【００３１】
記憶部１１は、ソート処理で用いられるデータを記憶する。記憶部１１は、入力データ記憶部２１と、サンプリング数記憶部２２と、サンプリングデータ記憶部２３と、ブロック幅記憶部２４と、ブロックデータ記憶部２５と、残データ記憶部２６と、ソート済データ記憶部２７とを有する。
【００３２】
入力データ記憶部２１は、ソートされるデータを入力データとして記憶する。サンプリング数記憶部２２は、入力データからサンプリングされるデータの数ｓを記憶する。サンプリングデータ記憶部２３は、入力データからサンプリングされたｓ個のサンプリングデータを記憶する。
【００３３】
ブロック幅記憶部２４は、バケツソートされるブロックの幅を記憶する。ブロックデータ記憶部２５は、バケツソートされるｓ個のブロックのデータをブロックデータとして記憶する。残データ記憶部２６は、バケツソートされないデータを残データとして記憶する。残データは、入力データからブロックデータを除いた残りのデータである。ソート済データ記憶部２７は、入力データがソート装置１０によりソートされたソート済データを記憶する。
【００３４】
ソート装置１０は、例えば、ユーザがキーボードを用いて入力したサンプリング数とブロック幅を受け付けてそれぞれサンプリング数記憶部２２とブロック幅記憶部２４に格納する。
【００３５】
入力部１２は、ソートされるデータを入力して入力データ記憶部２１に格納する。入力部１２は、例えば、ソートされるデータをファイルから読み込んで入力データ記憶部２１に格納する。入力部１２は、例えば、ユーザがキーボードから入力したファイル名を受け付けて、ソートされるデータをファイルから読み込む。
【００３６】
マージソート部１３は、マージソートを行う。バケツソート部１４は、バケツソートを行う。
【００３７】
サンプリング部１５は、入力データからランダムにサンプリング数のデータをサンプリングし、マージソート部１３を用いてソートし、サンプリングデータ記憶部２３にｙ１、ｙ２、．．．、ｙｓで表されるサンプリングデータとして格納する。
【００３８】
ブロックソート部１６は、ブロックデータを作成し、バケツソート部１４を用いてブロックデータをバケツソートする。すなわち、ブロックソート部１６は、サンプリングデータのそれぞれのデータｙｉについて、ブロック幅を用いて入力データからブロック［ｙｉ．．．ｙｉ＋ｔ］に含まれるデータを抽出し、バケツソートしてブロックデータ記憶部２５に格納する。
【００３９】
残データソート部１７は、入力データからブロックデータを除いて残データを作成し、マージソート部１３を用いて残データをマージソートして残データ記憶部２６に格納する。
【００４０】
全体マージ部１８は、バケツソートされたブロックデータとマージソートされた残データをマージソートしてソート済データを作成し、ソート済データ記憶部２７に格納する。
【００４１】
出力部１９は、ソート済データをソート済データ記憶部２７から読み出して出力する。出力部１９は、例えば、ソート済データをファイルに書き込む。
【００４２】
次に、ソート装置１０によるソート処理のフローについて説明する。図３は、ソート装置１０によるソート処理のフローを示すフローチャートである。図３に示すように、ソート装置１０は、ソートの対象となるデータを入力する（ステップＳ１）。ここでは、入力データをＸ＝ｘ１，．．．，ｘｎで表す。
【００４３】
そして、ソート装置１０は、入力データからランダムにデータをｓ個サンプリングし（ステップＳ２）、ｓ個のサンプリングデータをマージソートする（ステップＳ３）。ここでは、マージソートされたｓ個のサンプリングデータをｙ＝ｙ１，．．．，ｙｓで表す。
【００４４】
そして、ソート装置１０は、ブロック［ｙｉ．．．ｙｉ＋ｔ］をバケツソートする（ステップＳ４）処理をｉ＝１からｉ＝ｓまで繰り返す。そして、ソート装置１０は、その他のデータＺ＝Ｘ\Ｙをマージソートする（ステップＳ５）。ここで、「Ｘ\Ｙ」は、ＸからＹを取り除くことを表す。また、Ｙは、ブロックデータである。
【００４５】
そして、ソート装置１０は、ソート済みのＹとソート済みのＺをマージし、ソート済みのＸを作成する（ステップＳ６）。そして、ソート装置１０は、ソート済みのＸを出力する（ステップＳ７）。
【００４６】
このように、ソート装置１０は、入力データからｓ個のデータをランダムサンプリングし、サンプリングしたそれぞれのデータの値から右側にｔの範囲のｓ個のブロックをバケツソートの対象とするので、ソートを高速に行うことができる。
【００４７】
次に、ソート装置１０によるソート例を図４〜図１２を用いて説明する。図４は、入力されるデータとソートに用いられる配列の初期状態を示す図である。このソート例では、ｓ＝４、ｔ＝１０、ｎ＝８、Ｎ＝９３である。入力されるデータは、９０、９３、８４、８７、８６、１、８、９２である。
【００４８】
Ａ、Ｆ、Ｔ、Ｂ、Ｃは長さＮの配列である。Ａは、データの数を格納する。Ａの初期値は全て０である。ＦとＴは、バケツソートされるデータとマージソートされるデータを振り分けるために用いられる。ＦとＴの初期値は全て＃である。ここで、＃は、ｘｉ、ｉで使用されない記号であり、例えばＮ＋１である。ＢはバケツソートでソートしたデータＹを格納する。ＣはマージソートでソートしたデータＺを格納する。Ｂ及びＣもＦやＴと同様に初期値は全て＃である。
【００４９】
図５は、データを入力してデータ数をカウントする状態を示す図である。図５に示すように、ソート装置１０は、データｘｉをＡ［ｘｉ］＋＝１でカウントし、ｂ＋＝１、Ｆ［ｘｉ］＝ｂ、Ｔ［ｂ］＝ｘｉとする。ｂは、入力したデータの数を示す。ｘ１＝９０を入力した状態では、Ａ［９０］＝１、ｂ＝１、Ｆ［９０］＝１、Ｔ［１］＝９０となる。
【００５０】
そして、ソート装置１０は、９３、８４、．．．、９２を入力し、ｂ、Ｆ、Ｔを更新する。図６は、データの入力が完了した状態を示す図である。図６に示すように、入力したデータに対応するＡ［１］、Ａ［８］、Ａ［８４］、Ａ［８６］、Ａ［８７］、Ａ［９０］、Ａ［９２］、Ａ［９３］の値が１になる。また、Ｔ［１］〜Ｔ［８］に入力データが格納される。また、Ｔにおいてｘｉが格納された位置がＦ［ｘｉ］に格納される。すなわち、Ｆ［９０］＝１、Ｆ［９３］＝２、Ｆ［８４］＝３、Ｆ［８７］＝４、Ｆ［８６］＝５、Ｆ［１］＝６、Ｆ［８］＝７、Ｆ［９２］＝８である。
【００５１】
そして、ソート装置１０は、入力したデータから４個のデータをランダムにサンプリングし、Ｂの先頭に格納する。そして、ソート装置１０は、サンプリングデータをマージソートする。図７は、サンプリングデータのマージソートを示す図である。図７に示すように、サンプリングデータＢ［１］＝８７、Ｂ［２］＝８６、Ｂ［３］＝９２、Ｂ［４］＝８がマージソートされてＢ［１］＝８、Ｂ［２］＝８６、Ｂ［３］＝８７、Ｂ［４］＝９２となる。
【００５２】
そして、ソート装置１０は、ブロックデータを作成してバケツソートする。図８は、ブロックデータのバケツソートを示す図である。ソート装置１０は、ｙ１＝８を選び、ブロック［８．．．８＋１０］のデータのソート済み配列Ｙ１をＡを線形探索することで作成する。ブロック［８．．．８＋１０］には８しか含まれないので、８が探索され、Ｙ１［１］＝８となる。
【００５３】
そして、ソート装置１０は、８＋１０の次に大きなｙ２＝８６を選び、ブロック［８６．．．８６＋１０］のデータのソート済み配列Ｙ２をＡを線形探索することで作成する。ブロック［８６．．．８６＋１０］には、８６、８７、９０、９２、９３が含まれるので、Ｙ２［１］＝８６、Ｙ２［２］＝８７、Ｙ２［３］＝９０、Ｙ２［４］＝９２、Ｙ２［５］＝９３となる。そして、ソート装置１０は、Ｙ１とＹ２からＹを作成してＣに一時的に格納する。
【００５４】
そして、ソート装置１０は、ブロックデータ以外の残データを抽出するため、Ｔからブロックデータを削除する。すなわち、ソート装置１０は、Ｔ［Ｆ［ｙｉ］］＝＃とする。図９は、ｙ１＝８をＴから削除した状態を示す図である。ｙ１＝８のＴにおける位置はＦ［８］に格納されているので、Ｔ［Ｆ［８］］＝Ｔ［７］＝＃とする。なお、図８においてＣに一時的に格納されたブロックデータは、図９ではＢに移されている。
【００５５】
同様に、ソート装置１０は、配列Ｙ２に含まれるデータをＴから削除する。図１０は、配列Ｙ２に含まれるデータをＴから削除した状態を示す図である。図１０に示すように、ソート装置１０は、Ｔ［Ｆ［８６］］＝Ｔ［５］＝＃、Ｔ［Ｆ［８７］］＝Ｔ［４］＝＃、Ｔ［Ｆ［９０］］＝Ｔ［１］＝＃、Ｔ［Ｆ［９２］］＝Ｔ［８］＝＃、Ｔ［Ｆ［９３］］＝Ｔ［２］＝＃とする。
【００５６】
そして、ソート装置１０は、Ｔを線形探索して＃以外の数字を左詰めし、ＴをマージソートしてＺを作成してＣに格納する。図１１は、Ｚの作成を示す図である。図１１に示すように、Ｔ［３］＝８４とＴ［６］＝１が左詰めされ、ＴがマージソートされてＺが作成され、Ｃに保存される。
【００５７】
そして、ソート装置１０は、ＹとＺをマージソートしてソート済データを作成する。図１２は、ＹとＺのマージソートを示す図である。図１２に示すように、Ｃに格納されたＺとＢに格納されたＹがマージされてソート済データが作成され、Ｃに格納される。
【００５８】
次に、ソート装置１０の効果について説明する。ソート装置１０の計算時間は、Ｏ（ｎ＋ｓｔ＋（ｎ−ｋ）ｌｏｇ（ｎ−ｋ））である。ここで、ｋはバケツソートしたデータの数であり、ｎの部分は前処理としてのランダムサンプリングに基づき、ｓｔの部分はバケツソートに基づき、（ｎ−ｋ）ｌｏｇ（ｎ−ｋ）の部分はマージソートに基づく。
【００５９】
図１３は、ソート装置１０の効果を示す図である。図１３に示すように、ｓ，ｔが大である場合には、ブロック範囲が大きくなり、ｓ，ｔが小である場合には、ブロック範囲が小さくなる。また、データに偏りがある場合には、ブロック範囲にデータが沢山含まれ、ソート装置１０によるソートは高速化する傾向にある。一方、データに偏りがない場合には、ブロック範囲にデータが含まれにくく、ソート装置１０によるソートは低速化する傾向にある。
【００６０】
したがって、データに偏りがある場合には、ソート装置１０は、ブロック範囲大のとき、ソートを超高速化する傾向にあり、ブロック範囲小のとき、ソートを高速化する傾向にある。一方、データに偏りがない場合には、ソート装置１０は、ブロック範囲大のとき、ソートを超低速化する傾向にあり、ブロック範囲小のとき、ソートを低速化する傾向にある。
【００６１】
このように、ソート装置１０は、偏りがあるデータのソートを高速に行うことができる。なお、データに偏りがない場合、ランダムサンプリングに基づくバケツソートの無駄処理が発生するが、計算時間の上限はＯ（ｓｔ）であり、計算時間を見積もることは可能である。
【００６２】
上述してきたように、実施例では、サンプリング部１５が、入力データからランダムにデータをサンプリングしてマージソートする。そして、ブロックソート部１６が、マージソートされた各サンプリングデータから右にｔの範囲をブロックとして、ブロックに含まれるブロックデータをバケツソート部１４を用いてバケツソートする。そして、残データソート部１７がマージソート部１３を用いて残データをマージソートする。したがって、ソート装置１０は、データに偏りがある場合に、頻度分布において頻度が大きい範囲をバケツソートすることができ、ソートを高速化することができる。
【００６３】
また、実施例では、全体マージ部１８が、バケツソートされたブロックデータとマージソートされた残データをマージソートしてソート済データを作成する。したがって、ソート装置１０は、入力データをソートすることができる。
【００６４】
また、実施例では、ｓ＜＜ｎであり、ｓｔ＜＜Ｎである。したがって、ソート装置１０は、データに偏りがある場合に、頻度分布において頻度が大きい範囲を高い可能性で特定してバケツソートすることができる。
【００６５】
なお、実施例では、バケツソートとマージソートを用いる場合について説明したが、ソート装置１０は、マージソートの代わりに例えばクイックソート等他のソートアルゴリズムを用いてもよい。また、実施例では、サンプリングした値から右側にｔの範囲をバケツソートしたが、ソート装置１０は、サンプリングした値から左側にｔの範囲をバケツソートしてもよい。あるいは、ソート装置１０は、サンプリングした値から左右に（１／２）ｔの範囲をバケツソートしてもよい。
【００６６】
また、ソート装置１０は、サンプリングした値から右側にｔの範囲をデータが見つからなくなるまで拡張してもよい。図１４は、範囲の拡張を説明するための図である。図１４に示すように、ソート装置１０は、サンプリングしたデータｙｉから右側にｔの範囲を探索し、最後のデータの出現からさらにｔ以内にデータが見つかると、見つかったデータのうち最も大きなデータから右側にｔだけ探索範囲を拡張する。そして、ソート装置１０は、このような探索範囲の拡張を、拡張範囲にデータが見つからなくなるまで繰り返す。
【００６７】
このように、ソート装置１０は、データの分布幅がブロック幅ｔよりも大きい場合に、ブロック幅を自動で拡張することで、密な分布のより多くのデータをバケツソートし、ソートをより高速化することができる。あるいは、ソート装置１０は、拡張範囲に見つかるデータの数がユーザ設定の閾値を下回るまで探索範囲の拡張を繰り返してもよい。閾値を設定することで、ソート装置１０は、ｔ毎にデータが現れる場合等、広範囲で密でないデータをバケツソートすることを防ぎ、ソートを高速化できる。
【００６８】
なお、実施例では、ソート装置１０について説明したが、ソート装置１０が有する構成をソフトウェアによって実現することで、同様の機能を有するソートプログラムを得ることができる。そこで、ソートプログラムを実行するコンピュータについて説明する。
【００６９】
図１５は、実施例に係るソートプログラムを実行するコンピュータのハードウェア構成を示す図である。図１５に示すように、コンピュータ５０は、メインメモリ５１と、ＣＰＵ（Central  Processing  Unit）５２と、ＬＡＮ（Local  Area  Network）インタフェース５３と、ＨＤＤ（Hard  Disk  Drive）５４とを有する。また、コンピュータ５０は、スーパーＩＯ（Input  Output）５５と、ＤＶＩ（Digital  Visual  Interface）５６と、ＯＤＤ（Optical  Disk  Drive）５７とを有する。
【００７０】
メインメモリ５１は、プログラムやプログラムの実行途中結果等を記憶するメモリである。ＣＰＵ５２は、メインメモリ５１からプログラムを読み出して実行する中央処理装置である。ＣＰＵ５２は、メモリコントローラを有するチップセットを含む。
【００７１】
ＬＡＮインタフェース５３は、コンピュータ５０をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。ＨＤＤ５４は、プログラムやデータを格納するディスク装置であり、スーパーＩＯ５５は、マウスやキーボード等の入力装置を接続するためのインタフェースである。ＤＶＩ５６は、液晶表示装置を接続するインタフェースであり、ＯＤＤ５７は、ＤＶＤの読み書きを行う装置である。
【００７２】
ＬＡＮインタフェース５３は、ＰＣＩエクスプレス（ＰＣＩｅ）によりＣＰＵ５２に接続され、ＨＤＤ５４及びＯＤＤ５７は、ＳＡＴＡ（Serial  Advanced  Technology  Attachment）によりＣＰＵ５２に接続される。スーパーＩＯ５５は、ＬＰＣ（Low  Pin  Count）によりＣＰＵ５２に接続される。
【００７３】
そして、コンピュータ５０において実行されるソートプログラムは、コンピュータ５０により読み出し可能な記録媒体の一例であるＤＶＤに記憶され、ＯＤＤ５７によってＤＶＤから読み出されてコンピュータ５０にインストールされる。あるいは、ソートプログラムは、ＬＡＮインタフェース５３を介して接続された他のコンピュータシステムのデータベース等に記憶され、これらのデータベースから読み出されてコンピュータ５０にインストールされる。そして、インストールされたソートプログラムは、ＨＤＤ５４に記憶され、メインメモリ５１に読み出されてＣＰＵ５２によって実行される。
【符号の説明】
【００７４】
９    分布が密である部分
１０    ソート装置
１１    記憶部
１２    入力部
１３    マージソート部
１４    バケツソート部
１５    サンプリング部
１６    ブロックソート部
１７    残データソート部
１８    全体マージ部
１９    出力部
２１    入力データ記憶部
２２    サンプリング数記憶部
２３    サンプリングデータ記憶部
２４    ブロック幅記憶部
２５    ブロックデータ記憶部
２６    残データ記憶部
２７    ソート済データ記憶部
５０    コンピュータ
５１    メインメモリ
５２    ＣＰＵ
５３    ＬＡＮインタフェース
５４    ＨＤＤ
５５    スーパーＩＯ
５６    ＤＶＩ
５７    ＯＤＤ
【図１】
2020123035.tif 000003
【図２】
2020123035.tif 000004
【図３】
2020123035.tif 000005
【図４】
2020123035.tif 000006
【図５】
2020123035.tif 000007
【図６】
2020123035.tif 000008
【図７】
2020123035.tif 000009
【図８】
2020123035.tif 000010
【図９】
2020123035.tif 000011
【図１０】
2020123035.tif 000012
【図１１】
2020123035.tif 000013
【図１２】
2020123035.tif 000014
【図１３】
2020123035.tif 000015
【図１４】
2020123035.tif 000016
【図１５】
2020123035.tif 000017
【図１６】
2020123035.tif 000018
【図１７】
2020123035.tif 000019
【図１８】
2020123035.tif 000020
【図１９】
2020123035.tif 000021
【図２０】
2020123035.tif 000022