(57)【要約】【課題】  複数のデータよりなるデータ集合の中から、指定された順番の大きさのデータを選択するに際し、桁毎にソートする基数ソートの考え方に基づきその指定されたデータを選択することができ、特には、クイックソートの考え方に基づき選択するクイックセレクトと比較しより高速な選択が期待できる、基数ソートに基づく選択方法とその装置、及びそのプログラムを提供することを目的とする。【解決手段】  桁毎にソートする基数ソートの考え方に基づきデータを選択する方法であって、先ずそのデータ集合の全てのデータを桁ソートする対象データの集まりとして、先頭の桁から順に、桁ソートして分類した複数のグループの中から指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、その指定データを特定するまで桁毎のソート処理を繰り返す。【特許請求の範囲】
【請求項１】
複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択する方法であって、先ず該データ集合の全てのデータを桁ソートする対象データの集まりとして、先頭の桁から順に、桁ソートして分類した複数のグループの中から該指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、該指定データを特定するまで桁毎のソート処理を繰り返すことを特徴とする基数ソートに基づく選択方法。
【請求項２】
対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、該分類した複数のグループの中から該指定データを含むグループを特定する工程と、該特定したグループの全てのデータが該指定データであるかどうかを判定する工程と、該判定の結果、該指定データである場合に、該判定したグループの１つのデータを該指定データであるとして特定し、該指定された選択処理を終了する工程と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する工程に移行させる工程と、を有し、前記桁毎のソート処理を繰り返すことを特徴とする請求項１記載の基数ソートに基づく選択方法。
【請求項３】
前記ソートする桁は、二進数、十進数、十二進数、又は十六進数のいずれかであって、前記分類する工程で分類するグループ数は、それぞれ2、10、12、16であることを特徴とする請求項２記載の基数ソートに基づく選択方法。
【請求項４】
前記特定する工程は、前記ソートしたグループ毎のデータ数を、順次、積算して前記指定された順番と比較し、前記指定データを含むグループを特定する工程であって、自グループを含めた積算データ数が初めて該指定順番以上となるグループを、該指定データを含むグループとして特定する工程であることを特徴とする請求項２又は請求項３記載の基数ソートに基づく選択方法。
【請求項５】
前記指定された順番は、昇順又は降順の大きさの順番であって、前記順次する積算は、前記ソートしたグループ毎のデータ数を、それぞれ昇順、降順にする積算であることを特徴とする請求項４記載の基数ソートに基づく選択方法。
【請求項６】
前記判定する工程は、前記特定したグループのデータ数と、前記ソートの対象とした桁位置に基づき判定する工程であって、該データ数が1又は該対象桁がデータの最下位桁である場合、該特定したグループの全てのデータが該指定データであるとして判定する工程であることを特徴とする請求項２乃至請求項５記載の基数ソートに基づく選択方法。
【請求項７】
前記選択すべきデータの指定は、前記大きさの順番と共に、選択桁の下限を含めてする指定であって、前記判定する工程は、前記特定したグループのデータ数と、前記ソートの対象とした桁位置に基づき判定する工程であって、該データ数が1又は該対象桁が該指定された選択桁の下限である場合、該特定したグループの全てのデータが該指定データであるとして判定する工程であることを特徴とする請求項２乃至請求項５記載の基数ソートに基づく選択方法。
【請求項８】
前記終了する工程は、前記判定したグループの先頭のデータを前記指定データとして特定し、前記指定された選択処理を終了する工程であることを特徴とする請求項２乃至請求項７記載の基数ソートに基づく選択方法。
【請求項９】
前記データ集合のデータは、小数部と指数部からなる浮動小数点データであって、先ず、指数部を対象として、請求項１乃至請求項８記載の方法により、前記全てのデータが指定データであるとして判定されたグループを選択する第１の選択工程と、しかる後、該第１の選択工程で選択されたグループのデータの小数部を対象として、請求項１乃至請求項８記載の方法により、前記指定された順番の大きさのデータを特定する第２の選択工程と、を有することを特徴とする基数ソートに基づく選択方法。
【請求項１０】
請求項１乃至請求項９記載の方法を実施するための装置であって、入力装置と記憶装置と処理装置と出力装置とを含み、該処理装置は、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する手段と、該分類した複数のグループの中から該指定データを含むグループを特定する手段と、該特定したグループの全てのデータが該指定データであるかどうかを判定する手段と、該判定の結果、該指定データである場合に、該判定したグループの1つのデータを該指定データであるとして特定し、該指定された選択処理を終了する手段と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する手段が行う工程に移行させる手段と、を有することを特徴とする基数ソートに基づく選択装置。
【請求項１１】
請求項１乃至請求項９記載の方法を実行するコンピュータ読み取り可能なプログラムであって、少なくとも、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、該分類した複数のグループの中から該指定データを含むグループを特定する工程と、該特定したグループの全てのデータが該指定データであるかどうかを判定する工程と、該判定の結果、該指定データである場合に、該判定したグループの1つのデータを該指定データであるとして特定し、該指定された選択処理を終了する工程と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する工程に移行させる工程と、を実行させるプログラムであることを特徴とする基数ソートに基づく選択方法を実行するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択して通知する、基数ソートに基づく選択方法とその装置、及びそのプログラムに関する。
【背景技術】
【０００２】
本発明でいう「選択」とは、複数の数値データ（本発明では、単に「データ」と略称する）よりなるデータ集合の中から、指定された順番の大きさのデータを抽出・決定すること意味し、かかる選択アルゴリズムとしては、比較演算の回数を尺度とした計算量（以下、「計算量」とは、特に断らない限り、比較演算の回数を尺度とした計算量を意味する）が、データ数をnとして、最悪の場合でもオーダ記法による表記でO(n)に抑えられる、線形時間アルゴリズムが知られている（例えば、非特許文献１、非特許文献２）。然しながら、これらの線形時間アルゴリズムは、オーダ記法における比例定数は20程度であり、プログラム実装が複雑である点も相まって、実際に使用されることは少なく、理論的興味に止まっているのが現状である。
【０００３】
選択アルゴリズムとして、実際上、最も広く使われているのは、クイックソートの考え方に基づくクイックセレクトであり、そのクイックセレクトの計算量は、最悪の場合がO(n2)であり、平均の場合、計算量はO(n)、その比例定数の上限値は４程度であることが知られている（非特許文献２）。
【０００４】
クイックソートは、ソート（整列）対象データを、順次、基準値と比較したその大きさに基づき、細かなグループに分割していく方式であって、基準値として、例えば、ソート対象グループ内の最前列のデータを用い、そのソート対象グループ内のデータを、基準値未満のグループと基準値以上のグループと２つのグループに細分する如くして、順次、細かなグループに分割していく方式である。クイックソートでは、基準値としてソート対象グループ内の中央値を有するデータを用いた場合が最速となるため、中央値データの抽出を如何に効率よく行うかが問題であって、その中央値データの抽出法の改善に関し、例えば、特許文献１などに開示されている。
【０００５】
一方、クイックソートと共に広く使われているソート方式として、桁毎にソートする基数ソートがあり、基数ソートでは、２つのバッファを用いて、最下位の桁から順次、桁毎にソートを実行する。例えば、ソート対象データを26、95、13、31、57、18、21、5、90の9つのデータからなるデータ集合とした場合、先ず、1桁目の値に基づき例えば昇順にソートし、その結果として90、31、21、13、95、5、26、57、18のデータ集合をバッファAに格納し、次に、バッファAのデータ集合を対象として、2桁目の値に基づき昇順にソートし、その結果として5、13、18、21、26、31、57、90、95のデータ集合を、最終のソート結果としてバッファBに格納する。
【０００６】
かかるソート方式は、例えば、クイックソートは、一般的にソート速度が速いという利点を備えているが、上述のように、実際のソート速度は中央値データの抽出法に係るという問題の他、データの量が少ない場合は、基数ソートに比べて遅いという欠点があり、一方、基数ソートは、一般的にデータの量が少ない場合はソート速度が速いという利点を備えているが、２つのバッファを要するなど、それぞれ特徴があり、特許文献２には、ソート対象データの性質、量に対応させて、ソート方式を自動選択し、ソート速度を高速化する技術が開示されている。なお、特許文献２では、「基数ソート」を「ラディックソート」と表記している。
【０００７】
以上のようにソートに関しては、クイックソートや基数ソートを含め、種々のソート方式が開示され、且つ実用もされている。一方、複数のデータよりなるデータ集合の中から、指定された順番の大きさのデータを抽出・決定する選択に関しては、クイックソートの考え方に基づき選択するクイックセレクトは開示され、且つ実用もされているが、桁毎にソートする基数ソートの考え方に基づき選択する技術（以下、「基数セレクト」と称することがある）は未だ開示されていない。
【０００８】
例えば、特許文献３には、最大検索時間を基数検索法と同等以下にし、且つ、メモリの使用量を基数検索法より少なくすることを目的として、基数検索に用いられるツリー型の検索データ構造と、データを並置する並置テーブル構造とを混在させ、データが粗に分布している部分を並置テーブル構造とする技術が開示されているが、この従来技術は、ツリー型の検索データ構造を利用し、検索データの先頭の記号から順にツリーのノードを辿って探索範囲を狭めて検索を行う「基数検索」に係り、特にはその基数検索用データ構造を構築するための技術であって、本発明の意図する「選択」を行う技術ではない。なお、本発明で選択の対象とする、複数のデータよりなるデータ集合は、この文献でいうところの「並置テーブル構造」のデータ集合に属する。
【０００９】
又、特許文献４には、複数の宛先IPアドレスで構成されるルーチングテーブルの中から、所望の宛先IPアドレスを検索するために要する時間の短縮を図ると共に、可変長の検索キーとロンゲストマッチに対応した検索を実現することを目的として、構成を改善した検索木を用いて、基数検索する検索方式が開示されているが、この従来技術は、特許文献３と同様に、ツリー型の検索データ構造を利用し、検索データの先頭から順にツリーのノードを辿って探索範囲を狭めて検索を行う「基数検索」に係る技術であって、本発明の意図する「選択」を行う技術ではない。
【００１０】
即ち、良く知られている（例えば、非特許文献３）ように、固定小数点表示できるような通常の数値データの場合には、クイックソートよりも基数ソートの方が遥かに高速であり、同様なことが、クイックソートの考え方に基づき選択するクイックセレクトと、基数ソートの考え方に基づき選択する基数セレクトの間にも成り立つのではないかと予想されるにも係らず、桁毎にソートする基数ソートの考え方に基づき選択する技術は未だ開示されていない。
【非特許文献１】茨木俊秀：Cによるアルゴリズムとデータ構造，昭晃堂，1999
【非特許文献２】A.V. Aho, et al：The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974
【非特許文献３】クリフォード・シェーファー：Java(登録商標)によるデータ構造とアルゴリズム解析入門，ピアソンエデュケーション，2000
【特許文献１】特開平０５−３１３８５５号公報
【特許文献２】特開２００２−１１６９０７号公報
【特許文献３】特開２００１−２０９６５６号公報
【特許文献４】特開２０００−０８３０５６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、複数のデータよりなるデータ集合の中から、指定された順番の大きさのデータを選択する技術に係る前述の状況に鑑み、桁毎にソートする基数ソートの考え方に基づきその指定されたデータを選択することができ、特には、クイックソートの考え方に基づき選択するクイックセレクトと比較しより高速な選択が期待できる、基数ソートに基づく選択方法とその装置、及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の目的を達成するための手段として、次のような構成の基数ソートに基づく選択方法とその装置、及びそのプログラムを採用する。即ち、請求項１の発明は、複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択する方法であって、先ず該データ集合の全てのデータを桁ソートする対象データの集まりとして、先頭の桁から順に、桁ソートして分類した複数のグループの中から該指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、該指定データを特定するまで桁毎のソート処理を繰り返すことを特徴とする基数ソートに基づく選択方法である。
【００１３】
請求項２の発明は、請求項１の基数ソートに基づく選択方法において、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、該分類した複数のグループの中から該指定データを含むグループを特定する工程と、該特定したグループの全てのデータが該指定データであるかどうかを判定する工程と、該判定の結果、該指定データである場合に、該判定したグループの1つのデータを該指定データであるとして特定し、該指定された選択処理を終了する工程と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する工程に移行させる工程と、を有し、前記桁毎のソート処理を繰り返すことを特徴とする。
【００１４】
請求項３の発明は、請求項２の基数ソートに基づく選択方法において、前記ソートする桁は、二進数、十進数、十二進数、又は十六進数のいずれかであって、前記分類する工程で分類するグループ数は、それぞれ2、10、12、16であることを特徴とする。
【００１５】
請求項４の発明は、請求項２又は請求項３の基数ソートに基づく選択方法において、前記特定する工程は、前記ソートしたグループ毎のデータ数を、順次、積算して前記指定された順番と比較し、前記指定データを含むグループを特定する工程であって、自グループを含めた積算データ数が初めて該指定順番以上となるグループを、該指定データを含むグループとして特定する工程であることを特徴とする。
【００１６】
請求項５の発明は、請求項４の基数ソートに基づく選択方法において、前記指定された順番は、昇順又は降順の大きさの順番であって、前記順次する積算は、前記ソートしたグループ毎のデータ数を、それぞれ昇順、降順にする積算であることを特徴とする。
【００１７】
請求項６の発明は、請求項２乃至請求項５の基数ソートに基づく選択方法において、前記判定する工程は、前記特定したグループのデータ数と、前記ソートの対象とした桁位置に基づき判定する工程であって、該データ数が1又は該対象桁がデータの最下位桁である場合、該特定したグループの全てのデータが該指定データであるとして判定する工程であることを特徴とする。
【００１８】
請求項７の発明は、請求項２乃至請求項５の基数ソートに基づく選択方法において、前記選択すべきデータの指定は、前記大きさの順番と共に、選択桁の下限を含めてする指定であって、前記判定する工程は、前記特定したグループのデータ数と、前記ソートの対象とした桁位置に基づき判定する工程であって、該データ数が1又は該対象桁が該指定された選択桁の下限である場合、該特定したグループの全てのデータが該指定データであるとして判定する工程であることを特徴とする。
【００１９】
請求項８の発明は、請求項２乃至請求項７の基数ソートに基づく選択方法において、前記終了する工程は、前記判定したグループの先頭のデータを前記指定データとして特定し、前記指定された選択処理を終了する工程であることを特徴とする。
【００２０】
請求項９の発明は、前記データ集合のデータは、小数部と指数部からなる浮動小数点データであって、先ず、指数部を対象として、請求項１乃至請求項８の方法により、前記全てのデータが指定データであるとして判定されたグループを選択する第１の選択工程と、しかる後、該第１の選択工程で選択されたグループのデータの小数部を対象として、請求項１乃至請求項８の方法により、前記指定された順番の大きさのデータを特定する第２の選択工程と、を有することを特徴とする基数ソートに基づく選択方法である。
【００２１】
請求項１０の発明は、請求項１乃至請求項９記載の方法を実施するための装置であって、入力装置と記憶装置と処理装置と出力装置とを含み、該処理装置は、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する手段と、該分類した複数のグループの中から該指定データを含むグループを特定する手段と、該特定したグループの全てのデータが該指定データであるかどうかを判定する手段と、該判定の結果、該指定データである場合に、該判定したグループの1つのデータを該指定データであるとして特定し、該指定された選択処理を終了する手段と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する手段が行う工程に移行させる手段と、を有することを特徴とする基数ソートに基づく選択装置である。
【００２２】
請求項１１の発明は、請求項１乃至請求項９記載の方法を実行するコンピュータ読み取り可能なプログラムであって、少なくとも、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、該分類した複数のグループの中から該指定データを含むグループを特定する工程と、該特定したグループの全てのデータが該指定データであるかどうかを判定する工程と、該判定の結果、該指定データである場合に、該判定したグループの1つのデータを該指定データであるとして特定し、該指定された選択処理を終了する工程と、その他の場合に、該判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、該分類する工程に移行させる工程と、を実行させるプログラムであることを特徴とする。
【発明の効果】
【００２３】
本発明は、以下、詳細に説明するように、複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択することができ、特には、クイックソートの考え方に基づき選択するクイックセレクトと比較しより高速な選択が期待できる、基数ソートに基づく選択方法とその装置、及びそのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の好ましい実施の形態について説明する。先ず、本発明の基本的な考え方について説明する。即ち、本発明の方法は、複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択する方法であって、先ずそのデータ集合の全てのデータを桁ソートする対象データの集まりとして、先頭の桁から順に、桁ソートして分類した複数のグループの中から指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、その指定データを特定するまで桁毎のソート処理を繰り返すことを最大の特徴とする。
【００２５】
上述の如く、基数ソートでは、最下位の桁から順次、桁毎にソートを実行して、最上位の桁、即ち、先頭の桁まで桁ソートを行うことにより、全てのデータを効率よく整列させることができる。同様に、指定された順番の大きさのデータを選択するに際しても、先ず、基数ソートをして全てのデータを昇順又は降順に整列させ、しかる後に、指定された順番の大きさのデータを選択することもできるが、かかる方法によれば、高速に選択することはできない。
【００２６】
一方、本発明の方法においては、先頭の桁から順に、桁ソートし、且つそれぞれの桁ソート毎に、桁ソートして分類した複数のグループの中から指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、桁ソートする対象データの集まりを絞りながら、その指定データを特定するまで桁毎のソート処理を繰り返すため、高速に選択することができる。
【００２７】
かかる桁毎のソート処理の繰り返しは、好ましくは、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、その分類した複数のグループの中から指定データを含むグループを特定する工程と、その特定したグループの全てのデータが指定データであるかどうかを判定する工程と、その判定の結果、指定データである場合に、その判定したグループの1つのデータを指定データであるとして特定し、指定された選択処理を終了する工程と、その他の場合に、その判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、分類する工程に移行させる工程と、を有し、これらの工程を繰り返すことにより実施することができる。
【００２８】
ソートする桁は、通常、選択の対象とするデータの表記法による所謂「桁」に対応し、例えば、二進数、十進数、十二進数、或いは十六進数のデータの場合には、桁毎にソートし分類するグループ数、即ち基数は、それぞれ2、10、12、16として実施することができる。例えば、十進数表記で26のデータは、二進数、十進数、十二進数、十六進数では、それぞれ11010、26、22、1Aと表記され、それぞれ5桁、2桁、2桁、2桁のデータとなる。このデータは、計算機の中では、1桁を1ビットとする二進数で最少5ビットを要し、十進数、十二進数、及び十六進数の場合には、通常、1桁を4ビットで表して8ビットを要し、それぞれ00100110、00100010、00011010で表されている。
【００２９】
なお、如何なる表記法であっても、同じ表記法である限り、先頭から所定ビット数を比較した大きさの順番は変わることがない。従って、二進数のデータでも、上述の如く、1ビット毎に桁ソートし2分類する方法の他、例えば、2ビット毎に桁ソートし4分類するなどの形態として実施することもできる。同様に、十進数、十二進数、十六進数のデータで、上述の如く、4ビット毎に桁ソートしそれぞれ10分類、12分類、16分類する方法の他、例えば、2ビット毎に桁ソートし4分類するなどの形態として実施することもできる。
【００３０】
上述の桁毎に行う、分類した複数のグループの中から指定データを含むグループの特定は、ソートしたグループ毎のデータ数を、順次、積算して指定された順番と比較し、自グループを含めた積算データ数が初めてその指定順番以上となるグループを、指定データを含むグループとして特定することによって実施することができる。
【００３１】
例えば、セレクト対象データを十進数表記26、95、13、31、57、18、21、5、90の9つのデータからなるデータ集合（26、95、13、31、57、18、21、5、90）とし、その５番目に大きいデータを選択する場合、先ず、先頭の桁の値に基づき昇順にソートし、その結果として0〜9に対応し、それぞれ（05）、（13，18）、（26，21）、（31）、（  ）、（57）、（  ）、（  ）、（  ）、（95，90）の10グループに分類される。このグループ毎のデータ数を、順次、昇順に積算することにより、0〜9に対応し、それぞれ1、3、5、6、6、7、7、7、7、9が得られ、これを指定された順番と比較することにより、自グループを含めた積算データ数が初めて指定された順番である５以上となるグループを、指定データを含むグループとして、2に対応するグループ（26，21）を特定することができる。
【００３２】
なお、選択する大きさの順番の指定は、上述した昇順に限らず、降順の大きさの順番であってもよいが、この指定する順番の昇順、降順に対応し、桁毎にソートし分類する順番と、そのグループ毎のデータ数を順次する積算の順番は、特にはそれぞれ昇順、降順として実施するのが好ましい。
【００３３】
指定データを含むグループを特定した後、その特定したグループの全てのデータが指定データであるかどうかを判定する。この判定は、例えば、特定したグループのデータ数と、ソートの対象とした桁位置に基づき行うことができ、具体的には、そのデータ数が1又は対象桁がデータの最下位桁である場合、特定したグループの全てのデータが指定データであるとして判定する形態で実施することができる。
【００３４】
即ち、指定データを含むグループのデータ数が1の場合、当然ながら、それが指定された順番の大きさのデータであり、指定データを含むグループのデータ数が2以上でも、既に対象桁がデータの最下位桁になっている場合には、それ以上の分類は不可能であって、当該複数のデータを同じ大きさを有するデータ、即ち、グループの全てのデータが指定データであるとして処理せざるを得ない。
【００３５】
かかる判定を、例えば、上述した、9つのデータからなるデータ集合を対象とし、その5番目に大きいデータを選択する場合の、先頭の桁のソートをし、指定データを含むグループとして特定したグループ（26，21）に対し行うと、そのデータ数が1より多く、且つ、対象桁がデータの最下位桁でもないため、その判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、次の桁ソートによるデータの分類を行うことになる。
【００３６】
この次の桁、この場合、最下位桁を対象とした処理は、26、21の2つのデータからなるデータ集合を対象とし、このグループより小さいグループに分類されたデータ数3を指定順番5より差し引き、そのデータの中で2番目に大きいデータを選択することで行われる。
【００３７】
即ち、先ず、最下位桁の値に基づき昇順にソートし、その結果として0〜9に対応し、それぞれ（  ）、（21）、（  ）、（  ）、（  ）、（  ）、（26）、（  ）、（  ）、（  ）の10グループに分類される。次に、このグループ毎のデータ数を、順次、昇順に積算することにより、0〜9に対応し、それぞれ0、1、1、1、1、1、2、2、2、2が得られ、これを指定された順番と比較することにより、自グループを含めた積算データ数が初めて指定された順番である2以上となるグループを、指定データを含むグループとして、6に対応するグループ（26）を特定することができる。
【００３８】
次に、この特定したグループの判定を行い、この場合、そのグループのデータ数が1であり、又、対象桁がデータの最下位桁でもあり、特定したグループの全てのデータが指定データであるとして判定することができる。
【００３９】
なお、特定したグループの全てのデータが指定データであるかどうかの判定は又、上述の最下位桁かどうかの判定の他、ソートする桁数を限定する形態として実施することもできる。
【００４０】
即ち、例えば、選択すべきデータの指定は、大きさの順番と共に、選択桁の下限を含めてする指定とし、この判定は、特定したグループのデータ数と、ソートの対象とした桁位置に基づき行うことができ、具体的には、データ数が1又は対象桁が指定された選択桁の下限である場合、特定したグループの全てのデータが指定データであるとして判定する形態で実施することもできる。かかるソートする桁数を限定する形態は、例えば、測定データなど所定の有効精度を有するデータを対象とする際に、無駄な処理時間を排除することができ有効である。
【００４１】
以上のような処理により、最終的に、複数のデータからなるグループを、その全てのデータが指定データであるとして判定した場合、その中のいずれのデータを指定データとして特定してもよく、本発明を限定するものではないが、特にはその判定したグループの先頭のデータを指定データとして特定し、それを指定されたデータとして通知し、その選択処理を終了する形態として実施するのが好ましい。
【００４２】
本発明は、整数データ、固定小数点データ、浮動小数点データなどデータ形式を問わず選択の対象データとすることができるが、そのデータ形式により、適宜、具体的な処理の形態を変えられるようにして実施するのが好ましい。例えば、整数型データを対象とする場合には、上述した如く、その先頭の桁から始める１回の選択工程により、指定された順番の大きさのデータを選択することができる。
【００４３】
一方、例えば、小数部と指数部からなる浮動小数点型データの場合には、先ず、指数部を対象として、その先頭の桁から始める上述した処理により、全てのデータが指定データであるとして判定されたグループを選択する第１の選択工程と、しかる後、その第１の選択工程で選択されたグループのデータの小数部を対象として、その先頭の桁から始める上述した処理により、最終的に、指定された順番の大きさのデータを特定する第２の選択工程と、を有する形態として実施する必要があり、選択の対象とするデータ形式により、適宜、具体的な処理の形態を変えられるようにして実施するのが好ましい。
【００４４】
以上のような、本発明の基数ソートに基づく選択方法の計算量は、その具体的な説明は省略するが、理論的には、データ数をn、桁数をｋ、基数をMとして、最悪の場合がO(ｋ(n＋M))であり、平均の場合、計算量はO(n＋ｋM)、その比例定数の上限値は４程度である。ここで、M＝2とすれば、最悪計算量はO(ｋn)、平均計算量はO(n＋ｋ)となる。
【００４５】
即ち、本発明による計算量は、上述した、クイックソートの考え方に基づき選択するクイックセレクトと比較した場合、平均計算量は、比例定数も含めて、クイックセレクトと同程度であるが、最悪計算量は、クイックソートのO(n2)からO(ｋn)へ大幅に削減される。実際の計算速度は、単に比較演算回数で決まるものではなく、又、主に最悪計算量により決まるものでもないが、このことは、本発明によれば、クイックソートの考え方に基づき選択するクイックセレクトと比較しより高速な選択が期待できることを意味するものである。
【００４６】
この計算量に関する基数セレクトとクイックセレクトの関係は、概念的には以下の如く説明できる。即ち、基数セレクトでは、各要素における特定の桁の値を比較対象とし、各再帰ステップにおいて比較桁を１つずつ下位桁に移動するため、再帰の深さはデータの桁数kに一致し、結果的に最悪の場合でもO(ｋn)の計算量で抑えられる。これに対しクイックセレクトでは、上述のように、基準値データの抽出法に依存するが、例えば、各再帰ステップにおいて抽出された基準値データが常に最小値もしくは最大値に一致する最悪の場合、その計算量はO(n2)と大きく増大する。
【００４７】
一方、平均計算量は、各再帰ステップにおいて絞り込まれるデータ数が平均的に半分にまで減少するものと仮定した場合に相当し、トータルの比較回数は入力データの数に比例して、比例定数も含めて、基数セレクトとクイックセレクトは同程度の計算量になる。
【００４８】
次に、本発明の基数ソートに基づく選択装置の好ましい実施の形態について説明する。即ち、本発明の基数ソートに基づく選択装置は、上述した本発明の方法を実施するための装置であって、入力装置と記憶装置と処理装置と出力装置とを含み、その処理装置は、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する手段と、その分類した複数のグループの中から指定データを含むグループを特定する手段と、その特定したグループの全てのデータが指定データであるかどうかを判定する手段と、その判定の結果、指定データである場合に、その判定したグループの1つのデータを指定データであるとして特定し、指定された選択処理を終了する手段と、その他の場合に、判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、その分類する手段が行う工程に移行させる手段と、を有するのがその基本的な実施の形態である。
【００４９】
その入力装置は、例えば、キーボード、マウス、ペンタブレット、或いは、通信回線を介してデータを受信する受信装置などからなる装置とし、記憶装置は、選択の対象とするデータ集合とその関連情報や選択結果の情報などを格納・記憶すると共に、主記憶装置は、そのデータ集合から指定されたデータを選択するためのプログラムが記録されている装置であり、例えば、磁気ディスクやCD-ROM等のコンピュータ用記憶装置として、処理装置は、各種の演算処理を行う装置であり、例えば、ワークステーションやパーソナルコンピュータ等のコンピュータとし、出力装置は、選択結果などを表示及び／又は出力する装置であり、例えば、CRTディスプレイ、プリンタなどからなる装置として、本発明の基数ソートに基づく選択装置のハードを構成することができる。
【００５０】
このコンピュータは、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する桁ソート部と、その分類した複数のグループの中から指定データを含むグループを特定するグループ特定部と、その特定したグループの全てのデータが指定データであるかどうかを判定する判定部と、その判定の結果、指定データである場合に、その判定したグループの1つのデータを指定データであるとして特定し、指定された選択処理を終了するデータ特定部と、その他の場合に、判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、桁ソート部に移行させる桁更新部と、を有して構成することができる。
【００５１】
コンピュータは、主記憶装置に記録された上記のプログラムを読み込みその制御に従うことによって、コンピュータ上に、上記の桁ソート部、グループ特定部、判定部、データ特定部、桁更新部を実現し、記憶装置に記憶された選択の対象とするデータ集合とその関連情報に基づき、先ず入力されたデータ集合の全てのデータを桁ソートする対象データの集まりとして、先頭の桁から順に、桁ソートして分類した複数のグループの中から指定データを含むグループを特定しその特定したグループを次に桁ソートする対象データの集まりとする如くして、桁毎のソート処理を繰り返すことによって、指定された順番の大きさのデータを特定する。
【００５２】
即ち、本発明のプログラムは、上述した本発明の方法を実行するコンピュータ読み取り可能なプログラムであって、少なくとも、対象データの集まりを、対象とする桁の大きさに基づきソートして複数のグループに分類する工程と、その分類した複数のグループの中から指定データを含むグループを特定する工程と、その特定したグループの全てのデータが指定データであるかどうかを判定する工程と、その判定の結果、指定データである場合に、その判定したグループの1つのデータを指定データであるとして特定し、指定された選択処理を終了する工程と、その他の場合に、その判定したグループを次の桁でソートする対象データの集まりとし、対象桁を次の下位の桁に更新して、分類する工程に移行させる工程と、を実行させるプログラムとして実施できる。
【００５３】
なお、本発明の方法の選択アルゴリズムは、上述のように、桁毎の処理を繰り返す再帰が含まれるが、再帰呼び出しからの復帰後に行うべき作業としては、選択されたデータの受け渡し以外には存在しないため、実際のプログラム化に際しては、この繰り返し処理を、計算機の内部処理であるスタック操作等を要さないfor文、或いはwhile文など再帰なしの繰り返し文として実施することができる。
【００５４】
又、本発明の方法の選択アルゴリズムは、そのプログラム化に際し、特殊な数学関数等を必要とせず、又、膨大なメモリを必要とすることもなく、上述した線形時間アルゴリズムと比較しプログラムへの実装が容易であって、実際に広く使用されることが期待できる。
【００５５】
以上のような実施の形態により、本発明は、複数のデータよりなるデータ集合の中から、桁毎にソートする基数ソートの考え方に基づき、指定された順番の大きさのデータを選択することができ、特には、クイックソートの考え方に基づき選択するクイックセレクトと比較しより高速な選択が期待できる、基数ソートに基づく選択方法とその装置、及びそのプログラムを提供することができる。
【実施例】
【００５６】
以下、実施例により本発明を更に具体的に説明する。即ち、本発明の基数ソートに基づく選択方法と、クイックソートの考え方に基づく従来技術の選択方法とを比較し、実際の計算速度を実測した実施例について説明する。なお、使用したコンピュータは、Gateway社製のパーソナルコンピュータGateway2000 G6-333であり、使用したOSはMicrosoft社製のWindows(登録商標) NT4.0であり、使用したプログラム言語はSun Microsystems社製のJava(登録商標) 1.4である。
【００５７】
用いた、本発明の基数ソートに基づく選択方法を実行する基数セレクトのプログラムと、クイックソートの考え方に基づき選択するクイックセレクトのプログラムは、発明者が作成したものである。その基数セレクトのプログラムは、順番の指定と共に、選択桁の下限を含めてする指定も可能とし、基数Mも指定可能とした。なお、選択桁の下限を指定しない場合には、自動的に最下位桁を下限とした選択を行うように構成した。クイックセレクトのプログラムは、比較の基準値として先頭データを抽出するようにしたものである。
【００５８】
選択の対象とするデータは、整数型の二進32桁のデータであり、そのデータ集合は、その都度、指定されたデータ数n個分を乱数発生させるようにして構成した。なお、指定する選択の順番は、同様に、その都度、乱数発生させるようにして構成した。
【００５９】
次に、具体的な計算結果の一例を説明する。即ち、データ数nを1,000,000とし、基数Mを2として、10回の選択計算を実行させその計算時間を計測した結果、クイックセレクトでは、最短831ms、最長4757ms、平均2006msであったのに対し、基数セレクトでは、最短1211ms、最長1321ms、平均1255msであった。なお、基数セレクトに際し、選択桁の下限指定は行っていない。
【００６０】
もとより実際の計算速度は、具体的には、そのプログラムの組み方によって変わり、単純な比較はできないが、この結果は、本発明によれば、クイックセレクトと比較しより高速な選択が期待できることを実証するものである。
【００６１】
又、この計算結果は、クイックセレクトでは、実行する毎に計算時間が大きく異なり、特には最悪の計算時間が著しく大きくなっているのに対し、基数セレクトでは、最悪の計算時間が低く抑えられていることにより、比較的に安定した動作傾向を示しており、これは実用に際し、好ましい特性である。
【００６２】
以上、本発明の実施例を説明したが、特許請求の範囲で規定された本発明の精神と範囲から逸脱することなく、その形態や細部に種々の変更がなされても良いことは明らかである。