Факториал с использованием многопоточности

Question

Я получил кошмар на резьбе на решении факториала с использованием многопоточности я получил простую идею, как почему не мы используем метод быстрой сортировки, чтобы решить эту проблему я говорю о разделяй и властвуй ...

, например, мое объяснение в формате кода ...

, пусть если я должен найти факториал для 8 давайте ограничиться parition только 2 части

thread1 решения факториала п до п/2

8*fact(7) 
8*7*fact(6) 
8*7*6*fact(5) 
8*7*6*5*fact(4) 

thread2 вычисляет fact(4)

теперь моя проблема, я не знаю, как решить, как удалить факт (4) из thread1, так что я просто закончить мой ответ, как

result=thread1output*thread2output 

Пожалуйста, укажите код с комментариями, пожалуйста, В надежде получить от вас положительный ответ. Спасибо за то, что вы прошли до конца.

Answer 1

Обычно применимая оптимизация, когда одно вычисление зависит от результатов предыдущего вычисления, равно memoization. Вместо того, чтобы просто рекурсировать, проверьте, было ли значение уже вычислено; и если так, то возвращаемое ранее вычисленное значение. Что-то вроде,

private static Map<Integer, BigInteger> memo = new HashMap<>(); 
static { 
    memo.put(1, BigInteger.ONE); 
} 

public static BigInteger fact(int i) { 
    if (memo.containsKey(i)) { 
     return memo.get(i); 
    } 
    BigInteger result = BigInteger.valueOf(i).multiply(fact(i - 1)); 
    memo.put(i, result); 
    return result; 
} 

Answer 2

Если вы хотите атаковать факториал несколькими потоками, вам нужно разделить серию на единицы работы. При использовании двух нитей упрощенным подходом является разделение серии на 2.

Например, 8!

• нить 1 8x7x6x5
• нить 2 4x3x2x1

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

На самом деле, вы можете сделать это с помощью потока API:

long factorial = LongStream.rangeClosed(1, n).parallel().reduce((a, b) -> a * b).get(); 

Это может обработать расчет параллельно.

Для n больше 20, результат будет превышать наибольшее значение, которое может содержать long; использовать BigInteger для арифметики вместо:

BigInteger factorial = IntStream.rangeClosed(1, n) 
.parallel() 
.mapToObj(String::valueOf) 
.map(BigInteger::new) 
.reduce((a, b) -> a.multiply(b)) 
.get(); 

Answer 3

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

В простой рекурсивной разделяй и властвуй стратегии, псевдо-код

factorial(N) = 
    return factorialHelper(set_of(1, N)) 

factorialHelper(set) = 
    if set.size == 1 
     return set.first 
    else 
     let set1, set2 = split_into_subsets(set, 2) 
     return factorialHelper(set1) * factorialHelper(set2) 

Теперь мы можем наивности использовать потоки, как это:

factorialHelper(set) = 
    if set.size == 1 
     return set.first 
    else 
     let set1, set2 = split_into_subsets(set, 2) 
     return fork(lambda factorialHelper(set1)).join() * 
       fork(lambda factorialHelper(set2)).join() 

(Пояснение: fork(lambda factorialHelper(set1)).join() должно означать, что мы : - создание новой темы для расчета factorialHelper(set1), - начало темы, - ждет, пока сообщение не получено.)

В этом проблема. Каждый поток выполняет кучу домашнего хозяйства (например, разделение набора), а затем одно умножение. И если вы посмотрите на общую картину, это означает, что N! требуется примерно N потоков.

Мы можем сделать лучше. Вместо того, чтобы ждать завершения двух субтитров. «Текущая» нить могла выполнять работу одного из них; например

factorialHelper(set) = 
    if set.size == 1 
     return set.first 
    else 
     let set1, set2 = split_into_subsets(set, 2) 
     let child = fork(lanbda factorialHelper(set1)) 
     return factorialHelper(set2) * child.join() 

Для этого требуется примерно N/2 резьбы. И есть большие проблемы:

• Создание потоков очень дорого.
• Резьбовое переключение/ожидание завершения другой резьбы относительно дорого.
• В любой момент времени на вашем компьютере будет работать столько потоков, сколько у него есть физические (или гипертекстовые) ядра.

Так что, если бы вы хотели кодировать выше буквально на Java, он работал бы как собака. Слишком много потоков. Слишком много создания потоков/переключения накладных расходов и слишком мало полезно Работа для каждой нити.

