ナノ秒単位の時間のリストが 2 つあります。各リストには、10^12 個以上の要素を含めることができます。私の現在の実装では、両方のリストのサブセットを取得し、for ループを使用してそのサブセット内の時間を比較し、相関時間を出力してから、別のサブセットを取得します。サブセット比較ごとに、これは約で実行されます。(m*n) ここで、m はリスト 1 サブセットのサイズ、n はリスト 2 サブセットのサイズです。これは明らかに悪いアルゴリズムです。
また、データ セットの合計時間よりも小さいクロックを使用しているため、特定の時間に関係するデータにロールオーバーがあります。
リスト 1 には特定のイベントがあり、リスト 2 には二次的なイベントがあります。一次イベントから一定時間内に二次イベントが発生したかどうかを知りたいです。ノイズも多いため、相関する時間のヒストグラムを作成し、統計的に有意な信号がある時間を探す必要があります。
両方のリストの時間を検索し、ウィンドウ内にあるアイテムを出力するために、オープン ソース ライブラリから C++ で使用できる既知の効率的なアルゴリズム、または実装できる効率的なアルゴリズムがあるかどうかを知りたい.
ブルート フォース機能の例を次に示します。
int correlate_lists( int window )
{
for( int i = 0 ; i < list1.size() ; i++ )
{
for( int j = 0 ; j < list2.size() ; j++ )
{
if( list2[j].time() > list1[i].time() && (list2[j].time() - list1[j].time()) < window )
{
printf("Time: %d\n, list2[j].time() - list[1].time() );
}
}
}
}