Расчет факториала через DnC - PullRequest
Новая
       25

Расчет факториала через DnC

2 голосов
/ 02 февраля 2012

Я пытаюсь реализовать Факториальную функцию через стратегию «разделяй и властвуй».Я использовал инфраструктуру ForkJoin для разветвления каждой рекурсивной задачи для ускорения вычислений.Но я обнаружил, что это не ускорение, как я ожидал.Потребовалось 28 секунд, чтобы вычислить факториал 50000 без использования ForkJoin, а потребовалось 25 секунд, когда я использовал ForkJoin.это код без forkjoin: 

public static BigInteger factorial(long p, long q) {
    if (q < p) {
        return new BigInteger("1");
    }
    if (p == q) {
        return new BigInteger("" + p);
    }
    BigInteger fact = new BigInteger("1");
    fact = fact.multiply(factorial(p, (p + q) / 2)).multiply(factorial((p + q) / 2 + 1, q));
    return fact;
}

А это код с forkJoin: 

public class Factorial extends RecursiveTask<BigInteger>{
private long p, q;
public Factorial(long p, long q) {
    this.p = p;
    this.q = q;
}
@Override
public BigInteger compute() {
    if(q < p) {
        return new BigInteger("1");
    } 
    if( p == q) {
        return new BigInteger(""+p);
    }
    Factorial f1 = new Factorial(p, (p+q)/2);
    Factorial f2 = new Factorial((p+q)/2 + 1, q);
    f2.fork();
    return f1.compute().multiply(f2.join());        
}    
}

Где я ошибаюсь?Я не думаю, что это будет результатом Fork / Join.Пожалуйста, помогите!

1 Ответ

5 голосов
/ 02 февраля 2012

Fork / Join может парализовать вычисления. Это: дает вам постоянный выигрыш (разделите время на 4 на примере). И это ограничено реальными процессорами, которые у вас есть (например, 200 потоков будут использовать одни и те же 4 процессора).

В противоположность факториалу (типичный алгоритм) равен O(N!), что означает, что он очень очень быстро растет.

И если вы создаете новый форк для каждого шага, накладные расходы на разветвление и соединение компенсируют выигрыш от распараллеливания.

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

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

Глядя на ваш код, я вижу, что выполнение каждого факторного метода провоцирует два дочерних выполнения: (p+q)/2,q и p,(p+q)/2+1 ... или что-то в этом роде. Если каждый метод факториала времени находит результат, сохраняет его на карте [Pair -> BigDecimal], вы можете запросить этот кеш в начале метода. Сделайте эту карту членом вашего класса (или передайте ее через аргументы), чтобы различные вызовы методов разделяли карту. 

factorial(p,q) {
   if (there is result for (p,q) in the map)
      return it
   else
   {
      normal computation (provokes two child invocations)
      save result into cache
   }
}
...