Mehrdimensionale Arrays in Java langsam?

[Chr__Au]

Hallo,

ich soll ein Programm schreiben in dem ich die These, dass Vektor- und Matrizenberechnung in Java langsam und nicht sinnvoll ist, beweisen.

Ich soll ein Vektor beliebiger Größe mit einem Array darzustellen und einen in dem die Werte in Objekt-Atribute gespeichert sind. Soweit alles klar.

Jetzt soll ich aber das gleiche mit Matrizen machen einmal mit einem Mehrdimensionalen-Array und einmal mit einem eindimensionalen Array + die Anzahl der Spalten als Atribut.

(
e00 e01 e02
e10 e11 e12
e20 e21 e22 )

new double [] {e00,e01,e02,e10,e11,e12,e20,e21,e22}

Zum Schluss soll ich eine Zeitmessung durchführen.

Leider benötigt die "Effizientere" Methode B (mit einem Array) in etwa 80% der Fälle mehr Zeit.

Kann es also sein, dass mehrdimensionale Arrays doch schneller sind, als dass ich immer schaue wann der nächste Zeilenumbruch sein muss?
[EDIT]Beispiel Ausgaben:

Vektor v1 5866
Vektor v2 2444
[14.0, 32.0, 50.0]
Matrix v1 27864
[6.0, 6.0, 6.0]
Matrix v1 44484

Vektor v1 5377
Vektor v2 1955
[14.0, 32.0, 50.0]
Matrix v1 25908
[6.0, 6.0, 6.0]
Matrix v1 29331

Vektor v1 5866
Vektor v2 2933
[14.0, 32.0, 50.0]
Matrix v1 26397
[6.0, 6.0, 6.0]
Matrix v1 23465

[/EDIT]

 

[Beni]

Kommt auf deinen Code an...

Aber wenn das in der JVM ähnlich wie bei C/C++ abläuft, wundert es mich nicht sehr, dass der 2d-array schneller sein kann.
2d array: array[x][y] wird zu einer Pointer-operation die etwa so aussieht "(array + size<int> * x) + size<int> * y", da size<int> etwas wie 4 oder 8 ist, kann natürlich das effiziente bit-shifting verwendet werden.
1d array: array[x][y] wird zu etwas wie "array + x + y * sizeOfOneRow". Nur "y * sizeOfOneRow" ist eine echte Multiplikation, also verhältnismässig ineffizient.

 

[Chr__Au]

okay, ka.

Vielleicht habe ich auch mist bei der Matrix-Vektor-Multiplikation gemacht. Für die Zuweisung habe ich 3 Methodenaufrufe:

numColumn -> soll die anzahl der Spalten aufnehmen
MathFactory.createVector -> wurde vom Prof so gewünscht
setVector -> erwartet einen index und einen Wert
getVector -> liefert einen double an der index pos zurück
matrix -> ist das eindimensionale Array welches eine Matrix simulieren soll.

public Vector multi(Vector vector) {
		Vector result = MathFactory.createVector(matrix.length / numColumn);
		for (int i = 0; i < matrix.length/numColumn; i++) {
			for (int k = 0; k < numColumn; k++) {
				result.setVector(i, result.getVector(i)
						+ matrix[numColumn * i + k] * vector.getVector(k));
			}
		}
		return result;
	}

 

[Marco13]

Es geht um 3D? Wie machst du denn die Zeitmessung? (Tipp: Falsch 😀)

 

[Chr__Au]

