Die Berechnung der matrix-Determinante
Ich versuche, die Berechnung der Determinante einer matrix (beliebiger Größe), für selbst-Kodierung /interview Praxis. Mein Erster Versuch ist mit Rekursion und das führt mich zu folgender Umsetzung:
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;
}
}So weit, es ist alles gut und es gibt mir ein richtiges Ergebnis. Nun würde ich gerne meinen code optimieren, indem Sie die Verwendung mehrerer threads für die Berechnung dieser Determinante Wert.
Ich habe versucht zu parallelisieren, es mit der Java Fork/Join-Modell. Dies ist mein Ansatz:
@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);
}Jedoch nach Vergleich der Leistung, fand ich, dass die Leistung des Fork/Join-Ansatz ist sehr schlecht, und je höher der matrix-dimension ist, desto langsamer wird es (im Vergleich zum ersten Ansatz). Wo ist der Aufwand? Kann jemand Aufschluss geben, wie das zu verbessern?
- Vor dem Wurf in den threads, ich würd halt die Zuweisung in der Schleife. Eine Möglichkeit wäre, zwei array-Parameter, die bestimmen, welche Zeilen und Spalten zu berechnen, statt N.
- Ich würde dir empfehlen, einen Blick auf einige algorithmen entwickelt, um parallel sein. Ich ging nicht durch den Algorithmus aber in meiner Erfahrung viele clevere Optimierungen finden für gemeinsame Probleme zu suchen um.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Der Hauptgrund der ForkJoin code langsamer ist, dass es tatsächlich serialisiert mit Faden overhead geworfen. Profitieren Sie von fork/join, müssen Sie 1) Gabel alle Instanzen zuerst, dann 2) auf die Ergebnisse zu warten. Teilen Sie Ihre Schleife in "compute" in zwei Schleifen: eine Gabel (speichern von Instanzen von ParallelDeterminants in, sagen wir, ein array) und ein weiterer zum sammeln der Ergebnisse.
Auch, ich schlage vor, nur die Gabel an der äußersten Ebene und nicht in der inneren. Sie wollen nicht zu schaffen O(N^2) threads.
Mithilfe Dieser Klasse können Sie berechnen die Determinante einer matrix mit jeder dimension
Diese Klasse nutzt viele verschiedene Methoden, um die matrix dreieckig und dann berechnet die Determinante davon. Es kann verwendet werden, für die matrix von hoher dimension wie 500 x 500 oder sogar noch mehr. die helle Seite der dieser Klasse ist, dass man die Ergebnis in BigDecimal so gibt es keine Unendlichkeit und haben Sie immer die genaue Antwort auf die. Durch die Art und Weise, mit vielen verschiedenen Methoden und die Vermeidung von Rekursion führte zu einer viel schnelleren Weg mit höherer Leistung, um die Antwort. hoffe, dass es hilfreich sein würde.
Diese Klasse Empfängt eine matrix von n x n aus der Benutzer wird dann berechnet, es ist Determinante. Es zeigt auch die Lösung und die abschließende dreieckige matrix.