Параллельное Подмножество

Question

Настройка: у меня есть два массива, которые не отсортированы и не имеют одинаковую длину.Я хочу посмотреть, является ли один из массивов подмножеством другого.Каждый массив является набором в том смысле, что нет дубликатов.

Прямо сейчас я делаю это последовательно грубой силой, поэтому это не очень быстро.В настоящее время я делаю этот метод подмножества последовательно.У меня были проблемы с поиском каких-либо алгоритмов онлайн, которые A) работают быстрее и B) работают параллельно.Скажем, максимальный размер любого массива равен N, а сейчас он масштабируется как N ^ 2.Я думал, может быть, если бы я отсортировал их и сделал что-то умное, я мог бы свести это к чему-то вроде Nlog (N), но не уверен.

Главное, я понятия не имею, как распараллелить эту операцию вообще.Я мог бы просто сделать что-то похожее на то, что каждый процессор смотрит на равное количество первого массива и сравнивает эти записи со всем вторым массивом, но я все равно выполняю работу N ^ 2.Но я думаю, что будет лучше, так как он будет работать параллельно.

Есть идеи о том, как улучшить работу и сделать ее параллельной одновременно?

Спасибо

Answer 1

Предположим, вы пытаетесь решить, является ли A подмножеством B, и пусть len (A) = m и len (B) = n.

Если m намного меньше n, тогда для меня имеет смысл отсортировать A, а затем выполнить итерацию по B, выполняя двоичный поиск для каждого элемента на A, чтобы увидеть, есть ли совпадение или нет. Вы можете разделить B на k частей и сделать так, чтобы каждый поток выполнял двоичный поиск.

Для подсчета совпадений вы можете сделать 2 вещи. Либо вы могли бы увеличивать переменную num_matched каждый раз, когда находите совпадение (хотя вам нужно было бы защитить эту переменную, используя мьютекс, что может помешать параллелизму вашей программы), а затем проверить, если num_matched == m в конце программы. Или вы могли бы иметь другой массив или битовый вектор размером m и иметь поток, обновляющий k-й бит, если он нашел соответствие для k-го элемента A. Затем, в конце, вы убедитесь, что этот массив - все 1 , (На втором этапе битовый вектор может не работать без мьютекса, потому что потоки могут перезаписывать аннотации друг друга, когда загружают целое число, содержащее соответствующий им бит). Подход массива, по крайней мере, не нуждался бы в мьютексе, который может препятствовать параллелизму.

Сортировка обойдется вам в млог (м), а затем, если у вас есть только один поток, выполняющий сопоставление, это будет стоить вам nLog (м). Так что, если n намного больше, чем m, это будет nLog (m). Ваш худший случай все еще остается NLog (N), но я думаю, что параллелизм действительно очень помог бы вам сделать это быстро.

Резюме: просто отсортируйте меньший массив.

В качестве альтернативы, если вы хотите рассмотреть возможность преобразования A в HashSet (или любую эквивалентную структуру данных Set, которая использует некоторый тип хеширования + зондирования / цепочки для получения O (1) поисков), тогда вы можете выполнить одну проверку членства в просто O (1) (в амортизированном времени), так что вы можете сделать это за O (n) + стоимость преобразования A в набор.