Совместное использование нескольких потоков для одного процесса

Question

У меня есть факториальная программа, которую я написал в качестве теста производительности. Требуется 3 минуты, чтобы вычислить факториал 1 миллиона с помощью одного потока.Мне любопытно, можно ли выделить несколько потоков для одного и того же алгоритма, причем не одновременно, а совместно, что увеличивает скорость обработки и уменьшает время, необходимое для запуска алгоритма.Я предполагаю, что это возможно, потому что суперкомпьютеры имеют много потоков и, как правило, средние частоты процессора.

Answer 1

Как уже упоминал Алекс, эту проблему можно легко распределить по нескольким потокам.

Давайте рассмотрим однопоточную реализацию с использованием потоков Java8:

Stream<BigInteger> numbers = LongStream.rangeClosed(1, 1_000_000).mapToObj(BigInteger::valueOf);
BigInteger reduced = numbers.reduce(BigInteger.ONE, BigInteger::multiply);

Теперь давайте рассмотрим нескольковерсия того же с резьбой:

Stream<BigInteger> numbers = LongStream.rangeClosed(1, 1_000_000).mapToObj(BigInteger::valueOf);
numbers = numbers.parallel();
BigInteger reduced = numbers.reduce(BigInteger.ONE, BigInteger::multiply);

(Да, единственное отличие - numbers = numbers.parallel(); - красота потоков)

Второй - намного быстрее, чемпервый (в зависимости от количества реальных и гиперпоточных процессоров, которые у вас есть), но получает тот же результат.

---

По какой-то причине, которую я пока не могу полностью объяснить, параллельная версия - намного быстрее, чем непараллельная версия.Вероятно, это связано с использованием памяти.На моем 4-ядерном 2,5 ГГц i7 MacBook Pro для параллельной версии требуется 5,8 секунды, но непараллельная версия не завершается даже за 10 минут (на 1 миллион).

Для 100 000параллельная версия намного быстрее: 90 миллисекунд для параллельной версии 2500 миллисекунд для непараллельной (измеряется 10-я итерация после 9 итераций прогрева).

Answer 2

Очевидно, что если у вас есть k процессоры, вы можете разделить работу для n факториала на поиск продуктов [2, n * (1/k)], ... [n * ((k-1)/k) + 1, n] параллельно, чтобы получить числа P_1, ..., P_k, тогда общий факториал будет n! = P_1 * ... * P_k.