Предположим, у вас есть большой несортированный массив длины n, в котором вы хотите найти определенный элемент (пусть элементы этого массива будут уникальными). Поскольку в худшем случае вам придется искать элемент по всему массиву, время выполнения составит O(n). Однако, поскольку большинство процессоров в настоящее время поддерживают несколько ядер (с гиперпоточностью), вы можете использовать несколько потоков для поиска в массиве, чтобы ускорить его. Таким образом, с m ядрами в вашем распоряжении будет 2 млн (независимых) потоков. Если вы делегируете только часть массива каждому потоку, т.е. даете каждому из 2m потоков n/2m элементов массива для обработки, это было бы оптимально. Однако, когда один из потоков 2m находит элемент, другие потоки должны быть остановлены (для сохранения системных ресурсов), поскольку все элементы уникальны, и другие потоки никогда не найдут этот элемент.
Итак, мой вопрос таков: как бы вы искали большой несортированный массив с уникальными элементами с потоками 2m, сводя к минимуму работу, выполняемую вашими потоками, и время выполнения? Какие синхронизированные структуры данных вам понадобятся? Как вы останавливаете другие потоки 2m-1, когда элемент найден?
