Можно ли сравнить большие массивы по частям?

Question

[kategg]

Есть ли возможность сравнить два массива не целиком, а по частям, допустим, пачками по 500-1000 элементов? Под сравнить я имею ввиду, что есть 2 массива. В каждом массиве около 100.000 элементов, необходимо получить результирующий массив со значениями, которые есть в первом массиве, но нет во втором, т.е. функционал array_diff. Массивы отсортированы.

Comments

[alexalexes]

Если оба источника массива берутся из базы SQL, то нужно мучить SQL оператором join/left join/cross join/full join/вычитанием выборок, не нужно доставать 100 тыс. элементов в php - это не его работа. СУБД при правильном запросе выполнит эту задачу эффективнее всего.

[kategg]

alexalexes, если бы все так и было) Первый источник массива - это БД, второй - это api, которое за один запрос возвращает 100 элементов (пагинация). Следовательно, в БД надо добавить недостающие элементы и получить все записи, которых нет в приходящих от api массиве (т.е. есть в БД, но нет в массиве), чтобы пройтись по ним и выполнить некие действия.
Можно, конечно, загрузить приходящие от api данные во временную таблицу и join-ами сравнить с уже имеющейся, но не знаю, насколько такой подход оптимален. Получается много запросов на добавление + очистка после завершения сравнения

[alexalexes]

А api нет условий фильтрации?
Обычно, новые записи требуются с определенного id или отметки времени. Можно сразу запрашивать новое.

Answer 1

[Сергей П]

А зачем вам это делать частями? Что вы хотите этим добиться?
Ваша задача имеет сложность О(N) и не представляет никакой сложности, просто двигайтесь двумя курсорами синхронно по массивам и всё.

Comments

[kategg]

Данные для второго массива приходят частями по 100 элементов, т.е. для получения целого массива их придется складывать. Поэтому и интересуюсь, есть ли вариант, при котором не придется держать в памяти 2 больших массива

[Lynn «Кофеман»]

kategg, с точки зрения алгоритма это вообще неважно. В каждый момент времени нужен только один элемент.

[Сергей П]

kategg, прислушайтесь, Lynn «Кофеман» прав. Если данные поступают отсортированными и в чанках, то два курсора в обоих входящих потоках находятся каждый в своём одном чанке. Не нужно ничего склеивать, просто у вас получается двухуровневый курсор: Чанк, позиция в чанке.

[Михаил Ливач]

kategg, другими словами: так, как предлагает Сергей П - можно. Делать какой-нибудь array_slice() и пихать в array_diff() - нельзя

Answer 2

[Wataru]

Можно и по частям. Какой там алгоритм сравнения, если все сразу известно? Два указателя, по одному в каждом массиве. Выкидываем меньшее число из двух - оно уникальное в своем массиве. Если два числа равны - вы нашли совпадение и двигайте оба.

Можно алгоритм поставить "на паузу". Вам надо будет хранить указатель в первом массиве между порциями второго.
Когда у вас приходят данные от второго массива, двигайте указатель в первом, пока число там меньше текущего во втором массиве. Если они равны, двигайте оба. Если число в первом больше - дивгайте указатель во втором массиве. И так пока один из массивов не кончится.

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