Можем ли мы ускорить процессорные задачи в Java?

Question

Задача, подобная нахождению факториала 2000, где использование BigInteger - задача, интенсивно использующая ЦП, есть ли способ ускорить такие процессы?

Пример: поиск 2000! Поскольку это только одна задача, я думаю, что здесь нет необходимости в потоке (поскольку выполнение этой программы или выполнение этой задачи в потоке должны выполнять такие ресурсоемкие задачи).

Я слышал, что в Java 7 появился новый параллельный механизм для сложных вычислительных задач. Итак, как мне выполнить в нем подобные вещи?

Answer 1

Факториал может быть легко разделен на две задачи с окончательным объединением. Если хотите, это какое-то сокращение карты.

Пример:

9! = (7*5*3*1) * (8*6*4*2)

Таким образом, вы можете иметь две задачи.

Это может быть обобщено на любое количество параллельных задач.

Это решение не имеет ничего общего с Java в частности, оно заключается в преобразовании "обычных" решений в параллельные.

Answer 2

Можно просто отправить запрос в WolframAlpha и получить приблизительный ответ в течение доли секунды ( хотя бы за 2000! или даже 10 000 000 000! ), что, если вам нужно только приближение для больших факториалов, вероятно, будет более чем достаточно.

Вот статья в Википедии о проблемах, связанных с вычислением крупных факториалов самостоятельно, некоторые из которых вы уже обнаружили.

Что вы действительно хотите сделать, так это попытаться сократить общий объем работы, которую необходимо выполнить. Самый простой способ сделать это - сохранить результаты в таблице и выполнить поиск. Таблица, содержащая все эти значения, может быть довольно большой, но это один из методов, если хранение не является ограничением в вашей ситуации.

Простая попытка распараллелить это не спасет вас на ЦП (если вы не вычисляете приближение, а не точное число), потому что вы выполняете тот же объем всей работы, но распределяете ее. Кроме того, распараллеливание чего-либо требует некоторых накладных расходов (межпотоковое / межпроцессное взаимодействие, распределенная память, если проблемное пространство достаточно велико, все виды вещей). В тех случаях, когда распараллеливание любого алгоритма является большой победой, это когда вы можете успешно разбить задачу на более мелкие куски и распределить эти куски достаточно эффективно, чтобы время ...

• отправить куски наружу
• рассчитать куски
• отправить результаты обратно
• объединить результаты

... менее затратно (измеряется во времени, деньгах, хранении, электричестве или какими бы то ни было вашими ограниченными ресурсами), чем делать это последовательно, и / или что оно обеспечивает некоторую ценность (время, деньги, хранение и т. Д.) сохранено ), чтобы эффективно компенсировать расходы.