Лучший (более быстрый) алгоритм для сравнения 2 вектора вектора целого числа? - PullRequest
Новая
       19

Лучший (более быстрый) алгоритм для сравнения 2 вектора вектора целого числа?

0 голосов
/ 03 мая 2018

У меня есть 1 набор файлов необработанных данных, каждый из которых содержит 8 миллионов ~ 9 миллионов строк (да, 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. Каждый набор файлов «фильтра» содержит по 6–7 миллионов строк следующий формат, 

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

Я знал, что есть (максимум) 9 миллионов x 8 миллионов сравнений строк. Сначала я пытаюсь использовать 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 фильтром). И у меня есть 5000 файлов с необработанными данными и 40000 фильтров! Есть ли другой лучший подход для решения этой задачи? Спасибо.

Regds

LAM Chi-fung

1 Ответ

0 голосов
/ 03 мая 2018

Не уверен, насколько хорошо это будет работать для вашего случая (было трудно понять, что вы хотели из вашего описания), но я подумал о следующем алгоритме:

Сортировка длинных рядов. Это можно сделать в O(n), где n - длина отдельной строки данных простым подсчетом.

После этого только для каждого числа в строке фильтра выполните двоичный поиск в отсортированной строке. Это будет O(m * log(n)), где m - количество строк фильтра. Должно быть большим улучшением по сравнению с O(m*n) (вам необходимо умножить все эти сложности на количество строк данных, если быть точным).

Кроме того, обратите внимание на ваш ввод-вывод, после обновления алгоритма он может стать следующим узким местом (если вы используете iostreams, не забудьте std::ios::sync_with_stdio(false).

...