Tính toán yếu tố quyết định ma trận

Question

Tôi đang cố gắng tính toán yếu tố quyết định của ma trận (có kích thước bất kỳ), để thực hành tự mã hóa/phỏng vấn. Nỗ lực đầu tiên của tôi là sử dụng đệ quy và dẫn tôi đến việc triển khai sau:

import java.util.Scanner.*; 
public class Determinant { 

    double A[][]; 
    double m[][]; 
    int N; 
     int start; 
     int last; 

     public Determinant (double A[][], int N, int start, int last){ 
      this.A = A; 
      this.N = N; 
      this.start = start; 
      this.last = last; 
     } 

     public double[][] generateSubArray (double A[][], int N, int j1){ 
      m = new double[N-1][]; 
      for (int k=0; k<(N-1); k++) 
        m[k] = new double[N-1]; 

      for (int i=1; i<N; i++) 
      { 
        int j2=0; 
        for (int j=0; j<N; j++) 
        { 
         if(j == j1) 
           continue; 
         m[i-1][j2] = A[i][j]; 
         j2++; 
        } 
      } 
      return m; 
     } 
    /* 
    * Calculate determinant recursively 
    */ 
    public double determinant(double A[][], int N) 
    { 
     double res; 

     // Trivial 1x1 matrix 
     if (N == 1) 
      res = A[0][0]; 
     // Trivial 2x2 matrix 
     else if (N == 2) 
      res = A[0][0]*A[1][1] - A[1][0]*A[0][1]; 
     // NxN matrix 
     else 
     { 
      res=0; 
      for (int j1=0; j1<N; j1++) 
      { 
          m = generateSubArray (A, N, j1); 
          res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * determinant(m, N-1); 
      } 
     } 
     return res; 
    } 
} 

Cho đến giờ tất cả đều tốt và nó mang lại cho tôi kết quả chính xác. Bây giờ tôi muốn tối ưu hóa mã của mình bằng cách sử dụng nhiều luồng để tính toán giá trị quyết định này. Tôi đã cố gắng song song nó bằng cách sử dụng mô hình Java Fork/Join. Đây là cách tiếp cận của tôi:

@Override 
     protected Double compute() { 
      if (N < THRESHOLD) { 
       result = computeDeterminant(A, N); 
       return result; 
      } 

      for (int j1 = 0; j1 < N; j1++){ 
       m = generateSubArray (A, N, j1); 
       ParallelDeterminants d = new ParallelDeterminants (m, N-1); 
       d.fork(); 
       result += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * d.join(); 
      } 

      return result; 
     } 

    public double computeDeterminant(double A[][], int N) 
    { 
     double res; 

     // Trivial 1x1 matrix 
     if (N == 1) 
      res = A[0][0]; 
     // Trivial 2x2 matrix 
     else if (N == 2) 
      res = A[0][0]*A[1][1] - A[1][0]*A[0][1]; 
     // NxN matrix 
     else 
     { 
      res=0; 
      for (int j1=0; j1<N; j1++) 
      { 
          m = generateSubArray (A, N, j1); 
          res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * computeDeterminant(m, N-1); 
      } 
     } 
     return res; 
    } 

/* 
* Main function 
*/ 
public static void main(String args[]) 
{ 
    double res; 
      ForkJoinPool pool = new ForkJoinPool(); 
      ParallelDeterminants d = new ParallelDeterminants(); 
      d.inputData(); 
    long starttime=System.nanoTime(); 
      res = pool.invoke (d); 
    long EndTime=System.nanoTime(); 

    System.out.println("Seq Run = "+ (EndTime-starttime)/100000); 
    System.out.println("the determinant valaue is " + res); 
} 

Tuy nhiên sau khi so sánh việc thực hiện, tôi thấy rằng việc thực hiện các Fork/Tham cách tiếp cận là rất xấu, và kích thước ma trận cao hơn, chậm hơn nó trở nên (so với người đầu tiên tiếp cận). Đâu là chi phí? Có ai có thể làm sáng tỏ cách cải thiện điều này không?

Answer 1

Lý do chính mã ForkJoin chậm hơn là nó thực sự được nối tiếp với một số luồng trên đầu vào. Để hưởng lợi từ ngã ba/tham gia, bạn cần phải 1) chia tất cả các trường hợp trước, sau đó 2) đợi kết quả. Chia vòng lặp của bạn trong "tính toán" thành hai vòng: một đến ngã ba (lưu trữ các thể hiện của ParallelDeterminants trong, nói, một mảng) và một để thu thập kết quả.

Ngoài ra, tôi đề nghị chỉ dùng ngã ba ở mức ngoài cùng và không ở bất kỳ cái nào bên trong. Bạn không muốn tạo chủ đề O (N^2).