DnC를 통한 계승 계산

Question

나는 나누기와 정복 전략을 통해 Factorial 함수를 구현하려고합니다. 계산 속도를 높이기 위해 ForkJoin 프레임 워크를 사용하여 각 재귀 작업을 포크 화했습니다. 하지만 예상대로 속도가 올라가지 않는 것으로 나타났습니다. 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의 결과라고 생각하지 않는다. 도와주세요!

Answer 1

포크/가입으로 컴퓨팅을 병렬화 할 수 있습니다. 그것은 : 당신에게 일정한 이득을줍니다 (예를 들어 시간을 4로 나눕니다). 그리고 그게 당신이 가진 실제 CPU에 국한됩니다. (예를 들어, 200 개의 스레드는 동일한 4 개의 CPU를 공유합니다.)

계급 비교 (일반적인 알고리즘)는 O(N!)입니다. 이는 매우 매우 빠르게 성장한다는 것을 의미합니다.

각 단계마다 새 분기를 작성하면 분기 및 결합의 오버 헤드로 인해 병렬 처리에서 얻는 이득이 보상됩니다.

따라서 중요한 것은 O(N!)이 아닌 다른 알고리즘으로 계승을 계산하려고하는 것입니다. 동적 프로그래밍 (중간 결과 재사용)을 적용하면 O(N)으로 변환 할 수 있습니다. 난 당신이 내가 그들에게 두 번째 시간을 필요로 할 때 재사용하기 위해 쌍에 대한 계산과 매트릭스 또는 뭔가를 mantaining되어 무엇을해야하는지에 의해 모방하려고하는 알고리즘을 모르는

...

---

코드를 보면 각 계승 방법 실행이 두 개의 자식 실행을 유발할 수 있음을 알 수 있습니다 : (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 
    } 
}