Поиск минимального значения в отсортированном массиве, который был повернут, с использованием параллелизма
Это вопрос для интервью.
В первой части меня попросили найти минимальное значение в отсортированном массиве, который был повернут (например, отсортированный массив [1,2,3,4] был повернут на [3,4,1,2]).
Алгоритм этого можно найти здесь.
Затем меня попросили улучшить алгоритм с помощью параллельных вычислений. Это было мое предложение:
- Предполагая, что мы можем запускать потоки
kпараллельно, разделите массив на подмассивыkравного размера (кроме, возможно, последней части). - Выполните описанный выше алгоритм для каждого из подмассивов
k. - Вернуть минимальное значение из запущенного алгоритма
k.
Интервьюер сказал, что время выполнения алгоритма недостаточно велико. Вы знаете лучшее решение?
@NicoSchertler, ваш анализ предполагает, что решение должно использовать результаты всех k потоков. См. Мой ответ, который показывает, почему это не требуется и как улучшить время O (n).
Ответы 1
Предположим, у вас есть аппаратные потоки п + 1. Вы можете заставить потоки п обрабатывать массив, каждый поток «отвечает» за 1 запись и завершается за время O (1), а оставшийся поток ожидает результата. Для эффективности потоки следует запускать заранее и инициализировать индексной переменной (я), в противном случае сама инициализация займет время O (n). Процесс в каждом потоке может быть:
if arr[i] > arr[(i + 1) mod n]
SharedMemResult = arr[(i + 1) mod n]
Очевидно, что это время O (1), и все, что должен был сделать «главный» поток, - это читать SharedMemResult до тех пор, пока он не изменится (конечно, это должно быть инициализировано некоторым экстремальным значением, и следует использовать барьеры памяти, чтобы предотвратить переупорядочение ... ).
Используя ту же концепцию, мы могли бы использовать потоки
Результатом является алгоритм, который решает проблему за время O (log (n / m)).
Я не полностью понял ваш алгоритм, но я все еще думаю, что с ним есть проблема: вы забыли, что мы должны инициализировать эти m потоков, что означает, что этот алгоритм работает за O (log (n / m) + m) = O (logn - logm + m), и это не лучше, чем однопоточный алгоритм (как написал @Nico Schertler)
@John - Я этого не забыл ... На самом деле, я специально сказал: «потоки должны быть запущены заранее и инициализированы индексной переменной ...». Это похоже на пул потоков, который вы готовите один раз и используете при каждом выполнении алгоритма. Что вы не поняли в алгоритме?
У меня нет решения, но у меня есть причины. Время выполнения вашего алгоритма -
O(log n). Если вы разделите массив на частиk, вы получитеO(log (n/k)), и вам нужно будет найти минимальный элемент из результатовk. При линейном поиске это даст вамO(log(n/k) + k) = O(log n - log k + k). Посколькуlog kобычно меньшеk, вы, скорее всего, сделали его хуже. Фактически, почти все потоки (кроме одного) немедленно возвращают первый элемент как минимум и переходят в спящий режим. Ответ может заключаться в том, чтобы оставить его однопоточным.