Какой хороший алгоритм для поиска в массивах N и M, чтобы найти элементы в N, которые также существуют в M?

Question

У меня есть два массива, N и M. Они оба имеют произвольный размер, хотя N обычно меньше, чем M. Я хочу выяснить, какие элементы из N также существуют в M, как можно быстрее.

Чтобы дать вам пример одного возможного экземпляра программы, N - это массив размером 12 единиц, а M - это массив размером 1000 единиц.Я хочу выяснить, какие элементы в N также существуют в M. (Возможно, совпадений не будет.) Чем более параллельное решение, тем лучше.

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

Набирая это, я просто подумал о запуске бинарного поиска M в независимых по размеру (N) потоках.(Используя CUDA) Я посмотрю, как это работает, хотя приветствуются и другие предложения.

Answer 1

Просто отсортируйте N. Затем для каждого элемента M выполните его двоичный поиск по отсортированному N. Поиск элементов M в N тривиально параллельно, даже если вы выполняете линейный поиск по несортированному N размера 12.

Answer 2

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

Простым решением вашей проблемы является использование хеш-соединения.Создайте хеш-таблицу из M, затем найдите в ней элементы N (или наоборот; поскольку оба ваших массива малы, это не имеет большого значения).

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

Если вы хотите реализовать параллельное хеш-соединение, это не составит труда.Начните с создания хеш-таблиц X-1, где X - это количество потоков / процессоров, которые у вас есть.Используйте вторую хеш-функцию, которая возвращает значение по модулю X-1, чтобы определить, в какой хеш-таблице должен быть каждый элемент.

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