Самый эффективный способ сравнить два огромных массива объектов

Question

Я хочу сравнить два огромных массива, я читаю эти два массива партиями (получая по 10 объектов за раз из каждого массива). После завершения чтения этих двух массивов я хочу получить следующие данные (пересечение двух огромных массивов - объекты существуют только в первом массиве - объекты существуют только во втором массиве). Как лучше всего это сделать?

Пример в мелком масштабе:

let arr1 = [obj1, obj2, obj3, obj4, obj5, obj6, obj7];

let arr2 = [obj7, obj2, obj5, obj1, obj9, obj8];

Затем я буду читать два массива группами (по два элемента за раз):

Первый l oop

-> obj2 взаимно

-> obj1 существует только в arr1

-> obj7 существует только в arr2

Проблема здесь, это не окончательный результат, пока я не завершу цикл по всем массивам, чтобы получить правильный результат:

Взаимные объекты - это obj1, obj2, obj5, obj7

Объекты в arr1 только obj3, obj4, obj6

Только объекты в arr2: obj8, obj9

Примечание: я должен читать массивы группами, потому что они слишком велики.

Answer 1

Чтобы эффективно сравнивать ваши массивы, вам нужно как-то их отсортировать. Это верно независимо от того, слишком ли велики массивы для размещения в памяти.

Обычно есть два варианта: либо отсортировать объекты в каждом массиве и сравнить их по порядку, либо sh объекты в каждый массив и сравните их с картой ha sh.

Каждый метод имеет методы обработки данных, слишком больших для размещения в памяти. Для сортировки существуют «внешние» алгоритмы сортировки, не ограниченные размером памяти, и простая потоковая передача данных для сравнения. Для хеширования вы можете разделить данные (согласно ha sh) на бункеры, достаточно маленькие для обработки в памяти.

---

В качестве примера рассмотрим этот Python -подобный псевдокод для ha sh - объединение элементов данных:

// split data into bins
files = []
for i in 0 .. N-1:
    files.push_back(open_for_write("{filename}_bin{i}"))
for item in read_items(open_for_read(filename)):
    bin = item.hash() mod N
    write_item(item, files[bin])

Вы можете сделать это для обоих входных файлов, а затем обработать их по корзине:

// compare by bin
outfile = open_for_write(out_filename)
for i in 0 .. N-1:
    items = new_set()
    for item in read_items(open_for_read("{in_filename_1}_bin{i}")):
        items.insert(item)
    for item in read_items(open_for_read("{in_filename_2}_bin{i}")):
        if item in items:
            write_item(item, outfile)