时间戳

首页 > 解决方案 > 更好（更快）的算法来比较整数向量的 2 个向量？

c++ - 更好（更快）的算法来比较整数向量的 2 个向量？

问题描述

我有一组原始数据文件，每个文件有 800 万~900 万行（是的，8,000,000~9,000,000），格式如下，

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 我需要将“原始数据”文件中的每一行与“过滤器”文件中的每一行进行比较，并获得相交值，例如 raw 中的第 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;

接下来，我尝试建立一个整数零数组：

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 个过滤器要处理！！！有没有其他更好的方法来处理这个任务？谢谢。

注册表

林志峰

标签： c++arraysvectorintersection

解决方案

不确定它对您的情况有多好（很难从您的描述中理解您想要什么），但我想到了以下算法：

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

之后，仅对过滤器行中的每个数字在已排序的行上进行二进制搜索。那将是，过滤器行数O(m * log(n))在哪里。m应该是对您的一个很大的改进O(m*n)（准确地说，您还需要将所有这些复杂性乘以数据行的数量）。

另外，请注意您的 I/O，在算法更新后它可能会成为下一个瓶颈（如果您使用 iostreams，请不要忘记std::ios::sync_with_stdio(false).

推荐阅读