Вы должны будете проверить, лучше ли производительность наличия переменной синхронизации, которая сообщает циклам завершаться раньше, чем просто позволить потокам проходить через подмножество массива и возвращаться, если они что-то находят.Если у вас нет атомарного bool без блокировки, тогда запуск потоков до конца подмножества и последующая синхронизация, вероятно, будут быстрее.
Сам алгоритм довольно прост, вам просто нужно убедиться, что выобрабатывать угловой корпус.Допустим, ваш набор данных
1, 2, 3, 4, 4, 6, 7, 8
и вы разбили его на 4 четных потока.Потоки получат
thread 1: 1, 2
thread 2: 3, 4
thread 3: 4, 6
thread 4: 7, 8
, и каждый поток не найдет дубликат, так как дублирующиеся записи охватывают два разных потока.Это означает, что каждый поток должен иметь подмножество, которое перекрывает другие подмножества элементом, чтобы вы могли найти дубликат.Это означает, что потоки должны быть действительно выложены как
thread 1: 1, 2, 3
thread 2: 3, 4, 4
thread 3: 4, 6, 7
thread 4: 7, 8 // the last thread does need to overlap anything
Имея это, вы можете проходить через каждую подгруппу, проверяя линейно a[i] == a[i+1], и вы гарантированно найдете дубликат, если таковой существует.
Вам не нужно беспокоиться о синхронизации операции чтения содержимого вектора.Пока вектор не изменяется, пока вы проверяете его, хорошо, чтобы несколько читателей читали с него одновременно.Синхронизация необходима только в том случае, если у вас есть несколько потоков, и один или несколько из этих потоков записывают общие данные.