W14 ➡️ Имя и Фамилия ⬅️
Обычный однопоточный алгоритм поиска минимума в массиве может выглядеть так:
int min(int[] a) {
int r = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
if (a[i] < r) {
r = a[i];
}
}
return r;
}Необходимо реализовать такой алгоритм, который будет использовать не один поток (не одно ядро процессора, а сразу все).
Подход, который можно предложить для "распараллеливания" будет следующий:
Пусть нам дан массив длины N = 10, а также у нас есть M = 3 потоков.
Мысленно разделим массив на N / M частей
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | поток 1 | поток 2 | поток 3 <== |Обратите внимание, что последнему потоку пришлось взять на себя остаток
Каждый поток найдет минимум в своем подмассиве, а затем мы найдем минимум среди этих минимумов
| 3 | 5 | 4 | 2 | 0 | 9 | 7 | 7 | 3 | 7 | | поток 1 | поток 2 | поток 3 <== | | min = 3 | min = 0 | min = 3 | | min среди {3,0,3} == 0 | | ответ - 0 |
Чтобы запустить тесты:
- на Linux/macOS:
./gradlew test - на Windows:
gradlew test - в IntelliJ: запустите класс
MinTest
Воспользуйтесь методом MinTest.main и запустите анализ времени работы методов в наносекундах.
Вы можете менять точки (количество элементов массива), для которых будет произведен тестовый замер времени.
На листочке, в Paint или в Excel постройте графики f(x), где x - количество элементов в массиве, а f(x) - время исполнения алгоритма для:
- классического однопоточного алгоритма
- многопоточного алгоритма
Ваши графики на одной плоскости здесь. Не забудьте добавить файл в репозиторий (когда будете делать commit, нужно убедиться, что он выбран)
На каких интервалах многопоточный алгоритм работает быстрее?
Чем можно объяснить длительность выполнения многопоточного алгоритма?
Когда нужно предпочесть классические алгоритмы многопоточным?
Ваш Ответ Здесь