更好(更快)的算法来比较整数向量的2个向量？

Question

我有一套原始数据文件，每个文件有800万~900万行(是的，800万~900万行)，格式如下：

1,2,3,4,5,16,23,35
1,2,3,4,6,17,23,36
1,2,3,4,7,18,23,37
1,2,3,4,8,19,23,38
1,2,3,4,9,20,23,39
1,2,3,4,10,21,23,40
1,2,3,4,11,22,23,41
1,2,3,4,12,23,24,42
1,2,3,4,13,24,25,43
1,2,3,4,14,25,26,44

每行有8个排序的数字，范围从1到49。另一组“过滤器”文件，每一个都有600万~700万行，格式如下，

13,4,7,8,18,20
9,10,11,12,5,6,7,8,1,2,3,4,21,22,23,24,13,14,15,16,29,30,31,32,45,46,47,48
29,49,36,37,34,17,15,9,16,30,28,47,46,27,20,32,14,26,1,4,3,6,10,2,7,48,44,41

每一行有4~28个未排序的数字，范围为1~49。我需要将“原始数据”文件中的每一行与“过滤”文件中的每一行进行比较，得到交叉值，例如原始数据中的第1行与过滤器中的第1~3行。

1  // since only 4 is in common with filter line 1
7  // since only 35 not found in filter line 2
6  // since 5 23 35 not found in filter line 3    

比较后，将根据阈值输出结果。例如：

output raw data line with intersection value >= 2,
output raw data line with intersection value == 4

我知道(最多)有900万x 800万行比较。首先，我尝试使用set_intersection来完成这项工作，但这需要花费很长时间(在传递给set_intersection之前对筛选器行进行排序)。

int res[8];
int *it = set_intersection(Raw.Data, Raw.Data+8, FilterVal.begin(), FilterVal.end(), res);
ds = GetIntersect(GDE.DrawRes, LotArr) * 2;
int IntersectCnt=it-res;

接下来，我尝试构建一个整数为0的数组：

int ResArr[49] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

并使用3个辅助函数：

void InitResArr(int * inResArr, vector<int> & FilterVal) {
    for (int i = 0; i < FilterVal.size(); i++) {
        inResArr[FilterVal[i] - 1] = 1;
    }
}
void ResetResArr(int * inResArr, vector<int> & FilterVal) {
    for (int i = 0; i < FilterVal.size(); i++) {
        inResArr[FilterVal[i] - 1] = 0;
    }
}

int GetIntersect(int * inResArr, int * inRawData) {
    int RtnVal = 0;
    for (int i = 0; i < 8; i++) {
        RtnVal+=inResArr[inRawData[i] - 1];
    }

但是这种方法仍然需要3个多小时来完成1次比较(1个原始数据文件和1个过滤器)。我有5,000个原始数据文件和40,000个过滤器！有没有其他更好的方法来处理这项任务？谢谢。

Regds

林志峰

Answer 1

不确定它对你的情况有多好(很难理解你想从你的描述中得到什么)，但我已经想到了以下算法：

对长行进行排序。这可以通过简单的计数在O(n)中完成，其中n是单个数据行的长度。

之后，对于筛选行中的每个数字，在排序的行上执行二进制搜索。这将是O(m * log(n))，其中m是过滤器的行数。与O(m*n)相比应该是一个很大的改进(准确地说，您还需要将所有这些复杂性乘以数据行数)。

另外，注意你的I/O，在algo更新后，它可能成为下一个瓶颈(如果你正在使用iostreams，不要忘记std::ios::sync_with_stdio(false)。