Вычисление факториала через DnC

Я пытаюсь реализовать факториальную функцию с помощью стратегии «разделяй и властвуй». Я использовал инфраструктуру ForkJoin для разветвления каждой рекурсивной задачи, чтобы ускорить вычисления. Но я обнаружил, что это не ускоряется, как я ожидал. Вычисление факториала 50000 без использования ForkJoin заняло 28 секунд, а при использовании ForkJoin — 25 секунд. это код без 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. Пожалуйста помоги!


java fork-join java-7
person batman    schedule 02.02.2012    source источник
comment
Если вам нужно рассчитать много факториалов, вы должны заранее вычислить факториалы в необходимом вам диапазоне, а затем просто использовать их повторно. Вы не можете одновременно эффективно выполнять факториальные вычисления.   -  person Maurício Linhares    schedule 02.02.2012
comment
Советы по повышению производительности при использовании BigInteger: замените new BigInteger("1") константой BigInteger.ONE; Замените new BigInteger("" + p) на BigInteger.valueOf(p). Это быстрее и повторно использует ранее созданные экземпляры, где это возможно.   -  person gb96    schedule 05.12.2012
comment
@Maurício Для больших значений n используйте параллельные алгоритмы для вычисления n! теперь являются самыми быстрыми из известных. См. алгоритмы и тесты на luschny.de/math/factorial/FastFactorialFunctions.htm.   -  person gb96    schedule 05.12.2012

Ответы (1)


arrow_upward
5
arrow_downward

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
   }
}
person helios    schedule 02.02.2012