Also ich habe nur die Berechnung (mat_.multi(vector).g... und nicht das inizielisieren ... zwischen den Zeitmessungen, damit es auch wirklich keine unnötigen Verzögerungen gibt.

double[] tmpd1;
		long t1 = System.nanoTime();
		tmpd1 = mat1.multi(vector).getVector();
		long t2 = System.nanoTime();
		System.out.println(Arrays.toString(tmpd1));
		
		

		System.out.println("Matrix v1 " + (t2 - t1));

		double[] tmpd2;
		long t3 = System.nanoTime();
		tmpd2 = mat2.multi(vector).getVector();
		long t4 = System.nanoTime();
		System.out.println(Arrays.toString(tmpd2));

		System.out.println("Matrix v2 " + (t4 - t3));

Ich denke mal das bringt jetzt hier aber nichts mehr, ich frage einfach nächste Woche meinen Prof. Vielleicht sollte das ja auch gerade passieren.

Kein 3D einfach nur die Berechnung.

 

[Ark]

Sehe ich das richtig, dass mit Vector hier nicht

java.util.Vector

gemeint ist?

Ist das eine Aufgabe vom Prof? Wenn ja:

ich soll ein Programm schreiben in dem ich die These, dass Vektor- und Matrizenberechnung in Java langsam und nicht sinnvoll ist, beweisen.

MathFactory.createVector -> wurde vom Prof so gewünscht

Wie geil ist das denn?! :lol:

[EDIT]Nur speziell "Matrix mal (eindimensionaler) Vektor", oder allgemein "Matrix mal Matrix"?[/EDIT]
Ark

 

[Chr__Au]

Also es soll eine Matrix Vektor multiplikation sein. Matrix * Vektor = Vektor

Die Factory soll eine möglichkeit bieten, entweder ein Vektor A (mit Array als Speicher) oder B mit (Atributen als Speicher, nur für 2dim Vektoren).

sowie Matrizen mit einem double[][] als Speicher und einmal mit double[] als speicher und zusätzlichem Spalten Atribut.

Bei der Multiplikation soll darauf geachtet werden, dass der Ergebnisvektor über die Fabrik erzeugt wird. Somit muss ich ja result mit createVektor anlegen.

Alle VectorKlassen sind von mir selbst geschrieben.

package chrau.prog2.exercises.set4;

public interface Vector {


	double[] sum(Vector secondAddend) throws ArithmeticException;

	
	double[] sub(Vector subtrahend) throws ArithmeticException;


	double[] ScalarMulti(double scalar);

	
	void setVector(double... element) throws IllegalArgumentException;


	double getVector(int index) throws IndexOutOfBoundsException;

	
	double[] getVector();

	
	void setVector(int index, double newValue) throws IndexOutOfBoundsException;

}

Aber allgemein ist meine Frage ja was ist schneller in Java, eine Matrix in einem mehrdimensionalen Array oder die Implementierung wie sie angeblich in C und C++ (kann ich leider beides nicht) ist:

(
e00 e01 e02
e10 e11 e12
e20 e21 e22 )

new double [] {e00,e01,e02,e10,e11,e12,e20,e21,e22}

 

[Marco13]

Erstmal vorneweg: Die Zeitmessungen sind so vollkommen unsinning. Die Zeit, die zum Ausführen so einer kleinen Matrix-Vektor-Multiplikation benötigt wird, ist ggf. geringer, als die Auflösung, die der Timer für die Zeitmessung hat. "NanoTime" liefert zwar Zeiten in Nanosekunden, kann aber NICHT Nanosekunden-Genau messen - dafür müßtest du mal in der Physikalisch-Technischen Bundesanstalt in Braunschweig nachfragen - die mit der Atomuhr 😀 (In einer Nanosekunde bewegt sich ein Lichtstrahl ca. 30cm weit...)

Man müßte in diesem Fall also größere Matrizen verwenden. Da auch noch der JIT eine Rolle spielt, sollte die fragliche Methode außerdem eigentlich mehrere tausend mal aufgerufen werden, bis man verläßliche Ergebnisse bekommt. Ein Muster, mit dem man solchen "Microbenchmarks" wenigstens einen Hauch Aussagekraft geben kann, ist

long t0 = 0;
long t1 = 1;
int runs = 10;
for (int r=0; r<runs; r++)
{
    for (int size=100; size<=10000; size*=10)
    {
        Data data = createInputData();

        t0 = System.nanoTime();
        Result result0 = runMethod0(data);
        t1 = System.nanoTime();
        System.out.println("Result0 "+result0+" time "+((t1-t0)*1e-6)+" ms");

        t0 = System.nanoTime();
        Result result1 = runMethod1(data);
        t1 = System.nanoTime();
        System.out.println("Result1 "+result1+" time "+((t1-t0)*1e-6)+" ms");
    }
}

Also mehrmals beide Verfahren abwechselnd mit steigenden Eingabegrößen laufen lassen (und die Ergebnisse in einer Ausgabe verwenden, damit's nicht wegoptimiert werden kann). Ein bißchen mehr steht dazu in AngelikaLanger.com - Java Performance - Micro-Benchmarking - Angelika Langer Training/Consulting

Es wäre gut, wenn du genau beschreiben würdest, was vorgegeben ist, und was du selbst machen sollst. (Und wenn das Interface so vorgegeben war... :autsch: .. naja, war's wohl nicht)

Zur eigentlichen Frage: Ja, in C/C++ verwendet man tendenziell eher 1D-Arrays - auch für 2D-Matrizen. Der Grund dafür ist, dass ein dymamisch allokierter 2D-Array in C/C++ ein ziemlicher Krampf ist, weil man alle Zeilen einzeln allokieren und am Ende auch wieder einzeln löschen muss.

Der mögliche Geschwindigkeitsunterschied bei beiden Darstellungsweisen in Java kann aber viele Gründe haben. Ich bin da selbst mal drüber gestolpert: Der Thread http://www.java-forum.org/allgemein...nfluss-caching-performance-grosse-arrays.html könnte für dich in mehrerer Hinsicht interessant sein.

 

[Ark]

@Marco13: Jaja, das berühmte Seitenflattern … (oder sollte man eher Cacheflattern sagen?) 😉 https://en.wikipedia.org/wiki/Thrashing_(computer_science)

10000 Aufrufe sollten es schon mindestens sein: Stas's blog: The most complete list of -XX options for Java JVM Wobei das natürlich von der JVM-Implementierung abhängt. (Im OpenJDK scheint es diesen Parameter nicht zu geben, jedenfalls kommt bei mir immer nur eine Fehlermeldung, wenn ich ihn zu verwenden versuche.)

Meinen Messungen zufolge kann ich mit

System.nanoTime()

im Mittel nur eine Differenz von knapp 57 Nanosekunden erfassen. In der Zeit ist also das Licht 17 Meter weiter … :reflect: Bei solchen Zahlen wird einem irgendwie anders. 😀

Zur eigentlichen Frage: Ja, in C/C++ verwendet man tendenziell eher 1D-Arrays - auch für 2D-Matrizen. Der Grund dafür ist, dass ein dymamisch allokierter 2D-Array in C/C++ ein ziemlicher Krampf ist, weil man alle Zeilen einzeln allokieren und am Ende auch wieder einzeln löschen muss.

Es gibt auch Performancegründe, und wahrscheinlich auch deshalb verwendet ein BufferedImage intern eindimensionale Arrays: Zweidimensionale Arrays werden (zumindest in Java) intern als Arrays von Arrays umgesetzt. Jedes dieser Arrays kann prinzipiell irgendwo auf dem Heap landen. Die räumliche Lokalität ist damit sehr wahrscheinlich nicht mehr sichergestellt. Folge: Die CPU-Caches haben schneller ein Problem damit, es kommt eher zu Cache-Misses und/oder Cache-Lines können nicht in vollem Maße benutzt werden.

Hab' mal gerade aus Jux und Tollerei was zusammengehackt:

	public static final void mulMatrixVector(final double[] matrix, final double[] vector, final double[] result){
		int mi = 0;
		for(int ri = 0; ri < result.length; ri++){
			double tmp = 0.0;
			for(int vi = 0; vi < vector.length; vi++){
				tmp += matrix[mi++] * vector[vi];
			}
			result[ri] = tmp;
		}
	}

Für Matrix×Vektor braucht man, wie man sieht, gar keine Information darüber, wie "breit" oder "hoch" die Matrix ist, da sich das alles durch die Dimensionen der beiden Vektoren (eingegebener Vektor und Zielvektor) ergibt. Für große Matrizen gibt es ganz andere Verfahren, und bei kleinen Matrizen fester Größe (ich nehme mal an, es geht hauptsächlich um 3×3-Matrizen) könnte man entsprechende Vereinfachungen/Spezialisierungen vornehmen.

Auch wenn ich den Ausgang des Experimentes noch nicht kenne: Ich vermute ebenfalls, dass da jemand einfach keine Ahnung hat, wie man richtig misst. 😉

Ark

[EDIT]Ich habe mir mal vor einiger Zeit einen Testrahmen für solche Zwecke geschrieben. Vielleicht sollte ich ihn mal ins Forum stellen. *überleg*[/EDIT]