(57)【要約】【課題】本発明は、分岐予測ミスの数を大幅に減少させることにより性能向上を図ることを目的とする。【解決手段】本発明は、ソート済みの第１及び第２の入力データ列夫々の先頭からサイズＢ１及びＢ２のデータ数からなる第１及び第２のブロックを取り出すこと、及び当該取り出された第１及び第２のブロック中の各値の組み合わせを比較して、一致する値を出力すること、当該第１及び第２のブロックの最後の各値のうち小さい値を有するブロックの次のブロックを又は上記最後の各値が同じ場合には上記第１及び第２のブロックそれぞれの次のブロックを取り出すこと、及び当該第１及び第２のブロック中の各値の組み合わせをさらに比較して、一致する値を出力すること、上記次のブロックの取り出し及び上記比較を繰り返して行い、上記第１及び第２の入力データ列の間で共通する値を出力データとして得ることを含む。【選択図】図２Ａ
2014102613.tif 000002
【特許請求の範囲】
【請求項１】
共通集合演算（Set Intersection）の処理方法であって、コンピュータが、
ソート済みの第１の入力データ列及び第２の入力データ列を受け取るステップと、
前記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び前記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出すステップであって、前記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、前記サイズＢ１は前記サイズＢ２と同じ又は異なるデータ数である、前記取り出すステップと、
前記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較するステップであって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較するステップと、
前記取り出された第１のブロック中の最後の値と前記取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から前記取り出されたブロックの次のブロックを又は前記最後の各値が同じ場合には前記第１の入力データ列及び前記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出すステップであって、前記小さい値を有するブロックの入力データ列が前記第１の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ１であり、前記小さい数を有するブロックの入力データ列が前記第２の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ２である、前記取り出すステップと、
前記比較するステップ及び前記次のブロックを取り出すステップを繰り返すステップと
を実行することを含む、前記方法。
【請求項２】
前記コンピュータが、前記第１のブロック及び前記第２のブロックを取り出すステップの前において、又は、前記繰り返すステップの途中において少なくとも１回、
前記第１の入力データ列及び前記第２の入力データ列それぞれの特性を求めるステップであって、前記サイズＢ１及び前記サイズＢ２それぞれが、前記求められた特性に関連付けられたデータ数である、前記求めるステップと
をさらに実行することを含む、請求項１に記載の方法。
【請求項３】
前記求めるステップが前記第１のブロック及び前記第２のブロックを取り出すステップの前において実行される場合に、
前記第１の入力データ列の先頭から取り出される前記第１のブロックの前記サイズＢ１が、前記第１の入力データ列から求められた特性に関連付けられたデータ数であり、
前記第２の入力データ列の先頭から取り出される前記第２のブロックの前記サイズＢ２が、前記第２の入力データ列から求められた特性に関連付けられたデータ数である、
請求項２に記載の方法。
【請求項４】
前記求めるステップが前記繰り返すステップの途中において少なくとも１回実行される場合に、
前記次のブロックの前記サイズＢ１が、前記第１の入力データ列から求められた特性に関連付けられたデータ数であり、
前記次のブロックの前記サイズＢ２が、前記第２の入力データ列から求められた特性に関連付けられたデータ数である、
請求項２に記載の方法。
【請求項５】
前記特性が、入力データ列のデータ数、入力データ列の値の分布の偏り、又は、入力データ列のデータ数と上記一致する値の出力データ数から求められる値である、請求項２に記載の方法。
【請求項６】
前記特性が入力データ列のデータ数であり、
前記第１の入力データ列のデータ数が所定数以上であり且つ前記第２の入力データ列のデータ数が当該所定数よりも小さい場合には、前記サイズＢ１は前記サイズＢ２よりも大きく、
前記第２の入力データ列のデータ数が所定数以上であり且つ前記第１の入力データ列のデータ数が当該所定数よりも小さい場合には、前記サイズＢ２は前記サイズＢ１よりも大きい、
請求項２に記載の方法。
【請求項７】
前記求めるステップが前記第１のブロック及び前記第２のブロックを取り出すステップの前において実行される場合に、前記特性が入力データ列中の最初の値から最後の値までの隣接する各値間の差の平均値であり、
前記第１の入力データ列の前記平均値と前記第２の入力データ列の前記平均値との比率が第１の閾値を超える場合において、
前記第１の入力データ列の前記平均値が前記第２の入力データ列の前記平均値よりも小さい場合には、前記サイズＢ１は前記サイズＢ２よりも大きく、
前記第２の入力データ列の前記平均値が前記第１の入力データ列の前記平均値よりも小さい場合には、前記サイズＢ２は前記サイズＢ１よりも大きい、
請求項２に記載の方法。
【請求項８】
前記求めるステップが前記繰り返すステップの途中において少なくとも１回実行される場合に、前記特性が入力データ列中の次に取り出されるブロックの最初の値から当該入力データ列の最後の値までの隣接する各値間の差の平均値であり、
前記第１の入力データ列の前記平均値と前記第２の入力データ列の前記平均値と比率が第２の閾値を超える場合において、
前記第１の入力データ列の前記平均値が前記第２の入力データ列の前記平均値よりも小さい場合には、前記サイズＢ１は前記サイズＢ２よりも大きく、
前記第２の入力データ列の前記平均値が前記第１の入力データ列の前記平均値よりも小さい場合には、前記サイズＢ２は前記サイズＢ１よりも大きい、
請求項２に記載の方法。
【請求項９】
前記求めるステップが前記繰り返すステップの途中において少なくとも１回実行される場合に、前記特性が入力データ列のデータ数に対する前記出力した値の個数の比率であり、
前記第１の入力データ列の前記比率が第３の閾値を超え且つ前記第２の入力データ列の前記比率が前記第３の閾値を超えない場合において、前記サイズＢ１は前記サイズＢ２よりも大きく、
前記第２の入力データ列の前記比率が第３の閾値を超え且つ前記第１の入力データ列の前記比率が前記第３の閾値を超えない場合において、前記サイズＢ２は前記サイズＢ１よりも大きい、
請求項２に記載の方法。
【請求項１０】
前記コンピュータが、
前記第１の入力データ列の先頭から取り出される第１のブロックの事前定義されたサイズＢ１及び前記第２の入力データ列の先頭から取り出される第２のブロックの事前定義されたサイズＢ２を読み出すステップ
を実行することをさらに含む、請求項１に記載の方法。
【請求項１１】
前記コンピュータが、
前記第１の入力データ列をその先頭からデータ数が前記事前定義されたサイズＢ１からなる第１のブロックに分割し、且つ、前記第２の入力データ列をその先頭からデータ数が前記事前定義されたサイズＢ２からなる第２のブロックに分割するステップ
を実行することをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記第１のブロック及び前記第２のブロックを取り出すステップが、
前記分割された第１のブロックのうちの最初の１つを読み出し、且つ、前記分割された第２のブロックのうちの最初の１つを読み出すステップ
を含む、請求項１１に記載の方法。
【請求項１３】
前記一致する値を出力するステップが、
一致する値を出力するステップと、
前記一致する値の出力後に行う比較によって一致する値がないことが予め判る場合には、前記比較を中止するステップと
を含む、請求項１に記載の方法。
【請求項１４】
前記繰り返すステップが、前記第１の入力データ列又は前記第２の入力データ列の全てを処理した場合に又は前記出力した値の個数が所定数になった場合に終了する、請求項１に記載の方法。
【請求項１５】
前記繰り返すステップが、前記次のブロックを取り出すステップを実行する際に、前記第１の入力データ列における未処理のデータ数が前記サイズＢ１よりも小さい場合に前記サイズＢ１を１に変更するステップ、又は、前記第２の入力データ列における未処理のデータ数が前記サイズＢ２よりも小さい場合に前記サイズＢ２を１に変更するステップをさらに含む、請求項１に記載の方法。
【請求項１６】
前記繰り返すステップが、前記次のブロックを取り出すステップを実行する際に、
前記取り出された第１のブロック中の最後の値よりも小さい隣接する値が、前記取り出された第２のブロックの最初の値よりも小さく、且つ、前記取り出された第１のブロック中の最後の値が前記取り出された第２のブロック中の最後の値よりも大きい場合には、前記比較を行わずに、前記取り出された第１のブロックの次のブロック中の各値と、前記取り出された第２のブロック中の各値とを比較するステップ、又は、
前記取り出された第２のブロック中の最後の値よりも小さい隣接する値が、前記取り出された第１のブロックの最初の値よりも小さく、且つ、前記取り出された第２のブロック中の最後の値が前記取り出された第１のブロック中の最後の値よりも大きい場合には、前記比較を行わずに、前記取り出された第２のブロックの次のブロック中の各値と、前記取り出された第１のブロック中の各値とを比較するステップ
をさらに含む、請求項１に記載の方法。
【請求項１７】
前記コンピュータが、
前記出力した値からなる第３の入力データ列及び第４の入力データ列を受け取るステップと、
前記第３の入力データ列の先頭からサイズＢ３のデータ数からなる第３のブロック及び前記第４の入力データ列の先頭からサイズＢ４のデータ数からなる第４のブロックを取り出すステップであって、前記Ｂ３及びＢ４はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、前記Ｂ３は前記Ｂ４と同じ又は異なるデータ数である、前記取り出すステップと、
前記取り出された第３のブロック中の各値及び第４のブロック中の各値の組み合わせを比較するステップであって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較するステップと、
前記取り出された第３のブロックの最後の値と前記取り出された第４のブロックの最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から前記取り出されたブロックの次のブロックを又は前記最後の各値が同じ場合には前記第１の入力データ列及び前記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出すステップであって、前記小さい値を有するブロックの入力データ列が前記第３の入力データ列の場合には前記次のブロックのサイズは前記Ｂ３であり、前記小さい数を有するブロックの入力データ列が前記第４の入力データ列の場合には前記次のブロックのサイズは前記Ｂ４である、前記取り出すステップと、
前記比較するステップ及び前記次のブロックを取り出すステップを繰り返すステップと
をさらに実行することを含む、請求項１に記載の方法。
【請求項１８】
共通集合演算（Set Intersection）を処理するためのコンピュータであって、
ソート済みの第１の入力データ列及び第２の入力データ列を受け取る入力データ受取部と、
前記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び前記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出す第１の取出部であって、前記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、前記サイズＢ１は前記サイズＢ２と同じ又は異なるデータ数である、前記第１の取出部と、
前記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較する比較部であって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較部と、
前記取り出された第１のブロック中の最後の値と前記取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から前記取り出されたブロックの次のブロックを又は前記最後の各値が同じ場合には前記第１の入力データ列及び前記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す第２の取出部であって、前記小さい値を有するブロックの入力データ列が前記第１の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ１であり、前記小さい数を有するブロックの入力データ列が前記第２の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ２である、前記第２の取出部と
を備えており、
前記比較部及び前記第２の取出部が、前記比較すること及び前記次のブロックを取り出すことを繰り返して行う、前記コンピュータ。
【請求項１９】
共通集合演算（Set Intersection）を処理するための演算処理装置であって、
ソート済みの第１の入力データ列及び第２の入力データ列を受け取る入力データ受取部と、
前記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び前記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出す第１の取出部であって、前記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、前記サイズＢ１は前記サイズＢ２と同じ又は異なるデータ数である、前記第１の取出部と、
前記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較する比較部であって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較部と、
前記取り出された第１のブロック中の最後の値と前記取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から前記取り出されたブロックの次のブロックを又は前記最後の各値が同じ場合には前記第１の入力データ列及び前記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す第２の取出部であって、前記小さい値を有するブロックの入力データ列が前記第１の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ１であり、前記小さい数を有するブロックの入力データ列が前記第２の入力データ列の場合には前記次のブロックのサイズは前記サイズＢ２である、前記第２の取出部と
を備えており、
前記比較部及び前記第２の取出部が、前記比較すること及び前記次のブロックを取り出すことを繰り返して行う、前記演算処理装置。
【請求項２０】
共通集合演算（Set Intersection）を処理するためのコンピュータ・プログラムであって、コンピュータに、請求項１〜１７のいずれか一項に記載の方法の各ステップを実行させるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通集合演算（Set Intersection）の処理技法に関する。より特には、本発明は、ソート済みの２つの入力データ列の共通集合演算の高速処理技法に関する。
【背景技術】
【０００２】
共通集合演算とは、２つのソート済み配列を入力として受け取り、当該２つのソート済み配列の両方に含まれている同じ値を結果として出力する処理である。当該共通集合演算は、多くのワークロードで使用されている基本的な処理である。当該共通集合演算は例えば、データ検索などの分野で複数のキーワードを同時に含むドキュメントを検索する処理（すなわち、ＡＮＤ検索）であり、当該処理のための計算時間の主要な部分を当該共通集合演算に基づく操作が占めている。従って、当該共通集合演算の高速化がプログラム全体の性能向上にとって重要である。
【０００３】
下記特許文献１はＳＩＭＤ（single instruction multiple data）命令を用いて２以上のデータアレイの高速共通集合演算を実行する方法（クレーム１）を記載し、また下記旨を記載する：
（カラム２第３９〜４６行目）共通集合演算の条件分岐は、ランダム入力データについておおよそ５０％の可能性で順不同に行われる。分岐予測ハードウェアにとって分岐を予測することは困難である。それ故に条件分岐命令の数を減少させる解決法が必要である；
（カラム５第２５〜３０行目）ＳＩＭＤ命令を用いる多くの比較事例において、対応する対はない。それ故に、ベクター比較においてＳＩＭＤ命令を用いる場合には、複数の要素が単一の比較で終了されることができ、それ故に任意の分岐条件の予測ミスを軽減する。
【０００４】
下記特許文献２は、複数のデータよりなるデータ列に含まれるデータの値を大小比較して昇順又は降順に並び替えるマージソート処理方法において、前記マージソート処理の対象となるデータ列に含まれるデータを、当該データ列の先頭から３ずつ取り出して部分的にマージソート処理を行う第１マージソート処理工程と、前記第１マージソート処理工程により前記部分的にマージソート処理されたデータを、更に前記データ列に含まれるデータ全体のマージソート処理を行う第２マージソート処理工程と、を備えることを記載する（請求項１）。また、特許文献２は、ソート対象の配列を３つずつ分割し、分割された３つの値をソートし、ソートは、一番目と二番目の値で大小を比較し、更に大きい値と三番目の値で比較し、三番目の値が大きい場合には、ソートを完了し、三番目の値が小さい場合には、更に一番目と二番目で比較して小さい値と比較して並び替え、得られた３つのソート済みの値で、マージソート処理と同様にデータの値をマージするので、最善の場合にはマージソート処理によりデータ同士の比較回数が少なくなることを記載する（段落００３８）。
【０００５】
下記特許文献３は、キャッシュメモリを用いて、ソート対象データのソートを行うソート処理方法であって、前記キャッシュメモリのキャッシュサイズに基づきブロックサイズを算定し、算定したブロックサイズに基づいてソート対象データを複数のブロックに分割するブロック分割ステップと、前記キャッシュメモリを用いて、前記ブロック分割ステップにより分割されたブロック毎にブロック内のソートを行うブロック内ソート処理ステップと、前記キャッシュメモリを用いて、前記ブロック内ソート処理ステップによるソート後の各ブロックをマージして、ソート対象データのソートを行うブロック間マージ処理ステップとを有することを記載する（請求項６）。また、特許文献３は、ブロック内ソートされたＮ個のブロックの最小値によるデータ列を生成すること、次に生成したデータ列をソートすること、ソートされたデータ列の最小値をソート結果データの最小値として主記憶上に出力すること、出力されたデータが属していたブロックに次の最小値のデータがあるか否かを判断し、次の最小値のデータがあれば、これを最小値のデータ列に挿入するとともに、最小値のデータ列をソートする処理から繰り返して実行することを記載する（段落００１７）。
【０００６】
下記非特許文献１は、スキップ・ポインタを使用する高速リスト集合演算を記載し、また下記旨を記載する：
（「What Are Skip pointers」の項）２つのポスティング・リストのサイズがｘ及びｙである場合に、集合演算はｘ＋ｙ操作を行う。スキップ・ポインタは我々がｘ＋ｙ操作よりも少ない集合演算を潜在的に完了することを可能にする。以下のようにする。索引付け時に、我々のポスティング・リストに沿う値を参照する「ショート・カット」ポインタをセットで文書識別子の上記リストを増強する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第７５３６５３２号明細書
【特許文献２】特開２００９−１９９４３９号公報
【特許文献３】特開２００６−１６３５６５号公報
【非特許文献】
【０００８】
【非特許文献１】Alan Skorkin，“Faster List Intersection Using skip pointers”， ［online］、２０１０年３月２１日、［平成２４年７月２４日検索］、インターネット〈URL：http://www.skorks.com/2010/03/faster-list-intersection-using-skip-pointers〉
【非特許文献２】Alistair Moffat et. al., “Self-Indexing Inverted Files for Fast Text Retrieval”, ACM Transactions on Information Systems, Vol. 14, No. 4, p.349 - 379, October, 1996
【発明の概要】
【発明が解決しようとする課題】
【０００９】
共通集合演算の手法の例として、２つのソート済みの入力データ列中の値をそれぞれ一つずつ取り出して当該取り出した値を比較するアルゴリズム（以下、「ナイーブ（naive）・アルゴリズム」という）がある。図１０Ａは、当該ナイーブ・アルゴリズムを図式化して示した例である。図１０Ａの例において、２つのソート済みの入力データ列を、それぞれデータ列１及びデータ列２とする。当該データ列１及びデータ列２は昇順にソート済みであり、当該データ列１及びデータ列２ともにデータ数（すなわち、データ列が有する値の数と同じである）がｎ（ｎは、整数である）であるとする。当該ナイーブ・アルゴリズムは、コンピュータ、特にはＣＰＵによって実行されうる。
【００１０】
ステップ１００１では、コンピュータは、データ列１の先頭の値一つと、データ列２の先頭の値一つとを取り出す。コンピュータは、データ列１から取り出した値（１）とデータ列２から取り出した値（２）とを比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータは、データ列１の値（１）及びデータ列２の値（２）のうち小さい値（１）を有するデータ列１のポインタを一つ進める。
【００１１】
ステップ１００２では、コンピュータは、データ列１の先頭から２つ目の値一つを取り出す。コンピュータは、データ列１から取り出した値（５）とデータ列２の値（２）とを比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータは、データ列１の値（５）及びデータ列２の値（２）のうち小さい値（２）を有するデータ列２のポインタを一つ進める。
【００１２】
ステップ１００３では、コンピュータは、データ列２の先頭から２つ目の値一つを取り出す。コンピュータは、データ列１の値（５）とデータ列２から取り出した値（３）とを比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータは、データ列１の値（５）及びデータ列２の値（３）のうち小さい値（３）を有するデータ列２のポインタを一つ進める。
【００１３】
ステップ１００４では、コンピュータは、データ列２の先頭から３つ目の値一つを取り出す。コンピュータは、データ列１の値（５）とデータ列２から取り出した値（５）とを比較し、値が一致するので、共通する値（５）を出力データとして出力する。次に、コンピュータは、共通する値（５）が出力されたので、データ列１及びデータ列２のいずれのポインタも一つ進める。
【００１４】
以下のステップ１００５〜１０１０においても、上記したステップ１００１〜１００４と同様にして、データ列１から取り出した値又はデータ列２から取り出した値のうちの小さい値を有するデータ列のポインタを一つ進めて、データ列１の値とデータ列２の値とを比較し、一致する値を出力データとして出力していく。
【００１５】
図１０Ｂは、図１０Ａに示すナイーブ・アルゴリズムを擬似プログラムにより示した例である。擬似プログラム（１０１１）中、左端の数字01〜12は行番号を示すために便宜的に付したものである。
【００１６】
擬似プログラム（１０１１）の行06は、分岐予測ミスが多発する条件分岐を示す。上記ナイーブ・アルゴリズムでは、各値同士の比較の処理ごとに上記条件分岐の処理が行われる。当該条件分岐は、多くの場合には両方の分岐の確率が同程度であり、順番もランダムであるためにハードウェアによる分岐予測がヒットしにくい。よって、行06に示す条件分岐は、多くの分岐予測が困難な条件分岐を含む処理になり、分岐予測ミスが多発する条件分岐である。従って、当該分岐予測ミスによるペナルティ乃至はオーバーヘッドが大きくなり、それ故に当該条件分岐は共通集合演算の性能を制限する主な要因となりうる。
【００１７】
そこで、値の比較回数を減らすことにより、すなわち値の比較のための命令数を減らすことにより、共通集合演算の性能向上を図ることが行われている。
【００１８】
例えば、２つのソート済みの入力データ列の長さが大きく違う場合には、図１０Ａに示すナイーブ・アルゴリズムで示したように入力データ列中の値をそれぞれ一つずつ取り出して比較する代わりに、入力データ列中のある程度離れた場所にある値に対して比較を行うことによって、値の比較回数を減らすことができる。
【００１９】
図１１は、上記した、入力データ列中のある程度離れた場所にある値に対して比較を行うアルゴリズム（以下、「スキップ・アルゴリズム」という）を擬似プログラムにより示した例である。擬似アルゴリズム（１１０１）中、左端の数字01〜18は行番号を示すために便宜的に付したものである。
擬似プログラム（１１０１）の行06〜行08及び行09〜行11はいずれも、分岐予測ミスが多発する条件分岐を示す。上記スキップ・アルゴリズムにおいても、スキップされる値を除いて値同士の比較の処理ごとに条件分岐が行われる。しかしながら、上記ナイーブ・アルゴリズムと同様に値同士の比較の処理ごとに上記条件分岐の処理が行われるために、ハードウェアによる分岐予測がヒットしにくいことに変わりはない。
【００２０】
また、従来技術として、事前に前処理を行い、追加のデータ構造を制作しておくことによって高速化を図ることが行われている（例えば、非特許文献２を参照）。
【００２１】
しかしながら、共通集合演算の処理において依然として分岐予測ミスによるオーバーヘッドが大きいために、更なる改良法が求められている。
【００２２】
従って、本発明は、分岐予測ミスの数を大幅に減少させることによって共通集合演算の性能を向上させることを目的とする。
【課題を解決するための手段】
【００２３】
本発明は、共通集合演算の処理技法を提供する。当該技法は、共通集合演算の処理方法、並びに、共通集合演算を処理するためのコンピュータ、コンピュータ・プログラム及びコンピュータ・プログラム製品を包含しうる。当該技法は、上記課題を解決するために、ソート済みの第１の入力データ列及び第２の入力データ列の各先頭からそれぞれサイズＢ１及びサイズＢ２のデータ数からなる第１のブロック及び第２のブロックを取り出すこと、及び当該取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較して、当該比較の結果、一致する値がある場合に当該一致する値を出力することを含む。そして、当該技法はさらに、当該取り出された第１のブロック中の最後の値と当該取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から上記取り出されたブロックの次のブロックを又は上記最後の各値が同じ場合には上記第１の入力データ列及び上記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出すこと、並びに、当該第１のブロック中の各値及び第２のブロック中の各値の組み合わせをさらに比較して、当該比較の結果、一致する値を出力すること、そして、上記次のブロックの取り出し及び上記比較を繰り返して行い、上記第１の入力データ列と上記第２の入力データ列との間で共通する値を出力データとして得ることを含む。
【００２４】
本発明の上記方法は、
ソート済みの第１の入力データ列及び第２の入力データ列を受け取るステップと、
上記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び上記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出すステップであって、上記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、上記サイズＢ１は上記サイズＢ２と同じ又は異なるデータ数である、上記取り出すステップと、
上記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較するステップであって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較するステップと、
上記取り出された第１のブロック中の最後の値と上記取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から上記取り出されたブロックの次のブロックを又は上記最後の各値が同じ場合には上記第１の入力データ列及び上記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出すステップであって、上記小さい値を有するブロックの入力データ列が上記第１の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ１であり、上記小さい数を有するブロックの入力データ列が上記第２の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ２である、上記取り出すステップと、
上記比較するステップ及び上記次のブロックを取り出すステップを繰り返すステップと
を含む。
【００２５】
また、本発明の上記コンピュータは、
ソート済みの第１の入力データ列及び第２の入力データ列を受け取る入力データ受取部と、
上記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び上記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出す第１の取出部であって、上記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、上記サイズＢ１は上記サイズＢ２と同じ又は異なるデータ数である、上記第１の取出部と、
上記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較する比較部であって、当該比較の結果、一致する値がある場合に当該一致する値を出力する、前記比較部と、
上記取り出された第１のブロック中の最後の値と上記取り出された第２のブロック中の最後の値とを比較して、前記最後の各値のうち小さい値を有するブロックの入力データ列から上記取り出されたブロックの次のブロックを又は上記最後の各値が同じ場合には上記第１の入力データ列及び上記第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す第２の取出部であって、上記小さい値を有するブロックの入力データ列が上記第１の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ１であり、上記小さい数を有するブロックの入力データ列が上記第２の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ２である、上記第２の取出部と
を備えており、上記比較部及び上記第２の取出部は、上記比較すること及び上記次のブロックを取り出すことを繰り返して行う。
【００２６】
本発明の一つの実施態様において、上記コンピュータは、
上記第１のブロック及び上記第２のブロックを取り出す前において、又は、上記繰り返す途中において少なくとも１回、上記第１の入力データ列及び上記第２の入力データ列それぞれの特性を求める特性判断部であって、上記サイズＢ１及び上記サイズＢ２それぞれが、上記求められた特性に関連付けられたデータ数である、上記特性判断部
をさらに備えていてもよい。
【００２７】
本発明の一つの実施態様において、上記コンピュータは、
上記特性判断部が上記第１のブロック及び上記第２のブロックを取り出す前に上記特性を求める場合に、上記第１の入力データ列の先頭から取り出される上記第１のブロックの上記サイズＢ１を上記第１の入力データ列から求められた特性に関連付けられたデータ数に変更し、又は、上記第２の入力データ列の先頭から取り出される上記第２のブロックの上記サイズＢ２を上記第２の入力データ列から求められた特性に関連付けられたデータ数に変更するブロック・サイズ変更部
をさらに備えていてもよい。
【００２８】
本発明の一つの実施態様において、上記ブロック・サイズ変更部は、
上記特性判断部が上記第１のブロック及び上記第２のブロックを取り出す前に上記特性を求める場合に、上記次のブロックの上記サイズＢ１を上記第１の入力データ列から求められた特性に関連付けられたデータ数に設定し、又は、上記次のブロックの上記サイズＢ２を上記第２の入力データ列から求められた特性に関連付けられたデータ数に設定しうる。
【００２９】
本発明の一つの実施態様において、上記ブロック・サイズ変更部は、
上記特性判断部が上記繰り返す途中において少なくとも１回上記特性を求める場合に、上記次のブロックの上記サイズＢ１を上記第１の入力データ列から求められた特性に関連付けられたデータ数に変更し、又は、上記次のブロックの上記サイズＢ２を上記第２の入力データ列から求められた特性に関連付けられたデータ数に変更しうる。
【００３０】
また、本発明の上記コンピュータ・プログラムは、コンピュータに上記に記載の方法の各ステップを実行させる。
【００３１】
本発明の機能を実行するためのコンピュータ・プログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ＢＤ、ハードディスク装置、ＵＳＢに接続可能なメモリ媒体、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な記録媒体に格納することができる。当該コンピュータ・プログラムは、記録媒体への格納のために、通信回線で接続する他のデータ処理システムからダウンロードしたり、又は他の記録媒体から複製したりすることができる。また、当該コンピュータ・プログラムは、圧縮し、又は複数に分割して、単一又は複数の記録媒体に格納することもできる。また、様々な形態で、本発明を実施するコンピュータ・プログラム製品を提供することも勿論可能であることにも留意されたい。コンピュータ・プログラム製品は、例えば、上記コンピュータ・プログラムを記録した記憶媒体、又は、上記コンピュータ・プログラムを伝送する伝送媒体を包含しうる。
【００３２】
本発明の上記概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの構成要素のコンビネーション又はサブコンビネーションもまた、本発明となりうることに留意すべきである。
【００３３】
本発明の実施態様において使用されるコンピュータの各ハードウェア構成要素を、複数のマシンと組み合わせ、それらに機能を配分し実施する等の種々の変更は当業者によって容易に想定され得ることは勿論である。それらの変更は、当然に本発明の思想に包含される概念である。ただし、これらの構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。
【００３４】
また、本発明は、ハードウェア、ソフトウェア、又は、ハードウェア及びソフトウェアの組み合わせとして実現可能である。ハードウェアとソフトウェアとの組み合わせによる実行において、上記コンピュータ・プログラムがインストールされた装置における実行が典型的な例として挙げられる。かかる場合、該コンピュータ・プログラムが該装置のメモリにロードされて実行されることにより、該コンピュータ・プログラムは、該装置を制御し、本発明にかかる処理を実行させる。該コンピュータ・プログラムは、任意の言語、コード、又は、表記によって表現可能な命令群から構成されうる。そのような命令群は、該装置が特定の機能を直接的に、又は、１．他の言語、コード若しくは表記への変換、２．他の媒体への複製、のいずれか一方若しくは双方が行われた後に、実行することを可能にするものである。
【発明の効果】
【００３５】
本発明は、値の比較回数ないしは値の比較のための命令数は増加するが、分岐予測ミスの数を大幅に減少させることが可能である。従って、本発明を実装することによって、プロセッサ、特に分岐予測のオーバーヘッドの大きいプロセッサ上での共通集合演算の性能の向上を達成することが可能である。
【００３６】
また、本発明は、特許文献１に記載のように特定のＣＰＵに依存するＳＩＭＤ命令を用いないために、当該特定のＣＰＵに関わらず（すなわち、どのようなＣＰＵにおいても）適用可能であり、特には分岐予測のオーバーヘッドが大きいＣＰＵにおいて有用である。すなわち、本発明の適用可能な対象は特定のプロセッサに制限されず、種々の規格のプロセッサに適用可能である。また、本発明は、上記特定のＣＰＵに依存するＳＩＭＤ命令を用いないために、例えばＪａｖａ（登録商標）などの特殊命令を直接記述できないような環境においても実行が可能である。
【００３７】
さらに、本発明は、非特許文献２に記載のような前処理を一切要求しない。従って、本発明は例えば、入力データ列が動的に生成されるような場合（下記図３Ｂを参照されたい）においても適用可能である。
【００３８】
さらに、本発明は、２つの入力データ列それぞれを所定のブロック・サイズに従ってブロックに分け、当該ブロック中の各値について値が一致するかどうかを比較するが、本発明は当該ブロック・サイズを明示的にソフトウェア的に制御できるので、例えば２つの入力データ列に対して異なるブロック・サイズを用いたり、又は当該ブロック・サイズを共通集合演算の処理中に動的に変更したりすることが可能である。従って、本発明は、最適化されたブロック・サイズを用いることによって、本発明の実施態様に従う共通集合演算の性能をさらに向上することが可能である。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施態様に従うコンピュータを実現するためのハードウェア構成の一例を示した図である。
【図２Ａ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図２Ｂ】図２Ａに示す共通集合演算を処理するためのアルゴリズムを擬似プログラムにより示した例である。
【図３Ａ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図３Ｂ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図４Ａ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図４Ｂ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図４Ｃ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図４Ｄ】本発明の実施態様に従う共通集合演算の例を示す図である。
【図５】本発明の実施態様において、ブロック・サイズの決定のために使用されうる入力データ列の特性を求める例を示す図である。
【図６Ａ】本発明の実施態様に従う、共通集合演算の処理のフローチャートを示す。
【図６Ｂ】本発明の実施態様に従う、共通集合演算の処理のフローチャートを示す。
【図６Ｃ】本発明の実施態様に従う、共通集合演算の処理のフローチャートを示す。
【図７Ａ】本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価を示す。
【図７Ｂ】本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における異なるＣＰＵ上での性能評価を示す。
【図７Ｃ】本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価を示す。
【図８】本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価を示す。
【図９】図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従うコンピュータの機能ブロック図である。
【図１０Ａ】共通集合演算の例として、２つのソート済みの入力データ列中の値をそれぞれ一つずつ取り出して比較するアルゴリズムを図式化して示す。
【図１０Ｂ】図１０Ａに示す共通集合演算を処理するためのアルゴリズムを擬似プログラムにより示した例である。
【図１１】２つのソート済みの入力データ列において、ある程度離れたデータに対して比較を行う共通集合演算を処理するためのアルゴリズムを擬似プログラムにより示した例である。
【発明を実施するための形態】
【００４０】
以下に、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施態様は特許請求の範囲に係る発明を限定するものでなく、また実施態様の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。また、本発明は多くの異なる態様で実施することが可能であり、以下の実施態様において、種々の変更又は改良を加えることが可能であることが当業者に明らかである。
【００４１】
以下において、特に断らない限り、発明を実施するための形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００４２】
図１は、本発明の実施態様に従うコンピュータを実現するためのハードウェア構成の一例を示した図である。
コンピュータ（１０１）は、中央演算処理装置（ＣＰＵ）（１０２）とメイン・メモリ（１０３）とを備えており、これらはバス（１０４）に接続されている。ＣＰＵ（１０２）は好ましくは、３２ビット又は６４ビットのアーキテクチャに基づくものであり、例えば、インターナショナル・ビジネス・マシーンズ・コーポレーション（登録商標）のＰｏｗｅｒ（商標）シリーズ、インテル株式会社のＣｏｒｅ  ｉ（商標）シリーズ、Ｃｏｒｅ  ２（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｘｅｏｎ（商標）シリーズ、Ｐｅｎｔｉｕｍ（登録商標）シリーズ、Ｃｅｌｅｒｏｎ（登録商標）シリーズ、ＡＭＤ社のＯｐｔｅｒｏｎ（商標）シリーズ、Ｐｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ、Ｓｅｍｐｒｏｎ（商標）又はＡシリーズが使用されうる。コンピュータ（１０１）は、１又は複数のＣＰＵ（１０２）を備えうる。コンピュータ（１０１）は、同じ種類の又は異なる種類のＣＰＵ（１０２）を複数個備えていてもよい。バス（１０４）には、ディスプレイ・コントローラ（１０５）を介して、ディスプレイ（１０６）、例えば液晶ディスプレイ（ＬＣＤ）が接続されうる。ディスプレイ（１０６）は、コンピュータの管理のために、通信回線を介してネットワークに接続されたコンピュータについての情報と、そのコンピュータ上で動作中のソフトウェアについての情報を、適当なグラフィック・インタフェースで表示するために使用される。バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、ディスク（１０８）、例えばシリコン・ディスク又はハードディスクが接続されうる。また、バス（１０４）にはまた、ＳＡＴＡ又はＩＤＥコントローラ（１０７）を介して、任意的に、ドライブ（１０９）、例えばＣＤ、ＤＶＤ又はＢＤドライブが接続されうる。バス（１０４）にはさらに、任意的に、キーボード・マウスコントローラ（１１０）又はＵＳＢバス（図示せず）を介して、キーボード（１１１）及びマウス（１１２）が接続されうるが、本発明を実施する上では必要ない。
【００４３】
ディスク（１０８）には、各種オペレーティング・システム、Ｊ２ＥＥなどのＪａｖａ（登録商標）処理環境、Ｊａｖａ（登録商標）アプリケーション、Ｊａｖａ（登録商標）仮想マシン（ＶＭ）、Ｊａｖａ（登録商標）実行時（ＪＩＴ）コンパイラを提供するプログラム、パイソン処理環境、パイソン・アプリケーション、パイソン実行時コンパイラを提供するプログラム、その他のプログラム、及びデータが、メイン・メモリにロード可能なように記憶されている。また、ディスク（１０８）には、コードの入力乃至は編集を可能にするソフトウェア、文字変換処理ソフトウェアであるフロント・エンド・プロセッサ（ＦＥＰ）がメイン・メモリにロード可能なように記憶されている。オペレーティング・システムは、例えば、ＬＩＮＵＸ（登録商標）ディストリビュータが提供するＬＩＮＵＸ（登録商標）、マイクロソフト・コーポレーションが提供するＷｉｎｄｏｗｓ（登録商標）オペレーティング・システム、アップル・コンピュータ・インコーポレイテッドが提供するＭａｃＯＳ（登録商標）若しくはｉＯＳ（登録商標）、Ｘ  Ｗｉｎｄｏｗ  Ｓｙｓｔｅｍを備えるＵＮＩＸ（登録商標）系システム（たとえば、インターナショナル・ビジネス・マシーンズ・コーポレーション（登録商標）が提供するＡＩＸ（登録商標）でありうる。
【００４４】
ドライブ（１０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをディスク（１０８）にインストールするために使用されうる。
【００４５】
通信インタフェース（１１４）は、例えばイーサネット（登録商標）・プロトコルに従う。通信インタフェース（１１４）は、通信コントローラ（１１３）を介してバス（１０４）に接続され、コンピュータ（１０１）を通信回線（１１５）に物理的に接続する役割を担い、コンピュータ（１０１）のオペレーティング・システムの通信機能のＴＣＰ／ＩＰ通信プロトコルに対して、ネットワーク・インタフェース層を提供する。なお、通信回線は、有線ＬＡＮ環境に基づくもの、又は、無線ＬＡＮ環境、例えば、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｎなどのＷｉ−Ｆｉ規格に基づくものであってもよい。
【００４６】
以上から、本発明の実施態様において使用されるコンピュータは、特定のオペレーティング・システム環境に限定されるものではないことを理解することができるであろう。
【００４７】
以下に、本発明の実施態様において使用されうる「入力データ列」について、以下に説明する。
本発明において、入力データ列は、昇順又は降順にソートされている。当該ソート方法として、当業者に知られている任意の方法が使用されうる。ソート済みの入力データ列は、例えば、コンピュータ（１０１）の記憶部（１０８）に記憶されており、上記共通集合演算の処理をする場合に記憶部（１０８）からＣＰＵ（１０２）内の各レジスタに読み込まれうる。代替的には、ソート済みの入力データ列は、１又は複数のＣＰＵ（１０２）内において又は専用の演算装置内において動的に生成されうる。
【００４８】
ソート済みの入力データ列の値は、０以上の整数である。一つの入力データ列において、原則として重複した値は含まれない。
【００４９】
本発明の実施態様において、２つのソート済みの入力データ列を使用する。以下の説明において、２つのソート済みの入力データ列を、第１の入力データ列、第２の入力データ列と呼ぶ場合がある。
【００５０】
２つのソート済みの入力データ列は同じ長さ（同じデータ数，ｎ個）であってもよく、又は、異なる長さ（異なるデータ数，ｎ１個及びｎ２個）であってもよい。入力データ列の長さは、データ列が有する値の数と同じである。ソート済みの入力データ列の長さは、当該ソート済みの入力データ列の全てが上記ＣＰＵ（１０２）内のレジスタ内に格納される長さであってもよく、又は、当該ソート済みの入力データ列の全てがＣＰＵ（１０２）内のレジスタ内に格納されずに、その一部がＣＰＵ（１０２）内のレジスタ内に格納され、残りがメイン・メモリ（１０３）内若しくは記憶部（１０８）内に格納されてもよい。
【００５１】
２つの入力データ列（同じ又は異なるデータ数、ｎ１個及びｎ２個）は、任意のデータ数を有するブロックに分割されうる。例えば、第１の入力データ列は、その先頭からサイズＢ１（以下、単に「Ｂ１」という場合がある）のデータ数からなるブロック（以下、「第１のブロック」ともいう）に分割されうる。従って、第１の入力データ列についてのブロック数は、ｎ１／Ｂ１個である。また、第２の入力データ列は、その先頭からサイズＢ２（以下、単に「Ｂ２」という場合がある）のデータ数からなるブロック（以下、「第２のブロック」ともいう）に分割されうる。従って、第２の入力データ列についてのブロック数は、ｎ２／Ｂ２個である。第１の入力データ列のサイズＢ１と第２の入力データ列のサイズＢ２とは、同じであってもよく又は異なっていてもよい。但し、本発明の実施態様において、サイズＢ１とサイズＢ２のいずれもが１である場合は除かれる。従って、サイズＢ１及びサイズＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上である。なお、以下において、サイズＢ１及びサイズＢ２を（Ｂ１＝サイズ数，Ｂ２＝サイズ数）と表記する場合がある。
【００５２】
以下では、最初に、本発明の実施態様に従う共通集合演算の処理の理解を容易にするために、当該処理について図２Ａ及び図３Ａ〜図５を参照しながら説明する。次に、当該処理の流れについて図６Ａ〜図６Ｃを参照しながらで説明する。最後に、当該処理を適用した場合に得られる効果について、図７Ａ〜図８を参照して説明する。
【００５３】
図２Ａは、本発明の実施態様に従う共通集合演算の例を示す図である。
図２Ａの例において、２つのソート済みの入力データ列は、それぞれデータ列１及びデータ列２である。データ列１及びデータ列２は、昇順にソート済みであり、いずれのデータ数もｎ（ｎは、整数である）であるとする。また、データ列１のブロック（特許請求の範囲の記載の「第１のブロック」に対応する）のサイズＢ１及びデータ列２の（特許請求の範囲の記載の「第２のブロック」に対応する）のサイズＢ２のいずれも２であるとする。以下において、サイズＢ１とサイズＢ２を（Ｂ１＝サイズ数，Ｂ２＝サイズ数）で表す場合がある。従って、図２Ａの場合、（Ｂ１＝２，Ｂ２＝２）である。
【００５４】
ステップ２０１では、コンピュータ（１０１）は、データ列１のブロックのサイズＢ１及び入力データ列２のブロックのサイズＢ２がいずれも２であるので、データ列１の先頭から２つの値（第１のブロック）（１，５）と、データ列２の先頭から２つの値（第２のブロック）（２，３）とを取り出す。コンピュータ（１０１）は、データ列１の上記取り出した値（１，５）とデータ列２の上記取り出した値（２，３）との全ての組み合わせ（４種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（５）及びデータ列２の第２のブロック中の最後の値（３）のうちの小さい値（３）を有するデータ列２のポインタを次のブロックへ進める。
【００５５】
ステップ２０２では、コンピュータ（１０１）は、データ列２の上記第２のブロック（２，３）の次のブロックから２つの値（５，９）を取り出す。コンピュータ（１０１）は、データ列１の値（１，５）とデータ列２の値（５，９）との全ての組み合わせ（４種類）を比較し、値（５）が一致するので、出力データを格納する作業領域（例えば、ＣＰＵ（１０２）のレジスタ又はメイン・メモリ（１０３））に値（５）を入れる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（５）（すなわち、現在処理中の第１のブロック内の最大値である）及びデータ列２の第２のブロック中の最後の値（９）（すなわち、現在処理中の第１のブロック内の最大値である）のうちの小さい値（５）を有するデータ列１のポインタを次のブロックへ進める。
【００５６】
ステップ２０３では、コンピュータ（１０１）は、データ列１の上記第１のブロックの次のブロックから２つの値（６，８）を取り出す。コンピュータ（１０１）は、データ列１の値（６，８）とデータ列２の値（５，９）との全ての組み合わせ（４種類）を比較し、値が一致しないので、共通する値を出力しない。なお、コンピュータ（１０１）は、ステップ２０２において値（５）が既に一致する値として出力されているので、データ列１の値（６，８）とデータ列２の値（５，９）との全ての組み合わせ（４種類）を比較することなしに、データ列１の値（６，８）とデータ列２の値（９）（すなわち、値（５）を除く）との全ての組み合わせ（２種類）を比較するようにしうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（８）及びデータ列２の第２のブロック中の最後の値（９）のうちの小さい値（８）を有するデータ列１のポインタを次のブロックへ進める。
【００５７】
ステップ２０４では、コンピュータ（１０１）は、データ列１の上記第１のブロックの次のブロックから２つの値（１１，１４）を取り出す。コンピュータ（１０１）は、データ列１の値（１１，１４）とデータ列２の値（５，９）との全ての組み合わせ（４種類）を比較し、値が一致しないので、共通する値を出力しない。なお、コンピュータ（１０１）は、ステップ２０２において値（５）が既に一致する値として出力されているので、データ列１の値（１１，１４）とデータ列２の値（５，９）との全ての組み合わせ（４種類）を比較することなしに、データ列１の値（１１，１４）とデータ列２の値（９）（すなわち、値（５）を除く）との全ての組み合わせ（２種類）を比較するようにしうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（１４）及びデータ列２の第２のブロック中の最後の値（９）のうちの小さい値（９）を有するデータ列２のポインタを次のブロックへ進める。
【００５８】
ステップ２０５では、コンピュータ（１０１）は、データ列２の上記第２のブロックの次のブロックから２つの値（１０，１２）を取り出す。コンピュータ（１０１）は、データ列１の値（１１，１４）とデータ列２の値（１０，１２）との全ての組み合わせ（４種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（１４）及びデータ列２の第２のブロック中の最後の値（１２）のうちの小さい値（１２）を有するデータ列２のポインタを次のブロックへ進める。
【００５９】
コンピュータ（１０１）は、以降、上記と同様にして、第１及び第２のブロック中の最後の値が小さいデータ列の次のブロックの取り出すこと、及び当該第１及び第２のブロック中の値同士の比較を繰り返して行い、当該第１及び第２の入力データ列の間で共通する値を出力データとして順次出力していく。従って、出力データも結果としてソート済の状態で出力された状態である。
【００６０】
図２Ｂは、図２Ａに示す共通集合演算を処理するためのアルゴリズムを擬似プログラムにより示した例である。擬似プログラム（２１１）中、左端の数字01〜34は行番号を示すために便宜的に付したものである。
【００６１】
擬似プログラム（１０１１）の行19は、分岐予測ミスが多発する分岐条件を示す。上記共通集合演算（Ｂ１＝２，Ｂ２＝２）の場合、４種類の組み合わせの値同士の比較判断処理が行04〜行06，行07〜行10，行11〜行13，及び行15〜18において行われ、そして当該比較判断処理を満たさない場合に、行19の処理に進みうる。従って、行19の処理に進む前に、４種類の組み合わせの値同士の比較判断処理が既に行われている。また、本発明に従う２つのブロック内の各値の比較での条件分岐（大小比較ではなく、一致の分岐である）は、一般的に「ｎｏｔ  ｔａｋｅｎ」（分岐せず）になることが支配的であるために、分岐予測ミスの回数には大きな影響を与えない。結局、分岐予測ミスを頻繁に起こす分岐命令の回数は、（ｎ１＋ｎ２）／Ｂ回（Ｂ１とＢ２が同じ場合）となり、Ｂが大きい方が当該分岐命令の回数が少なくなる。従って、図１０Ａ及びＢに示した上記ナイーブ・アルゴリズムに比べて、値同士の比較の回数は４倍に増えるけれども、分岐予測ミスが多発する分岐条件を経る回数が大幅に減っている。
【００６２】
図３Ａは、本発明の実施態様に従う共通集合演算の例を示す図である。
図３Ａの例において、２つのソート済みの入力データ列は、それぞれデータ列１及びデータ列２である。データ列１及びデータ列２は、昇順にソート済みであり、いずれのデータ数もｎ（ｎは、整数である）であるとする。また、データ列１のブロック（特許請求の範囲の記載の「第１のブロック」に対応する）のサイズＢ１は３であり、且つ、データ列２のブロック（特許請求の範囲の記載の「第２のブロック」に対応する）のサイズＢ２は１であるとする（Ｂ１＝３，Ｂ２＝１）。
【００６３】
ステップ３０１では、コンピュータ（１０１）は、データ列１の第１のブロックのサイズＢ１が３であり、且つ、データ列２の第２のブロックのサイズＢ２が１であるので、データ列１の先頭から３つの値（第１のブロック）（１，５，６）と、データ列２の先頭から１つの値（第２のブロック）（２）とを取り出す。コンピュータ（１０１）は、データ列１の上記取り出した値（１，５，６）とデータ列２の上記取り出した値（２）との全ての組み合わせ（３種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（６）及びデータ列２の第２のブロック中の最後の値（２）のうちの小さい値（２）を有するデータ列２のポインタを次のブロックへ進める。
【００６４】
ステップ３０２では、コンピュータ（１０１）は、データ列２の上記第２のブロック（２）の次のブロックから１つの値（３）を取り出す。コンピュータ（１０１）は、データ列１の値（１，５，６）とデータ列２の値（３）との全ての組み合わせ（３種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（６）及びデータ列２の第２のブロック中の最後の値（３）のうちの小さい値（３）を有するデータ列１のポインタを次のブロックへ進める。
【００６５】
ステップ３０３では、コンピュータ（１０１）は、データ列２の上記第２のブロック（３）の次のブロックから１つの値（５）を取り出す。コンピュータ（１０１）は、データ列１の値（１，５，６）とデータ列２の値（５）との全ての組み合わせ（３種類）を比較し、値（５）が一致するので、出力データを格納する作業領域に値（５）を入れる。なお、コンピュータ（１０１）は、第１のブロックのうち、値（５）が一致しているので、当該一致した値（５）と第２のブロックの値（５）との比較をスキップしうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（６）及びデータ列２の第２のブロック中の最後の値（５）のうちの小さい値（５）を有するデータ列２のポインタを次のブロックへ進める。
【００６６】
ステップ３０４では、コンピュータ（１０１）は、データ列２の上記第２のブロック（５）の次のブロックから１つの値（９）を取り出す。コンピュータ（１０１）は、データ列１の値（１，５，６）とデータ列２の値（９）との全ての組み合わせ（３種類）を比較し、値が一致しないので、共通する値を出力しない。なお、コンピュータ（１０１）は、データ列２の第２のブロックのサイズＢ２が１であり、且つ、現在の第２のブロックの値（９）が現在の第１のブロック中の最後の値（６）よりも大きいので、ステップ３０４の比較自体をスキップすることが可能でありうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（６）及びデータ列２の第２のブロック中の最後の値（９）のうちの小さい値（６）を有するデータ列１のポインタを次のブロックへ進める。
【００６７】
ステップ３０５〜ステップ３０７においても、コンピュータ（１０１）は、上記と同様にして、第１及び第２のブロック中の最後の値が小さいデータ列の次のブロックの取り出すこと、及び当該第１及び第２のブロック中の値同士の比較を繰り返して行い、当該第１及び第２の入力データ列の間で共通する値を出力データとして順次出力していく。
【００６８】
ステップ３０８は、データ列１の最後（ｎ）のみがまだ未処理として残った場合を示す。コンピュータ（１０１）は、データ列１のサイズＢ１を３から１に動的に変更する（Ｂ１＝１，Ｂ２＝１）。コンピュータ（１０１）は、データ列１の上記最後の値（３２）を取り出す。コンピュータ（１０１）は、データ列１の値（３２）とデータ列２の値（３３）とを比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（３２）及びデータ列２の第２のブロック中の最後の値（３０）のうちの小さい値（３０）を有するデータ列２のポインタを次のブロックへ進める。
【００６９】
ステップ３０９では、コンピュータ（１０１）は、データ列２の上記第２のブロック（３０）の次のブロックから１つの値（３３）を取り出す。コンピュータ（１０１）は、データ列１の値（３２）とデータ列２の値（３３）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１及びデータ列２のいずれも最後まで処理されたことに応じて、共通集合演算の処理を終了する。
【００７０】
その結果、コンピュータ（１０１）は、出力データとして、（５，１５，２０，２４，２７）を得た。
【００７１】
本発明の１つの実施態様において、上記ステップ３０８に示すように、データ列の未処理のデータ数がブロックのサイズ数よりも小さくなった場合には、コンピュータ（１０１）は、ブロックのサイズを当該未処理のデータ数全ての数若しくはその一部、又は１に動的に変更することが可能である。
【００７２】
図３Ｂは、本発明の実施態様に従う共通集合演算の例を示す図である。
図３Ｂの例において、２つのソート済みの入力データ列は、図３Ａにおいて得られた出力データ（以下、「出力データ１」という）と、データ列３である。出力データ列１は、図３Ａにおける処理において昇順で出力されている。また、出力データ１のブロック（特許請求の範囲の記載の「第１のブロック」に対応する）のサイズＢ１は２であり、且つ、データ列３のブロック（特許請求の範囲の記載の「第２のブロック」に対応する）のサイズＢ２は３であるとする（Ｂ１＝２，Ｂ２＝３）。
【００７３】
ステップ３１１では、コンピュータ（１０１）は、出力データ１のブロックのサイズＢ１が２であり、且つ、データ列３のブロックのサイズＢ２が３であるので、出力データ１の先頭から２つの値（第１のブロック）（５，１５）と、データ列３の先頭から３つの値（第２のブロック）（４，７，１５）とを取り出す。コンピュータ（１０１）は、出力データ１の上記取り出した値（５，１５）とデータ列３の上記取り出した値（４，７，１５）との全ての組み合わせ（６種類）を比較し、値（１５）が一致するので、出力データを格納する作業領域に値（１５）を入れる。次に、コンピュータ（１０１）は、出力データ１の第１のブロック中の最後の値（１５）とデータ列３の第２のブロック中の最後の値（１５）とが同じであるので、出力データ１及びデータ列３の両方のポインタを次のブロックへ進める。
【００７４】
コンピュータ（１０１）は、ステップ３１１以降においても、上記と同様にして、出力データ１のブロック（第１のブロック）中の最後の値とデータ列３のブロック（第２のブロック）中の最後の値とを比較して、当該最後の各値のうち小さい値を有するブロックの入力データ列から当該小さい値を有するブロックの次のブロックを取り出すこと、そして当該第１のブロック中の値と当該第２のブロック中の各値との組み合わせの比較を行うことを繰り返して行い、出力データ１とデータ列３との間で共通する値を出力データとして順次出力していく。
【００７５】
本発明の１つの実施態様において、共通集合演算の処理において出力された結果である出力データを引き続き入力データ列として使用しうる。従って、コンピュータ（１０１）は、３つ以上の入力データ列についても本発明の上記実施態様に従って共通集合演算の処理を順次行うことによって、３つ以上の入力データ列について共通集合演算の処理を行うことができる。また、コンピュータ（１０１）は、図３Ａに示すデータ列１とデータ列２との共通集合演算の処理が終了した後に、図３Ｂに示す当該処理の結果である出力データ１とデータ列３との共通集合演算の処理を行ってもよく、又は、図３Ａに示すデータ列１とデータ列２との共通集合演算の処理の途中で、すなわち出力データ１の値を得ている途中において、図３Ｂに示す出力データ１とデータ列３との共通集合演算の処理を並行して行ってもよい。また、コンピュータ（１０１）は、図３Ａに示すデータ列１とデータ列２との共通集合演算の処理の途中で、すなわち出力データ１の値を得ている途中において一旦当該処理を中断して、図３Ｂに示す出力データ１とデータ列３との共通集合演算の処理を行い、必要に応じて、図３Ａに示すデータ列１とデータ列２との共通集合演算の処理を再開するようにしてもよい。
【００７６】
図４Ａ及び図４Ｂは、本発明の実施態様に従う共通集合演算の例を示す図である。
図４Ａ及び図４Ｂの例において、２つのソート済みの入力データ列は、それぞれデータ列１及びデータ列２である。データ列１及びデータ列２は、昇順にソート済みであり、データ列１のデータ数は１０ｎ（ｎは、整数である）及びデータ列２のデータ数はｎ（ｎは、整数である）であるとする。また、データ列１のブロック（特許請求の範囲の記載の「第１のブロック」に対応する）のサイズＢ１は４であり、且つ、データ列２のブロック（特許請求の範囲の記載の「第２のブロック」に対応する）のサイズＢ２は２であるとする（Ｂ１＝４，Ｂ２＝２）。
【００７７】
ステップ４０１では、コンピュータ（１０１）は、データ列１の第１のブロックのサイズＢ１が４であり、且つ、データ列２の第２のブロックのサイズＢ２が２であるので、データ列１の先頭から４つの値（第１のブロック）（0，100，200，300）と、データ列２の先頭から２つの値（第２のブロック）（1，10）とを取り出す。コンピュータ（１０１）は、データ列１の上記取り出した値（0，100，200，300）とデータ列２の上記取り出した値（1，10）との全ての組み合わせ（８種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（300）及びデータ列２の第２のブロック中の最後の値（10）のうちの小さい値（10）を有するデータ列２のポインタを次のブロックへ進める。
【００７８】
ステップ４０２では、コンピュータ（１０１）は、データ列２の上記第２のブロック（1，10）の次のブロックから２つの値（100，1,000）を取り出す。コンピュータ（１０１）は、データ列１の値（0，100，200，300）とデータ列２の値（100，1,000）との全ての組み合わせ（８種類）を比較し、値（100）が一致するので、出力データを格納する作業領域に値（100）を入れる。なお、コンピュータ（１０１）は、データ列２の最後の値（1,000）がデータ列１の最後の値（300）よりも大きいので、データ列２の最後の値（1,000）とデータ列１の最後の値（300）よりも前の値との比較をスキップしうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（300）及びデータ列２の第２のブロック中の最後の値（1,000）のうちの小さい値（300）を有するデータ列１のポインタを次のブロックへ進める。
【００７９】
ステップ４０３では、コンピュータ（１０１）は、データ列１の上記第１のブロック（0，100，200，300）の次のブロックから４つの値（400，500，600，700）を取り出す。コンピュータ（１０１）は、データ列１の値（400，500，600，700）とデータ列２の値（100，1,000）との全ての組み合わせ（８種類）を比較し、値が一致しないので、共通する値を出力しない。なお、コンピュータ（１０１）は、データ列２の第２のブロックのサイズＢ２が２であり、且つ、データ列１の最初の値（100）がデータ列１の最初の値（400）よりも小さく、データ列２の第２のブロック中の最後の値（1,000）がデータ列１の最後の値（700）よりも大きいので、上記最初の値同士の比較及び上記最後の値同士の比較以外の比較をスキップしうる。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（700）及びデータ列２の第２のブロック中の最後の値（1,000）のうちの小さい値（700）を有するデータ列１のポインタを次のブロックへ進める。
【００８０】
ステップ４０４〜ステップ４０６においても、コンピュータ（１０１）は、上記と同様にして、第１及び第２のブロックのうち最後の値が小さいブロックを有するデータ列から次のブロックを取り出すこと、そして当該第１及び第２のブロック中の各値の組み合わせを比較することを繰り返して行い、当該第１及び第２の入力データ列の間で共通する値を出力データとして順次出力していく。
【００８１】
ステップ４０７では、コンピュータ（１０１）は、データ列１の第１のブロック（2,000，3,000，4,000，6,000）の次のブロックから４つの値（10,000，14,000，18,000，22,000）を取り出す。コンピュータ（１０１）は、データ列１の値（10,000，14,000，18,000，22,000）とデータ列２の値（10,000，100,000）との全ての組み合わせ（８種類）を比較し、値が一致しないので、共通する値を出力しない。コンピュータ（１０１）は、所定の条件を満たすことに応じて、ブロック・サイズを変更するかどうかを判断する。ブロック・サイズの変更については、下記図６Ｂにおいて詳述する。コンピュータ（１０１）は、所定の条件を満たすことに応じて、ブロック・サイズを変更する。変更後のブロック・サイズは、（Ｂ１＝４，Ｂ２＝２）から（Ｂ１＝６，Ｂ２＝２）である。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（22,000）及びデータ列２の第２のブロック中の最後の値（100,000）のうちの小さい値（22,000）を有するデータ列１のポインタを次のブロックへ進める。
【００８２】
ステップ４０８では、コンピュータ（１０１）は、データ列１の第１のブロック（10,000，14,000，18,000，22,000）の次のブロックから６つの値（26,000，30,000，34,000，38,000，42,000，46,000）を取り出す。コンピュータ（１０１）は、データ列１の値（26,000，30,000，34,000，38,000，42,000，46,000）とデータ列２の値（10,000，100,000）との全ての組み合わせ（８種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（46,000）及びデータ列２の第２のブロック中の最後の値（100,000）のうちの小さい値（46,000）を有するデータ列１のポインタを次のブロックへ進める。
【００８３】
コンピュータ（１０１）は、引き続き、上記と同様にして、第１及び第２のブロック中の最後の値が小さいデータ列の次のブロックの取り出すこと、及び当該第１及び第２のブロック中の値同士の比較を繰り返して行い、当該第１及び第２の入力データ列の間で共通する値を出力データとして順次出力していく。
【００８４】
ステップ４０９では、コンピュータ（１０１）は、データ列１の第１のブロック（64,000，68,000，72,000，76,000，78,000，80,000）の次のブロックから６つの値（105,000，130,000，155,000，185,000，210,000，260,000）を取り出す。コンピュータ（１０１）は、データ列１の値（105,000，130,000，155,000，185,000，210,000，260,000）とデータ列２の値（10,000，100,000）との全ての組み合わせ（１２種類）を比較し、値が一致しないので、共通する値を出力しない。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（260,000）及びデータ列２の第２のブロック中の最後の値（100,000）のうちの小さい値（100,000）を有するデータ列２のポインタを次のブロックへ進める。
【００８５】
コンピュータ（１０１）は、ステップ４０９以降においても、上記と同様にして、第１及び第２のブロックのうち最後の値が小さいブロックを有するデータ列から次のブロックを取り出すこと、そして当該第１及び第２のブロック中の各値の組み合わせを比較することを繰り返して行い、当該第１及び第２の入力データ列の間で共通する値を出力データとして順次出力していく。また、コンピュータ（１０１）は、所定の条件を満たすことに応じて、ブロック・サイズをさらに変更しうる。
【００８６】
本発明の１つの実施態様において、共通集合演算の処理途中において、所定の条件を満たすことに応じて、ブロック・サイズを動的に変更することが可能である。また、ブロック・サイズは、入力データ列１及び入力データ列２それぞれの特性に応じて求められる。従って、コンピュータ（１０１）は、共通集合演算の処理途中における上記特性に応じてブロック・サイズを動的に変更することが可能である。
【００８７】
図４Ｃ及び図４Ｄは、本発明の実施態様に従う共通集合演算の例を示す図である。
図４Ｃ及び図４Ｄの例において、２つのソート済みの入力データ列は、それぞれデータ列１及びデータ列２であり、図４Ａ及び図４Ｂの例において示す２つのソート済みの入力データ列と同じである。また、データ列１のブロック（特許請求の範囲の記載の「第１のブロック」に対応する）のサイズＢ１は４であり、且つ、データ列２のブロック（特許請求の範囲の記載の「第２のブロック」に対応する）のサイズＢ２は２であるとする（Ｂ１＝４，Ｂ２＝２）。
【００８８】
図４Ｃ及び図４Ｄに示すステップ４１１〜ステップ４１７は、図４Ａ及び図４Ｂに示すステップ４０１〜ステップ４０７と同じであるので、ここではそれらの説明を省略する。
【００８９】
ステップ４１８では、コンピュータ（１０１）は、データ列１の第１のブロック（10,000，14,000，18,000，22,000）の次のブロックから４つの値（26,000，30,000，34,000，38,000）を取り出す。コンピュータ（１０１）は、データ列１の値（26,000，30,000，34,000，38,000）とデータ列２の値（10,000，100,000）との全ての組み合わせ（８種類）を比較し、値が一致しないので、共通する値を出力しない。コンピュータ（１０１）は、所定の条件を満たすことに応じて、ブロックをスキップするかどうかを判断する。スキップするかどうかの判断については例えば、上記した図１１に示すアルゴリズムを使用して実装することが可能である。コンピュータ（１０１）は、所定の条件を満たすことに応じて、所定数分のブロックをスキップするように決定する。次に、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（38,000）及びデータ列２の第２のブロック中の最後の値（100,000）のうちの小さい値（38,000）を有するデータ列１のポインタをスキップ後の次のブロックへ進める。
【００９０】
図５は、本発明の実施態様において、ブロック・サイズの決定のために使用されうる入力データ列の特性を求める例を示す図である。
まず、入力データ列の特性について説明する。入力データ列の特性は例えば、入力データ列のデータ数、入力データ列の値の分布の偏り、又は、入力データ列のデータ数と上記一致する値の出力データ数から求められる値でありうる。
【００９１】
入力データ列の特性が入力データ列のデータ数（値の数でもある）である場合は、第１の入力データ列のデータ数と第２の入力データ列のデータ数に基づいて、ブロック数を決定する。例えば、第１の入力データ列のデータ数が２ｎ（ｎは１以上の整数である）であり、第２の入力データ列のデータ数がｎ（ｎは１以上の整数である）である場合に、第１の入力データ列のブロックのサイズＢ１は４であり、第２の入力データ列のブロックのサイズＢ２は２であるとすることができる（Ｂ１＝４，Ｂ２＝２）。
【００９２】
入力データ列の値の分布の偏りとは例えば、第１の入力データ列と第２の入力データ列の各平均値（Ａｄ）の比である。入力データ列の平均値（Ａｄ）は、入力データ列中の最初の値又は次に取り出されるブロックの最初の値から最後の値までの隣接する各値間の差の平均値である。入力データの平均値（Ａｄ）は下記式で表されうる：
・平均値（Ａｄ）を入力データ列全体から求める場合（すなわち、共通集合演算の開始前に平均値を求める場合である）、
平均値（Ａｄ）＝（（入力データ列の最後の値）−（入力データ列の最初の値））／（入力データ列のデータ数−１）；
・平均値（Ａｄ）を入力データ列途中から求める場合（すなわち、共通集合演算の処理の途中に平均値を求める場合である）
平均値（Ａｄ）＝（（入力データ列の最後の値）−（入力データ列の現在処理した値の次の値））／（入力データ列の未処理のデータ個数−１）。
【００９３】
入力データ列のデータ数と上記一致する値の出力データ数から求められる値とは例えば、第１の入力データ列及び第２の入力データ列の処理したデータ数の合計値と出力データ数との比率（例えば、出力データ数／第１の入力データ列の処理したデータ数と第２の入力データ列の処理したデータ数との合計値）若しくは差、又は、出力データ数に対する第１の入力データ列の全データ数と第２の入力データ列の全データ数との合計値との比率でありうる。
【００９４】
上記では、入力データ列の特性を求める例を示した。以下では、図５の記載に従って、平均値（Ａｄ）をどのようにして求めるのかの一例を説明する。
図５は、２つのソート済みの入力データ列であるデータ列１及びデータ列２について、平均値（Ａｄ）を求める例を示す。
図５の符号５０１は、入力データ列の平均値（Ａｄ）が本発明の実施態様に従う共通集合演算の処理の前に求められる場合の例を示す。当該例の場合には、当該入力データ列の平均値（Ａｄ）は、入力データ列中の最初の値から最後の値までの隣接する各値間の差の平均値である。データ列１の平均値（Ａｄ）とデータ列２の平均値（Ａｄ）が求められた後に、例えばデータ列１の平均値（Ａｄ）とデータ列２の平均値（Ａｄ）との比率（図５の例の場合、データ列２の平均値（Ａｄ）に対するデータ列１の平均値（Ａｄ）である：データ列１の平均値（Ａｄ）／データ列２の平均値（Ａｄ））が求められる。
図５の符号５０２は、入力データ列の平均値（Ａｄ）が本発明の実施態様に従う共通集合演算の処理の途中に求められる場合の例を示す。当該例の場合には、当該入力データ列の平均値（Ａｄ）は、入力データ列中の次に処理される値から最後の値までの隣接する各値間の差の平均値である。符号５０２の例では、コンピュータ（１０１）は、データ列１の第１のブロック中の最後の値（４００）及びデータ列２の第２のブロック中の最後の値（１００）のうちの小さい値（１００）を有するデータ列２のポインタを次のブロックへ進めて、次に、データ列１の値（200，400）とデータ列２の値（1,000）との全ての組み合わせ（２種類）を比較しようとしている例を示す。当該例において、データ列１の平均値（Ａｄ）は次に処理される値（すなわち、先頭から３番目の値200）から当該データ列１の最後（先頭から８番目）の値（1,600）までの平均値であり、データ列２の平均値（Ａｄ）は次に処理される値（すなわち、先頭から４番目の値（1,000））から当該データ列２の最後（先頭から６番目）の値（50,000）までの平均値である。データ列１の平均値（Ａｄ）とデータ列２の平均値（Ａｄ）が求められた後に、例えばデータ列１の平均値（Ａｄ）とデータ列の平均値（Ａｄ）との比率（図５の例の場合、データ列２の平均値（Ａｄ）に対するデータ列１の平均値（Ａｄ）である：データ列１の平均値／データ列２の平均値）が求められる。
【００９５】
以下において、入力データ列の値の分布の偏りからブロック・サイズをどのように求めるかについて以下に説明する。
【００９６】
データ列１の平均値（Ａｄ）とデータ列２の平均値（Ａｄ）との比率がある閾値（例えば、事前に定義されている）を超えた場合には、データ列１とデータ列２に異なるブロック・サイズを用いることができる。例えば、上記平均値（Ａｄ）が小さいデータ列について、ブロック・サイズを大きくしうる。
【００９７】
ブロック・サイズは例えば、ブロック・サイズを変えた複数の実装（例えば、複数の最適化された実装）を用意しておき、平均値（Ａｄ）に応じて適切な実装を選択可能なようにしておくことによって決定されうる。
（１）例えば、２つの入力データ列の各平均値（Ａｄ）に大きな差がない場合には、当該２つの入力データ列に対して、（Ｂ１＝３，Ｂ２＝３）程度に設定することが分岐予測ミスの削減と命令数の増加とのバランスの上で適切でありうる（例えば、下記図７Ａを参照）。
（２）例えば、２つの入力データ列の各平均値（Ａｄ）に１０倍程度の差がある場合において、第２の入力データ列の平均値（Ａｄ）が第１の入力データ列の平均値（Ａｄ）よりも小さいとすると、当該２つの入力データ列に対して、（Ｂ１＝２，Ｂ２＝４）というように異なるブロック・サイズを使用することによって、例えばさらに１０％程度の性能向上が得られうる。従って、例えば、ブロック・サイズを変えた複数の実装として、（Ｂ１＝３，Ｂ２＝３），（Ｂ１＝２，Ｂ２＝４）及び（Ｂ１＝４，Ｂ２＝２）を用意しておき、第１の入力データ列の平均値（Ａｄ）と第２の入力データ列の平均値（Ａｄ）との比率が５を超えた場合に、上記複数の実装のうちの最適なブロック・サイズを有する実装に変更する（すなわち、ブロック・サイズを切り替える）ことが可能である。
【００９８】
上記の例では、ブロック・サイズを変えた複数の実装として３つを挙げたが、より多くのブロック・サイズの実装を用意しておいてもよい。
【００９９】
また、入力データ列の平均値（Ａｄ）の計算及びブロック・サイズの変更を本発明の実施態様に従う共通集合演算の処理の途中に行う場合には、全ての繰り返し（イタレーション）において当該計算及び当該変更を行う必要は無い。従って、当該計算及び当該変更を本発明の実施態様に従う共通集合演算の処理の途中に行うことは、大きなオーバーヘッドにはならない。例えば、図２Ｂに示した擬似プログラムの例では、Aend（23行目及び32行目）及びBend（27行目及び32行目）というループの終了条件を、全データ数の代わりに次にチェックしておくタイミング（例えば、全データ数の１／１００）を指定しておくことによって、最内ループでは追加の条件分岐無しに一定の間隔で上記計算及び上記変更を行うことが可能である。
【０１００】
このように平均値（Ａｄ）に従ってブロック・サイズを変更することによって、本発明の実施態様に従う共通集合演算の更なる性能向上が得られうる。
【０１０１】
以下において、第１の入力データ列及び第２の入力データ列の処理したデータ数の合計値と出力データ数との比率からブロック・サイズをどのように求めるかについて以下に説明する。
本発明は、２つの入力データ間で共通する値が少ない場合であっても多い場合であっても有用である（例えば、下記図７Ｃを参照）。例えば２つの入力データ列の間で共通する値がごく少数しか出力されないと場合であっても、そのデータ特性に基づいて分岐予測ミスを削減し、その結果として共通集合演算の性能向上を達成することが可能である。しかしながら、入力データ列のデータ数に対して、出力データ数が多い場合には、ＣＰＵの特性によってはブロック・サイズが大きいと共通集合演算の性能向上が影響されうる場合がある。そこで、入力データ列をある程度処理したところで、それまでに処理した２つの入力データのデータ数の合計数と出力データ数との比率（例えば、出力データ数／第１の入力データ列の処理したデータ数と第２の入力データ列の処理したデータ数との合計値）又は、出力データ数に対する第１の入力データ列の全データ数と第２の入力データ列の全データ数との合計値との比率を計算して、ある閾値よりも大きかった場合には、２つの入力データ列の両方又は一方のブロック・サイズを小さくすることによって、上記影響を回避することが可能である。例えば、ブロック・サイズを（Ｂ１＝２，Ｂ１＝１）、（Ｂ１＝１，Ｂ１＝２）、又は（Ｂ１＝１，Ｂ１＝１）に変更しうる。なお、出力データ数は当然ながら２つの入力データ列のうちの短い方の入力データ列のデータ数を超えることがないので、２つの入力データ列間に極端な差がある場合には、２つの入力データ列のデータ数の合計数に対する出力データ数は大きくならない。従って、この場合には、２つの入力データ列のうちの長い方の入力データ列のポインタを進める頻度が非常に高くなるために条件分岐ミスが起こしにくくなる故に、上記に示した通り、出力データ数に対する第１の入力データ列の全データ数と第２の入力データ列の全データ数との合計値との比率を求めることが有用である。
【０１０２】
図６Ａないし図６Ｃは、本発明の実施態様に従う、共通集合演算の処理のフローチャートを示す。なお、当該フローチャートに示す処理は、コンピュータ（１０１）、１つ又は複数の演算処理装置（例えば、１又は複数の中央演算処理装置（１０２）又は専用の１又は複数の演算処理装置）が主体となって行いうる。以下に示すフローチャートの説明では、各ステップの主体がコンピュータ（１０１）であるとして述べているが、各ステップの主体をコンピュータ（１０１）の代わりに、１つ又は複数の上記演算処理装置に置き換えてもよい。
【０１０３】
ステップ６０１では、コンピュータ（１０１）は、本発明に従う共通集合演算の処理を開始する。
【０１０４】
ステップ６０２では、コンピュータ（１０１）は、ソート済みの第１の入力データ列及び第２の入力データ列を受け取る。コンピュータ（１０１）は例えば、ソート済みの第１の入力データ列及び第２の入力データ列それぞれをＣＰＵ（１０２）上の異なるレジスタ内に受け取る。代替的には、コンピュータ（１０１）は、未ソートの第１の入力データ列及び第２の入力データ列を受け取り、当該受け取った未ソートの第１の入力データ列及び第２の入力データ列を、昇順又は降順にソートしうる。
【０１０５】
ステップ６０３では、コンピュータ（１０１）は、共通集合演算の処理のために、第１の入力データ列及び第２の入力データ列それぞれから取り出されるブロックのサイズ数であるブロック・サイズ（それぞれ、サイズＢ１及びサイズＢ２とする、但し、サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、サイズＢ１はサイズＢ２と同じ又は異なるデータ数である）が事前定義されているかどうかを判断する。コンピュータ（１０１）は事前定義されたブロック・サイズがある場合には、処理をステップ６０４に進める。事前定義されたブロック・サイズは例えば、ユーザによって事前に定義又は設定されており、当該定義されたブロック・サイズは例えば共通集合演算の処理のためのプログラム中に記述されている。例えば、図２Ｂに示す擬似プログラム（２１１）中の行04（Adat0 == Bdat0），行07（Adat0 == Bdat1），行11（Adat1== Bdat0）及び行15（Adat1 == Bdat1）から、（Ｂ１＝２，Ｂ２＝２）である。一方、コンピュータ（１０１）は事前定義されたブロック・サイズがない場合には、処理をステップ６０５に進める。
【０１０６】
ステップ６０４では、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列それぞれについての事前定義された各ブロック・サイズＢ１及びＢ２を読み取る。
【０１０７】
ステップ６０５では、コンピュータ（１０１）は、事前定義されたブロック・サイズが無いことに応じて、例えば図５の説明において説明した特性のうちどの特性を求めるかを読み取る。どの特性を求めるかは例えば、予めユーザによって例えば共通集合演算の処理のためのプログラム中に記述されている。コンピュータ（１０１）は、ブロック・サイズを求めるために使用する特性として、一つの特性を使用してもよく、又は、複数の特性を組み合わせて使用してもよい。そして、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列についての上記読み取った各特性を求める。特性は、図５の上記説明において述べた通りであり、例えば入力データ列のデータ数、入力データ列の値の分布の偏りである。
【０１０８】
ステップ６０６では、コンピュータ（１０１）は、ステップ６０４で求められた各特性に応じて、第１の入力データ列及び第２の入力データ列それぞれの各ブロック・サイズＢ１及びＢ２を決定する。例えば下記の通りである：
・特性が入力データ列のデータ数である場合、
第１の入力データ列のデータ数が所定数以上であり且つ第２の入力データ列のデータ数が当該所定数よりも小さい場合には、サイズＢ１はサイズＢ２よりも大きく、
第２の入力データ列のデータ数が所定数以上であり且つ第１の入力データ列のデータ数が当該所定数よりも小さい場合には、サイズＢ２はサイズＢ１よりも大きい；
・特性が入力データ列中の最初の値から最後の値までの隣接する各値間の差の平均値である場合、
第１の入力データ列の平均値（Ａｄ）と第２の入力データ列の平均値（Ａｄ）との比率又は差が第１の閾値を超える場合において、
第１の入力データ列の上記平均値（Ａｄ）が第２の入力データ列の上記平均値（Ａｄ）よりも小さい場合には、サイズＢ１はサイズＢ２よりも大きく、
第２の入力データ列の上記平均値（Ａｄ）が第１の入力データ列の上記平均値（Ａｄ）よりも小さい場合には、サイズＢ２はサイズＢ１よりも大きい。
【０１０９】
ステップ６０７では、コンピュータ（１０１）は、第１の入力データ列の先頭からサイズＢ１の第１のブロック及び第２の入力データ列の先頭からサイズＢ２の第２のブロックそれぞれを、例えばＣＰＵ（１０２）内の各レジスタ内に取り出す。代替的には、コンピュータ（１０１）は、第１の入力データ列をその先頭からサイズＢ１に分割して例えばメモリ（１０３）内に格納しておき、その分割されたブロック（特許請求の範囲に記載の「第１のブロック」である）のうちの最初の１つのブロックを上記メモリ（１０３）から取り出す。また、コンピュータ（１０１）は、第２の入力データ列をその先頭からサイズＢ２に分割して例えばメモリ（１０３）内に格納しておき、その分割されたブロック（特許請求の範囲に記載の「第２のブロック」である）のうちの最初の１つのブロックを上記メモリ（１０３）から取り出す。
【０１１０】
ステップ６０８では、コンピュータ（１０１）は、ステップ６０７で取り出された第１のブロック中の各値とステップ６０７で取り出された第２のブロック中の各値との組み合わせを比較する。当該組み合わせの比較は、第１及び第２の各ブロック中の各値同士の全ての比較を行うが、比較の途中でそれ以降の比較において値同士が一致しないことが予め判る場合ないしは明白な場合には、それ以降の比較を中止してよい。各値の比較は例えば、ＳＩＭＤ命令、又は専用命令（例えば、ＳＳＥ４の文字に対するＰＣＭＰＥＳＴＲＭ命令）を使用することができる。
【０１１１】
ステップ６０９では、コンピュータ（１０１）は、ステップ６０８における比較において一致した値があるか否かを判断する。コンピュータ（１０１）は、一致した値があることに応じて、処理をステップ６１０に進める。一方、コンピュータ（１０１）は、一致した値がないことに応じて、処理をステップ６１１に進める。
【０１１２】
ステップ６１０では、コンピュータ（１０１）は、一致した値があることに応じて、当該一致した値を出力データとして出力する。コンピュータ（１０１）は、出力データを例えば、ＣＰＵ（１０２）内のレジスタ内に格納する。なお、一致する値が複数ある場合には、当該値は、昇順にソート済みの第１及び第２の入力データ列と同様に、昇順に並び替えられて出力される。
【０１１３】
ステップ６１１では、コンピュータ（１０１）は、一致した値がないことに応じて、ステップ６０７において取り出された第１のブロック中の最後の値と第２のブロック中の最後の値とを比較する。当該比較は、ステップ６０８において既に行われている場合には、その結果を利用しうる。
【０１１４】
ステップ６１２では、コンピュータ（１０１）は、上記最後の値同士の比較の結果、ステップ６０７において取り出された第１のブロック中の最後の値と第２のブロック中の最後の値とのうち小さい値を有する方のブロック中の入力データ列から、次のブロックを取り出す。すなわち、コンピュータ（１０１）は、第１のブロック中の最後の値が第２のブロック中の最後の値よりも小さい場合には、当該第１のブロックの次のブロック（サイズＢ１である）を第１の入力データ列から取り出し、第２のブロック中の最後の値が第１のブロック中の最後の値よりも小さい場合には、当該第２のブロックの次のブロック（サイズＢ２である）を第２の入力データ列から取り出す。代替的には、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列それぞれがサイズＢ１及びサイズＢ２に予め分割されている場合において、第１のブロック中の最後の値が第２のブロック中の最後の値よりも小さい場合には、当該第１のブロックの次に位置する分割されたブロック（サイズＢ１である）をメモリ（１０３）から取り出し、第２のブロック中の最後の値が第１のブロック中の最後の値よりも小さい場合には、当該第２のブロックの次に位置する分割されたブロック（サイズＢ２である）をメモリ（１０３）から取り出す。また、コンピュータ（１０１）は、上記最後の値同士の比較の結果、ステップ６０７において取り出された第１のブロック中の最後の値と第２のブロック中の最後の値とが同じ場合には、第１の入力データ列及び第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す。代替的には、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列それぞれがサイズＢ１及びサイズＢ２に予め分割されている場合には、当該第１のブロックの次に位置する分割されたブロック（サイズＢ１である）及び当該第２のブロックの次に位置する分割されたブロック（サイズＢ２である）をそれぞれメモリ（１０３）から取り出す。
【０１１５】
ステップ６１３では、コンピュータ（１０１）は、ステップ６０７又はステップ６１２で取り出された第１のブロック中の各値とステップ６０７又はステップ６１２で取り出された第２のブロック中の各値との組み合わせを比較する。当該組み合わせの比較は、第１及び第２の各ブロック中の各値同士の全ての比較を行うが、比較の途中でそれ以降の比較において値同士が一致しないことが予め判る場合ないしは明白な場合には、それ以降の比較を中止してよい（例えば、図３Ｂのステップ３０３を参照）。
【０１１６】
ステップ６１４では、コンピュータ（１０１）は、ステップ６１３における比較において一致した値があるか否かを判断する。コンピュータ（１０１）は、一致した値があることに応じて、処理をステップ６１５に進める。一方、コンピュータ（１０１）は、一致した値がないことに応じて、処理をステップ６１６に進める。
【０１１７】
ステップ６１５では、コンピュータ（１０１）は、一致した値があることに応じて、当該一致した値を出力データとして出力する。コンピュータ（１０１）は、出力データを例えば、ＣＰＵ（１０２）内のレジスタ内に格納する。
【０１１８】
ステップ６１６では、コンピュータ（１０１）は、一致した値がないことに応じて、現在処理中の第１のブロック中の最後の値と現在処理中の第２のブロック中の最後の値とを比較する。当該比較は、ステップ６１３において既に行われている場合には、その結果を利用しうる。
【０１１９】
ステップ６１７では、コンピュータ（１０１）は、本発明に従う共通集合演算の処理を終了するかどうかを判断する。当該判断の基準は例えば、以下の通りである：
・入力データ列の値の所定数を処理した場合；
・出力データ数が一定の数に達した場合。
コンピュータ（１０１）は、上記処理を終了しないことに応じて、処理をステップ６１８に進める。一方、コンピュータ（１０１）は、上記処理を終了することに応じて、処理を終了ステップ６２０に進める。
【０１２０】
ステップ６１８では、コンピュータ（１０１）は、ブロック・サイズを変更するかどうかを判断する。当該判断の基準は例えば、以下の通りである：
・特性が入力データ列のデータ数である場合において、
第１の入力データ列のデータ数が所定数以上であり且つ第２の入力データ列のデータ数が当該所定数よりも小さい場合；
第２の入力データ列のデータ数が所定数以上であり且つ第１の入力データ列のデータ数が当該所定数よりも小さい場合；
・特性が入力データ列中の次に取り出されるブロックの最初の値から最後の値までの隣接する各値間の差の平均値である場合であって、
第１の入力データ列の平均値（Ａｄ）と第２の入力データ列の平均値（Ａｄ）との比率又は差が第１の閾値を超える場合において、
第１の入力データ列の上記平均値が第２の入力データ列の上記平均値よりも小さい場合；
第２の入力データ列の上記平均値が第１の入力データ列の上記平均値よりも小さい場合；
・特性が入力データ列のデータ数に対する出力した値の個数の比率である場合において、
第１の入力データ列の比率が第３の閾値を超え且つ第２の入力データ列の上記比率が第３の閾値を超えない場合；
第２の入力データ列の比率が第３の閾値を超え且つ第１の入力データ列の上記比率が第３の閾値を超えない場合。
コンピュータ（１０１）は、ブロック・サイズを変更することに応じて、処理をステップ６１９に進める。一方、コンピュータ（１０１）は、ブロック・サイズを変更しないことに応じて、処理をステップ６１２に戻す。
【０１２１】
ステップ６１９のブロック・サイズを変更するサブ・フローチャートの詳細は、下記図６Ｃの説明において述べる。
【０１２２】
ステップ６２０では、コンピュータ（１０１）は、本発明に従う共通集合演算の処理を終了する。
【０１２３】
（図６Ｃを参照されたい）
【０１２４】
ステップ６２１では、コンピュータ（１０１）は、ブロック・サイズを変更する処理を開始する。
【０１２５】
ステップ６２２では、コンピュータ（１０１）は、入力データ列のデータ数又は入力データ列の値の分布などのどの特性を求めるかを読み取る。どの特性を求めるかは例えば、予めユーザによって例えば共通集合演算の処理のためのプログラム中に記述されている。
【０１２６】
ステップ６２３では、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列についての上記読み取った各特性を求める。
【０１２７】
ステップ６２４では、コンピュータ（１０１）は、ステップ６２３で求められた各特性に応じて、第１の入力データ列及び／又は第２の入力データ列それぞれのブロック・サイズＢ１及び／又はブロック・サイズＢ２を求める。例えば下記の通りである：
・特性が入力データ列のデータ数である場合、
第１の入力データ列のデータ数が所定数以上であり且つ第２の入力データ列のデータ数が当該所定数よりも小さい場合には、サイズＢ１はサイズＢ２よりも大きく、
第２の入力データ列のデータ数が所定数以上であり且つ第１の入力データ列のデータ数が当該所定数よりも小さい場合には、サイズＢ２はサイズＢ１よりも大きい；
・特性が入力データ列中の次に取り出されるブロックの最初の値から当該入力データ列の最後の値までの隣接する各値間の差の平均値である場合、
第１の入力データ列の平均値（Ａｄ）と第２の入力データ列の平均値（Ａｄ）との比率又は差が第２の閾値を超える場合において、
第１の入力データ列の上記平均値（Ａｄ）が第２の入力データ列の上記平均値（Ａｄ）よりも小さい場合には、サイズＢ１はサイズＢ２よりも大きく、
第２の入力データ列の上記平均値（Ａｄ）が第１の入力データ列の上記平均値（Ａｄ）よりも小さい場合には、サイズＢ２はサイズＢ１よりも大きい；
・特性が入力データ列のデータ数に対する上記出力した値の個数の比率である場合、
第１の入力データ列の上記比率が第３の閾値を超え且つ第２の入力データ列の上記比率が第３の閾値を超えない場合において、サイズＢ１はＢ２よりも大きく、
第２の入力データ列の上記比率が第３の閾値を超え且つ第１の入力データ列の上記比率が第３の閾値を超えない場合において、サイズＢ２はＢ１よりも大きい。
【０１２８】
ステップ６２５では、コンピュータ（１０１）は、ステップ６２４で決定したサイズＢ１及び／又はＢ２それぞれを、現在のサイズＢ１及び／又はＢ２と置き換える。コンピュータ（１０１）は、ステップ６１２において当該置き換えられたサイズＢ１及び／又はサイズＢ２で、最後の各値のうち小さい値を有するブロックの入力データ列から当該ブロックの次のブロックを取り出す。または、コンピュータ（１０１）は、最後の各値が同じ場合には、ステップ６１２において当該置き換えられたサイズＢ１及び／又はサイズＢ２で、第１の入力データ列及び第２の入力データ列それぞれから当該ブロックの次のブロックを取り出す。
【０１２９】
ステップ６２６では、コンピュータ（１０１）は、ブロック・サイズを変更する処理を終了し、ステップ６１２に戻る。
【０１３０】
ステップ６１２では、コンピュータ（１０１）は、ステップ６１６における上記最後の値同士の比較の結果、第１のブロック中の最後の値と第２のブロック中の最後の値とのうち小さい値を有する方のブロック中の入力データ列から、次のブロックを取り出す。代替的には、コンピュータ（１０１）は、第１の入力データ列及び第２の入力データ列それぞれがサイズＢ１及びサイズＢ２に予め分割されている場合において、第１のブロック中の最後の値が第２のブロック中の最後の値よりも小さい場合には、当該第１のブロックの次に位置する分割されたブロック（サイズＢ１である）をメモリ（１０３）から取り出し、第２のブロック中の最後の値が第１のブロック中の最後の値よりも小さい場合には、当該第２のブロックの次に位置する分割されたブロック（サイズＢ２である）をメモリ（１０３）から取り出す。また、コンピュータ（１０１）は、ステップ６１６における上記最後の値同士の比較の結果、第１のブロック中の最後の値と第２のブロック中の最後の値とが同じ場合には、第１の入力データ列及び第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す。が同じ場合には、第１の入力データ列及び第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す。
【０１３１】
引き続き、コンピュータ（１０１）は、上記で既に説明したステップ６１３以降の処理を行う。
【０１３２】
図７Ａは、本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価の結果を示す。
図７Ａの性能評価の条件は下記の通りである：
ＣＰＵ：ＰＯＷＥＲ７（ＩＢＭ（登録商標）社製）
コンパイラ：gcc-4.6.3
ＯＳ：ＩＢＭ（登録商標）  AIX（登録商標）  7.1
入力データ列：乱数で生成された100k個の64-bit integer配列である２つの入力データ列（当該２つの入力データ列間で、773個の値が一致する）
なお、ＣＰＵ依存の特殊な命令は使用していない。また、共通集合演算処理中において、ブロック・サイズの変更は行っていない。
【０１３３】
また、図７Ａの性能評価で使用した共通集合演算処理の方法は下記の５種類である。
１．図１０Ａ及び図１０Ｂに示したナイーブ・アルゴリズム
２．本発明の実施態様に従う共通集合演算処理（Ｂ１＝２，Ｂ２＝２）（以下、単に「Ｂ＝２」と示す）
３．本発明の実施態様に従う共通集合演算処理（Ｂ１＝３，Ｂ２＝３）（以下、単に「Ｂ＝３」と示す）
４．本発明の実施態様に従う共通集合演算処理（Ｂ１＝４，Ｂ２＝４）（以下、単に「Ｂ＝４」と示す）
５．Ｃ＋＋の標準ライブラリに含まれるstd::set_intersection（以下、単に「ＳＴＬ」と示す）；なお、set_intersectionは、２つの集合の一致する要素を出力するアルゴリズムである。
【０１３４】
グラフ７０１は、１個の値を処理するのに必要な命令数を示す。
１個の値を処理するのに命令数が少ないほど、性能はよい。すなわち、命令数が増えることは、性能向上の観点からはデメリットである。
本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）において、ブロック・サイズが増えるにつれて、命令数が増えている。本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）のいずれにおいても、ナイーブ・アルゴリズム及びＳＴＬに比べて命令数が多い。
【０１３５】
グラフ７０２は、１個の値を処理するのに生じる分岐予測ミスの数を示す。
分岐予測ミスの数が減るほど、性能はよい。すなわち、分岐予測ミスが増えることは、性能向上の観点からはデメリットである。
本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）において、ブロック・サイズが増えるにつれて、分岐予測ミスの数が減っている。本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）のいずれにおいても、ナイーブ・アルゴリズム及びＳＴＬに比べて分岐予測ミスの数が低い。
【０１３６】
グラフ７０３は、上記５種類の場合における単位時間当たりにおいて何個の値が処理できたかを示すスループットを示す。
本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）中、Ｂ＝３において性能が最大になった。本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）の性能はいずれも、ナイーブ・アルゴリズム及びＳＴＬの各性能よりも高い。本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約２．２倍高く、且つ、ＳＴＬの性能よりも約２倍高い。
【０１３７】
グラフ７０１〜７０３から、本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）のいずれにおいても命令数は増えるけれども、分岐予測ミスが減る結果として、ナイーブ・アルゴリズム及びＳＴＬに比べて性能向上が認められた。
【０１３８】
図７Ｂは、本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における異なるＣＰＵ上での性能評価を示す。
図７Ｂのグラフ７１１の性能評価の条件は、図７Ａと同じである。
図７Ｂのグラフ７１２の性能評価の条件は下記の通りである：
ＣＰＵ：ＩＮＴＥＬ（登録商標）  Ｘｅｏｎ  Ｘ５５７０（Nehalem-EP）
コンパイラ：gcc-4.4.4
ＯＳ：ＩＢＭ（登録商標）  Redhat（登録商標） Enterprise Linux 6.0
入力データ列：図７Ａの入力データ列と同じである。
なお、ＣＰＵ依存の特殊な命令は使用していない。また、共通集合演算処理中において、ブロック・サイズの変更は行っていない。
【０１３９】
また、図７Ｂの性能評価で使用した共通集合演算処理の方法は、図７Ａにおいて示した５種類と同じである。
【０１４０】
グラフ７１１及びグラフ７１２のいずれも、上記５種類の場合における単位時間当たりにおいて何個の値が処理できたかを示すスループットを示す。
【０１４１】
グラフ７１１は、図７Ａに示すグラフ７０３と同じである。従って、グラフ７０３に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約２．２倍高く、且つ、ＳＴＬの性能よりも約２倍高い。
【０１４２】
グラフ７１２では、本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）中、（Ｂ＝３）において性能が最大になった。グラフ７１２に示す本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）の性能はいずれも、ナイーブ・アルゴリズム及びＳＴＬの各性能よりも高い。グラフ７１２に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約１．８倍高く、且つ、ＳＴＬの性能よりも約１．９倍高い。
【０１４３】
グラフ７１１及び７１２から、本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）のいずれにおいても、ＣＰＵの種類にかかわらず、ナイーブ・アルゴリズム及びＳＴＬに比べて性能向上が認められた。
【０１４４】
図７Ｃは、本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価を示す。
図７Ｃのグラフ７２１の性能評価の条件は、図７Ａと同じである。
図７Ｃのグラフ７２２の性能評価の条件は、使用した入力データ列が下記である以外は、図７Ａと同じである：
入力データ列：乱数で生成された100k個の64-bit integer配列である２つの入力データ列（当該２つの入力データ列間で、11689個の値が一致する）。
【０１４５】
グラフ７２１及びグラフ７２２のいずれも、上記５種類の場合における単位時間当たりにおいて何個の値が処理できたかを示すスループットを示す。
【０１４６】
グラフ７２１は、図７Ａに示すグラフ７０３と同じである。従って、グラフ７２１に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約２．２倍高く、且つ、ＳＴＬの性能よりも約２倍高い。
【０１４７】
グラフ７２２において、本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）中、（Ｂ＝３）において性能が最大になった。グラフ７２２に示す本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）の性能はいずれも、ナイーブ・アルゴリズム及びＳＴＬの各性能よりも高い。グラフ７２２に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約２．３倍高く、且つ、ＳＴＬの性能よりも約１．８倍高い。
【０１４８】
グラフ７２２で使用した入力データ列はグラフ７２１で使用した入力データ列に比べて、入力データ列間での一致する数がより多い。しかしながら、入力データ列の長さにかかわらず、いずれの場合であっても、本発明の実施態様（Ｂ＝２），（Ｂ＝３）及び（Ｂ＝４）の性能はいずれも、ナイーブ・アルゴリズム及びＳＴＬの各性能よりも高い。
【０１４９】
図８は、本発明の実施態様に従い及びその他の方法に従い、共通集合演算処理を行った場合における、ＣＰＵ上の性能評価を示す。
図８のグラフ８０１の性能評価の条件は、図７Ａと同じである。
図８のグラフ８０２の性能評価の条件は、使用した入力データ列が下記である以外は、図７Ａと同じである：
入力データ列１：10k個の64-bit integer配列
入力データ列２：100k個の64-bit integer配列
入力データ列１と入力データ列２との間で、154個の値が一致する。また、入力データ列２の最初の値から最後の値までの隣接する各値間の差の平均値（Ａｄ）は入力データ列２の最初の値から最後の値までの隣接する各値間の差の平均値（Ａｄ）のほぼ１０倍である。
なお、共通集合演算処理中において、ブロック・サイズの変更は行っていない。
【０１５０】
また、図８のグラフ８０２の性能評価で使用した共通集合演算処理の方法は下記の５種類である。
１．図１０Ａ及び図１０Ｂに示したナイーブ・アルゴリズム
２．図１１に示したスキップ・アルゴリズム；但し、図１１に示すアルゴリズム中、Askip=0，Bskip=4である。この各skip値は、実験的に求めた上記入力データ列１及び２に対する最適値である。
３．本発明の実施態様に従う共通集合演算処理（Ｂ１＝３，Ｂ２＝３）（以下、単に「Ｂ＝３」と示す）
４．本発明の実施態様に従う共通集合演算処理（Ｂ１＝２，Ｂ２＝４）（以下、単に「Ｂ＝２，４」と示す）
５．Ｃ＋＋の標準ライブラリに含まれるstd::set_intersection（以下、単に「ＳＴＬ」と示す）；なお、set_intersectionは、２つの集合の一致する要素を出力するアルゴリズムである。
【０１５１】
グラフ８０１は、図７Ａに示すグラフ７０３と同じである。従って、グラフ８０１に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約２．２倍高く、且つ、ＳＴＬの性能よりも約２倍高い。
【０１５２】
グラフ８０２において、本発明の実施態様（Ｂ＝３）及び（Ｂ＝２，４）中、（Ｂ＝２，４）において性能が最大になった。グラフ８０２に示す本発明の実施態様（Ｂ＝３）及び（Ｂ＝２，４）の性能はいずれも、ナイーブ・アルゴリズム、スキップ・アルゴリズム及びＳＴＬの各性能よりも高い。グラフ８０２に示す本発明の実施態様（Ｂ＝３）の性能は、ナイーブ・アルゴリズムの性能よりも約１．３倍高く、スキップ・アルゴリズムの性能よりも約１．２倍高く、且つ、ＳＴＬの性能よりも約１．４倍高い。また、グラフ８０２に示す本発明の実施態様（Ｂ＝２，４）の性能は、ナイーブ・アルゴリズムの性能よりも約１．４倍高く、スキップ・アルゴリズムの性能よりも約１．２倍高く、且つ、ＳＴＬの性能よりも約１．５倍高い。
【０１５３】
グラフ８０１に示す本発明の実施態様（Ｂ＝３）の性能は、グラフ８０２に示す本発明の実施態様（Ｂ＝３）の性能とほぼ同じであった。従って、入力データ列１及び２の間でその長さに差及び上記平均値の差があっても、ほぼ同じ性能が得られる。
【０１５４】
グラフ８０２に示す本発明の実施態様（Ｂ＝２，４）の性能はグラフ８０２に示す本発明の実施態様（Ｂ＝３）の性能よりも約１．１倍性能が高かった。従って、ブロック・サイズを適切に選択することによって、更に性能向上が図られる。
【０１５５】
図９は、図１に従うハードウェア構成を好ましくは備えており、本発明の実施態様に従うコンピュータの機能ブロック図である。
コンピュータ（９０１）は、図１に従うハードウェア構成を有しうる。
【０１５６】
コンピュータ（９０１）は、入力データ受取部（９１１）、取出部（９１２）、比較部（９１３）の各構成要素を備えている。また、コンピュータ（９０１）は、出力された一致する値を格納する出力データ格納部（９１４）、特性判断部（９１５）及び／又はブロック・サイズ変更部（９１６）の各構成要素をさらに備えていてもよい。
【０１５７】
コンピュータ（９０１）は、記憶部（９０２）からの入力データ列（第１の入力データ列、第２の入力データ列）を受け取り可能なように、当該記憶部（９０２）に接続されうる。は、コンピュータ（９０１）は記憶部（９０２）を内蔵しているか（１０８）、又は、又は、コンピュータ（２０１）外にある記憶部（９０２）に有線的に又は無線的に接続されうる。
【０１５８】
入力データ受取部（９１１）は、ソート済みの第１の入力データ列及び第２の入力データ列を受け取る。代替的には、入力データ受取部（９１１）は、第１の入力データ列及び第２の入力データ列を受け取り、コンピュータ（９０１）が、当該受け取った第１の入力データ列及び第２の入力データ列を昇順又は降順にソートしてもよい。
【０１５９】
取出部（９１２）は、特許請求の範囲に記載の第１の取出部及び第２の取出部を包含しうる。代替的には、コンピュータ（９０１）は、第１の取出部及び第２の取出部を別々に備えうる。
【０１６０】
取出部（９１２）（第１の取出部）は、上記第１の入力データ列の先頭からサイズＢ１のデータ数からなる第１のブロック及び上記第２の入力データ列の先頭からサイズＢ２のデータ数からなる第２のブロックを取り出す。但し、上記サイズＢ１及びＢ２はいずれも１以上の整数であり且つ少なくとも一方は２以上であり、及び、上記サイズＢ１は上記サイズＢ２と同じ又は異なるデータ数である。
【０１６１】
取出部（９１２）（第２の取出部）は、上記取り出された第１のブロック中の最後の値と上記取り出された第２のブロック中の最後の値とを比較して、上記最後の各値のうち小さい値を有するブロックの入力データ列から上記取り出されたブロックの次のブロックを、又は上記最後の各値が同じ場合には第１の入力データ列及び第２の入力データ列それぞれから取り出されたブロックの次のブロックを取り出す。但し、上記小さい値を有するブロックの入力データ列が上記第１の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ１であり、上記小さい数を有するブロックの入力データ列が上記第２の入力データ列の場合には上記次のブロックのサイズは上記サイズＢ２である。
【０１６２】
比較部（９１３）は、上記取り出された第１のブロック中の各値及び第２のブロック中の各値の組み合わせを比較して、当該比較の結果、一致する値がある場合に当該一致する値を出力する。
【０１６３】
出力データ格納部（９１４）は、比較部（９１３）によって出力された一致する値を格納する。出力データ格納部（９１４）は、出力された一致する値を出力された順に格納する。
【０１６４】
特性判断部（９１５）は、上記第１のブロック及び上記第２のブロックを取り出す前において、又は、上記繰り返す途中において少なくとも１回、上記第１の入力データ列及び上記第２の入力データ列それぞれの特性を求める。特性判断部（９１５）は、求めた特性をブロック・サイズ変更部（９１６）に渡す。
【０１６５】
ブロック・サイズ変更部（９１６）は、特性判断部（９１５）が上記第１のブロック及び上記第２のブロックを取り出す前に上記特性を求める場合に、上記第１の入力データ列の先頭から取り出される上記第１のブロックの上記サイズＢ１を上記第１の入力データ列から求められた特性に関連付けられたデータ数に変更し、又は、上記第２の入力データ列の先頭から取り出される上記第２のブロックの上記サイズＢ２を上記第２の入力データ列から求められた特性に関連付けられたデータ数に変更しうる。
【０１６６】
ブロック・サイズ変更部（９１６）は、特性判断部（９１５）が上記繰り返す途中において少なくとも１回上記特性を求める場合に、上記次のブロックの上記サイズＢ１を上記第１の入力データ列から求められた特性に関連付けられたデータ数に変更し、又は、上記次のブロックの上記サイズＢ２を上記第２の入力データ列から求められた特性に関連付けられたデータ数に変更しうる。
【０１６７】
記憶部（９０２）は、ソート済みの入力データ列（ソート済みの第１の入力データ列及びソート済みの第２の入力データ列）を格納する。代替的には、記憶部（９０２）は、ソート前の入力データ列（第１の入力データ列及び第２の入力データ列）を格納しうる。
【０１６８】
上記では、本発明の１つの実施態様として、コンピュータ（９０１）が上記各構成要素（９１１〜９１６）を備えうることを説明した。本発明の別の実施態様として、コンピュータ（９０１）の代わりに、１つ又は複数の演算処理装置（例えば、１又は複数のＣＰＵ（１０２）又は専用の１又は複数の演算処理装置）が、上記各構成要素（９１１〜９１６）を備えていてもよい。
【図１】
2014102613.tif 000003
【図２Ａ】
2014102613.tif 000004
【図２Ｂ】
2014102613.tif 000005
【図３Ａ】
2014102613.tif 000006
【図３Ｂ】
2014102613.tif 000007
【図４Ａ】
2014102613.tif 000008
【図４Ｂ】
2014102613.tif 000009
【図４Ｃ】
2014102613.tif 000010
【図４Ｄ】
2014102613.tif 000011
【図５】
2014102613.tif 000012
【図６Ａ】
2014102613.tif 000013
【図６Ｂ】
2014102613.tif 000014
【図６Ｃ】
2014102613.tif 000015
【図７Ａ】
2014102613.tif 000016
【図７Ｂ】
2014102613.tif 000017
【図７Ｃ】
2014102613.tif 000018
【図８】
2014102613.tif 000019
【図９】
2014102613.tif 000020
【図１０Ａ】
2014102613.tif 000021
【図１０Ｂ】
2014102613.tif 000022
【図１１】
2014102613.tif 000023