Сравнение двух разделенных списков данных параллельно - PullRequest
Новая
       27

Сравнение двух разделенных списков данных параллельно

0 голосов
/ 26 июня 2019

Проблема как указано:

Найдите несоответствия между двумя отчетами об объектных ключах, которые должны быть резервными копиями друг друга.

Отчеты разбиты на несколько файлов .csv:

Отчет A может содержать 50 файлов, а отчет B - 20, хотя оба отчета должны содержать одинаковое количество ключей объекта.

Ключи объектов в каждом отчете расположены в алфавитно-цифровом порядке.

Размеры файлов .csv ненадежны, поэтому мы могли видеть упомянутое выше разделение 50/20.

Предположим, что файлы расположены по порядку: если file1 из отчета A содержит a-c, то file2 подхватит d.

Пример данных (где каждый массив представляет собой отдельный файл, а содержащий массив - это отчет в целом): 

 report1 =  [
    [1, 2],
    [3, 4, 5, 6],
    [7],
    [8, 9],
    [10],
 ]
 report2 = [
    [1, 2, 3, 4, 5],
    [6, 7, 8, 9, 10],
 ]

Имейте в виду, что эти данные НЕ хранятся в памяти, я просто имею доступ к указателям файлов, связанным с каждым массивом (файлом), которые могут выполнять итерацию вперед, а не назад.

Первоначальный алгоритм состоял в том, чтобы обрабатывать их как два больших списка и изменять считыватели файлов, когда один из них заканчивается, а затем выполнять итерации в то же время, делая сравнения. Предположим, что смена файлов уже началась. Псевдо-код: 

while (not end of report1) and (not end of report2)
   if key1 < key2
      // key1 missing from report2
      move up reader1
   else if key2 < key1
      // key2 missing from report1
      move up reader2
   else
      // keys match and are in both reports
      move up reader1 and reader2

Это было слишком медленно. Мне нужно работать с миллиардами объектных ключей.

Я решил распараллелить сравнение файлов по отдельности, используя тот же алгоритм сравнения:

Первый файл Report1 и первый файл Report2 сравниваются одновременно с обоими их вторыми файлами и т. Д.

Очевидно, что это приведет к множеству ложноположительных расхождений из-за различий в размерах файлов, но я снова запускаю алгоритм сравнения для ВСЕХ найденных расхождений в конце процессов.

Это ускорило многое. Однако 95% всех расхождений, обнаруженных во время мультиобработки, были ложноположительными, опять же из-за ужасной ненадежности этих размеров файлов. Помните, что 50/20 раскол? Если мы дойдем до файла 21 из отчета 1, то из отчета 2 файла 21 не будет, поэтому ВСЕ эти элементы помечены как несоответствия.

Большинство работ по сравнению НЕ ДОЛЖНЫ выполняться при окончательном сравнении. В идеале это должно быть сделано в параллельном процессе.

Хорошо, теперь мой вопрос:

Какими способами я мог бы распараллелить эти сравнения? Я хотел бы использовать как можно меньше памяти и значительно уменьшить это число ложных срабатываний на 95%.

...