Если вы используете Java Fork/Join Pool, вы можете сделать намного лучше, но вам также нужно что-то сделать о шаге split_into_subsets(set, 2). Это собирается сделать много лишней работы копирование набор элементов.

Классический подход состоит в том, чтобы иметь один общий массив (от 1 до N) и передавать «низкие» и «высокие» индексы. Но в этом случае нам даже не нужен массив, потому что мы знаем, что array[i] - это то же самое, что и i. (Игнорировать по-одному. Я все еще говорю псевдокод!)

Но тогда мы дойдем до последней проблемы. Балансировка рабочей нагрузки. Работа умножения двух больших (например, BigInteger) чисел не является постоянной. Фактически это зависит от величины чисел. (Я думаю, что для M * N это O (журнал M * войти N). Если вы используете наивные разделяй и властвуй, умножений на «левом конце» гораздо быстрее, чем у «правого конца». Решая это сложно, и я подозреваю, что разделяй и властвуй неправильный подход для работы с ним

Я бы на самом деле рассмотреть гибридный подход:.

• Создать T рабочие потоки, где T соответствует числу доступных ядер.
• Распределите номера 1 через N в T подмножества, в круговой форме.
• Получите каждую нить (последовательно) вычислить произведение всех чисел в своем подмножестве.
• Сделайте окончательные умножения продуктов подмножества, используя как можно больше потоков.

В конце расчета, независимо от того, как вы это сделаете, произойдет окончательное умножение, которое будет выполнено с использованием одного потока. И два вычисления до этого могут быть выполнены не более чем на 2 потока. Так что в конце концов, какой-то поток «голода» будет неизбежен.

И наконец, существует само умножение. Ясно, что если мы вычисляем factorial (N) для достаточно большого N для нескольких потоков, чтобы стоить, результат будет больше Long.MAX_VALUE. Использование BigInteger было бы очевидным выбором. Тем не менее, есть немного вопросительного знака над BigInteger.multiply(BigInteger). Возможно, стоит посмотреть на высокопроизводительные алгоритмы умножения N-разрядных чисел и алгоритмы умножения, которые можно распараллелить. Начало здесь:

• Computational complexity of mathematical operations

Для записи, сложность BigInteger.multiply(BigInteger) для двух п-значных чисел следующим образом:

• Java 6 использует алгоритм "школьный мальчик" ; т.е. сложность O (n * n) для n цифр

• Java 8 использует алгоритм «школьного мальчика», алгоритм Карацубы (O (n * 1.585)) или трехстороннее умножение Toom-Cook (O (n * 1.465)) в зависимости от размера n. Таким образом, в конечном счете, сложность O (n * 1.465).

Answer 4

Как насчет этого кода: - 1. Получить число входных и создавать пары (начало, конец). 2. Создайте задачу, которая умножает заданное число и возвращает результаты; 3. Отправьте задачу. 4. Получите результаты, используя будущее.

общественного класса TestFactorial {

public static void main(String[] args) throws InterruptedException,ExecutionException { 


    Scanner scanner = new Scanner(new InputStreamReader(System.in)); 
    System.out.println(" Please enter the number for which you want to calculate Factorial"); 
    String input = scanner.nextLine(); 
    int number =0; 
    int answer =1; 
    scanner.close(); 
    if(input!=null) 
      number = Integer.valueOf(input); 
    if(number==0 || number ==1){ 
      answer = 1; 
    } 
    calcuateFactorial(number, answer); 

} 

private static void calcuateFactorial(int number, int answer) throws InterruptedException, ExecutionException { 
    ExecutorService executor = Executors.newFixedThreadPool(10); 
    List<Future<Integer>> totalTaskResults = new ArrayList<Future<Integer>>(); 
    for(int start =1;start<=number ;start++){ 
     int end = start+1; 
     Future<Integer> taskResult; 
     if(end>start) 
      taskResult = executor.submit(new Multiply(start, 1)); 
     else 
      taskResult= executor.submit(new Multiply (start, end)); 
     totalTaskResults.add(taskResult); 

    } 

    for (Future<Integer> future :totalTaskResults){ 
     answer = answer* future.get(); 
    } 
    executor.shutdown(); 
    System.out.println("Answer "+ answer); 
} 

}

Вот вызываемая класс (задачи): -

public class Multiply implements Callable<Integer>{ 
private int start ; 
private int end; 


public Multiply (int start, int end){ 
    this.start= start; 
    this.end = end; 
} 

@Override 
public Multiply call() throws Exception { 
    return start*end; 
} 

}