Неуникальный C ++ несортированный алгоритм пересечения

Question

Я пытался придумать способ написать эффективный алгоритм для выполнения несортированного пересечения двух векторов / массивов, но безуспешно.Я работаю с одним большим неуникальным массивом (обычно от 500 000 до 1 000 000 значений) и одним относительно небольшим (может быть, максимум 5000 значений) уникальным массивом.

Я видел множество предлагаемых здесь методов, включающих такие методы, как unordered_sets, но, насколько я понимаю, это не сработает, если один из массивов не является уникальным.Во-вторых, вместо того, чтобы иметь выходной вектор, который содержит числа, общие для обоих массивов, я бы хотел, чтобы выходной вектор содержал индексы этих общих значений по отношению к большему массиву.Итак, если у большого массива есть 5 местоположений, которые равны одному из значений в меньшем массиве, мне нужен каждый из этих 5 индексов.Возможно, что-то похожее на функцию Python in1d.

У кого-нибудь есть идеи?Спасибо

Answer 1

Поместите уникальную сторону в unordered_set и пройдите неуникальную сторону одну за другой. Если вы найдете элемент в non_unique_side[i] в unordered_set(unique_side), добавьте i к результату.

Предполагая, что unordered_set реализован как хеш-код с O(1) амортизированным временем вставки и поиска, этот алгоритм дает вам O(L+S) сложность времени, где L - количество элементов в большом списке, а S - количество предметов в меньшем наборе. Это так быстро, как вы можете сделать пересечение.

Answer 2

Создайте еще один вектор, который содержит все индексы из большого массива.Затем отсортируйте индексы, используя предикат, который использует один уровень косвенности, и либо сделайте то же самое для уникального массива, либо отсортируйте его на месте.Затем выполните нормальное упорядоченное пересечение, используя сравнение, которое учитывает один уровень косвенности и помещает индекс из вектора отображения в конечный результат.

Answer 3

Вы можете отобразить большой массив из его значения в int.

например: unordered_map<int,int>

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

Тогда вам просто нужно перейти на меньшее значение, и для каждого значения проверить, существует ли оно на карте. Если он существует, то добавьте количество элементов в отображаемом int в вектор результата.

поэтому, если у вас 5 шестерок, карта [6] = 5 .. поэтому просто добавьте 5 экземпляров по 6 к значению результата.

Edit:

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