@kategg

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

Есть ли возможность сравнить два массива не целиком, а по частям, допустим, пачками по 500-1000 элементов? Под сравнить я имею ввиду, что есть 2 массива. В каждом массиве около 100.000 элементов, необходимо получить результирующий массив со значениями, которые есть в первом массиве, но нет во втором, т.е. функционал array_diff. Массивы отсортированы.
  • Вопрос задан
  • 210 просмотров
Пригласить эксперта
Ответы на вопрос 2
trapwalker
@trapwalker
Программист, энтузиаст
А зачем вам это делать частями? Что вы хотите этим добиться?
Ваша задача имеет сложность О(N) и не представляет никакой сложности, просто двигайтесь двумя курсорами синхронно по массивам и всё.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Можно и по частям. Какой там алгоритм сравнения, если все сразу известно? Два указателя, по одному в каждом массиве. Выкидываем меньшее число из двух - оно уникальное в своем массиве. Если два числа равны - вы нашли совпадение и двигайте оба.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы