在C++中比較兩個大型數據列表的有效算法是什麼？

Question

我有兩個時間列表（納秒）。每個列表可以有10^12個元素或更多。我目前的實現是獲取這兩個列表的一個子集，使用for循環比較該子集中的時間並輸出相關時間，然後獲取另一個子集。對於每個子集的比較，這個運行時間約爲（m * n）其中m是列表1子集的大小，n是列表2子集的大小，這顯然是一個不好的算法。

我也有一個時鐘比我的數據集的總時間更小，所以有數據翻車要在特定的時間與相關。

表1有一定的活動，並列表中有兩個具有次要事件。我想知道次要事件是否在主要事件發生的特定時間內發生。還有很多噪音，所以我需要創建一個相關時間的直方圖，並尋找有統計意義的信號的時間。

我想知道是否有一個已知的高效算法，可以在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()); 
     } 
    } 
    } 
} 

Answer 1

如果兩個列表按時間排序，您可以通過列表有效地走路：

for(int i = 0, j = 0 ; i < list1.size() ; ++i) 
    { 
    while(j < list2.size() && list2[j].time() <= list1[i].time()) 
    { 
     ++j; 
    } 

    int k = j; 

    while(k < list2.size() && list2[k].time() < list1[i].time() + window) 
    { 
     printf("Time: %d\n, list2[k].time() - list1[i].time()); 
     ++k; 
    } 
    } 

Answer 2

如果列表進行排序，當然你可以使用二進制搜索來查找「窗口」的位置？