Ein Algorithmus soll schneller werden

[Canis_Lupus]

Hi zusammen

Ich benötige Unterstützung bei einer Optimierug. Ein Algorithmus soll schneller werden.

Die Aufgabe ist eine Teilaufgabe eines Sandkastens den ich Entwickel. Deshalb sind viele Parameter nicht fest vorgegeben sondern können später vom User gewählt werden. Dies betrifft z. B den nachbarschaftsAbstand und auch den abstandsFaktor doch dazu gleich mehr.

Zum Hintergrund:
Aus einem großen 3 dimensionalen Arry ziehe ich mir einen Auszug der Größe 100x100x100 Datenpunkte. ( In diesem Programm sind es 120x120x120 damit ich Randprobleme später behandeln kann.) Für jeden der Datenpunkte soll nun der Einfluss der anderen Punkte auf ihn berechnet werden. Dabei nimmt der Einfluss aufeinander mit steigendem Abstand, mit einem wählbaren Faktor (abstandsFaktor) ab. Daduch müssen für ein hinreichend genaues Ergebniss auch nich alle Einflüsse berechnet werden, sondern nur die im Nahbereich (nachbarschaftsAbstand).
Im Sandkasten selber werden es dann ca. 30 Parameter werden die nach unterschiedlichen Regeln berechnet werden. Hier für die Optimierung habe ich mich auf einen Parameter (beeinflussenderParameter) beschränkt.

In der erster Lösung (Kubus) spanne ich einen Kubus der Kantenlänge nachbarschaftsAbstand um den zu beeinflussenden Datenpunkt. Nachteil ist, dass hierbei auch die entfernteren Punkte in den Ecken, obwohl sie wenig Einfluss haben, mit berechnet werden. Ich nehme diese Berechnung als Referenzergebniss um die obtimierten Versionen bewerten zu können.

Die zweite Lösung (Kugel) rundet nur die Ecken ein wenig ab um die Anzahl der Rechnungen zu verringern. Auf weitere Optimierungen habe ich komplett verzichtet um anderen Ansätzen nicht im Weg zu stehen.

Über Tipps und Ideen von euch, wie ich diesen Algorithmus beschleunigen kann würde ich mich freuen.


[CODE lang="java" title="Die Klasse entityNB"]package NachbarschaftNB;

public class entityNB {

//Legt den beeinflussten Parameter auf einen Basiswert zwischen 995-1005 fest.
private short beeinflussterParameter = (short) (Math.random()*11+995);
// legt den beeinflussenden Parameter auf 0-100 fest.
private short beeinflussenderParameter = (short) (Math.random()*22-11);

public short getBeeinflussterParameter() {
return beeinflussterParameter;
}

public void setBeeinflussterParameter(short beeinflussterParameter) {
this.beeinflussterParameter = beeinflussterParameter;
}

public short getBeeinflussenderParameter() {
return beeinflussenderParameter;
}

public void setBeeinflussenderParameter(short beeinflussenderParameter) {
this.beeinflussenderParameter = beeinflussenderParameter;
}

}
[/CODE]


[CODE lang="java" title="Main und die Algorithmen"]package NachbarschaftNB;

public class startNB {

public static void main(String[] args) {
// Festlegen der Arraygrenzen
int xKoordinateMax = 120;
int yKoordinateMax = 120;
int zKoordinateMax = 120;

// Willkuerlich gewaehlte Startkoordinaten als Alternativer zur Schleife
// ueber 100x100x100 Punkte.
//int xAusgangsKoordinate = 23;
//int yAusgangsKoordinate = 42;
//int zAusgangsKoordinate = 84;


int nachbarschaftsAbstand = 3; // Abstand bis zu dem eine Beeinflussung gewertet werden soll. Typische Werte 3-10
float abstandsFaktor = 1/3f; // Faktor um den mit zunehmendem Abstand der Einfluss schwindet. Typische Werte 1/1,2 - 1/20


entityNB[][][] world = new entityNB[xKoordinateMax][yKoordinateMax][zKoordinateMax];

// Nur Befuellen des Arrays. Fuer die Aufgabe nicht relevant.
for(int xKoordinate = 0;xKoordinate < xKoordinateMax; xKoordinate ++) {
for(int yKoordinate = 0;yKoordinate < yKoordinateMax; yKoordinate ++) {
for(int zKoordinate = 0;zKoordinate < zKoordinateMax; zKoordinate ++) {
world[xKoordinate][yKoordinate][zKoordinate] = new entityNB();
// System.out.println(world[xKoordinate][yKoordinate][zKoordinate].getBeeinflussterParameter());
// System.out.println(world[xKoordinate][yKoordinate][zKoordinate].getBeeinflussenderParameter());
}
}
}

/* Einige Variablen erklaert
* xAusgangsKoordinate, yAusgangsKoordinate, zAusgangsKoordinate = Absolutwerte Kooedinaten des Ausgangpunkts
* um diesen Punkte herumm wird errechnet wie gross die Beeinflussung ist.
* In diesem Testaufbau durchlauft der Punkt die Koordinaten 10,10,10 bis 100,100,100 .
*
* xKooedinate, yKooedinate, zKooedinate = Absolutwerte Kooedinaten der Punkte die gelesen
* und ihre Werte gewichtet werden
*
* gewichtungAbstandfaktor = beeinflussenderParameter * Math.pow(abstandsFaktor, Abstand)
* Wobei sich der Abstand aus den Summe der relativen Abstaende (x, y und z) zum Ausgangpunkt ergibt.
*
*
*/


// Schleife, die die Punkte (10,10,10) bis (110,110,110) (x,y,z) durchlauft
// fuer jeden dieser Punkte wird dann die Einwirkung durch die Nachbarn errechnet.

System.out.println("Start der Rechnung ");
for(int xAusgangsKoordinate = 10; xAusgangsKoordinate <= 110; xAusgangsKoordinate++) {
for(int yAusgangsKoordinate = 10; yAusgangsKoordinate <= 110; yAusgangsKoordinate++) {
for(int zAusgangsKoordinate = 10; zAusgangsKoordinate <= 110; zAusgangsKoordinate++) {



/* Version 1 Nick Name: Kubus ***************************************************************************************************
*
* Um die Ausgangskoordinaten wir ein Kubus mit der Kantenlaenge nachbarschaftsAbstand gelegt und berechnet,
* wie stark jeder Punkt im Kubus das Feld in der Mitte beeinflusst.
*
* nachbarschaftsAbstand = Spannt ein Rechteck mit der Kantenlaenge - nachbarschaftsAbstand bis + nachbarschaftsAbstand
* ueber x, y und z auf. (Obtiemierungspotential !!!)
*
*/

int schleifenzaehlerKubus = 0; // spielt nur waehrend des Optimierungsprozess eine Rolle um Loesungen vergleichen zu koennen.
double gewichteteSummeBeeinflussenderParameter = 0.0; // Das Setzen dieser Groesse ist das Ziel der ganzen Aufgabe.

for(int xKooedinate = xAusgangsKoordinate - nachbarschaftsAbstand; xKooedinate <= xAusgangsKoordinate + nachbarschaftsAbstand; xKooedinate ++ ) {
for(int yKooedinate = yAusgangsKoordinate - nachbarschaftsAbstand; yKooedinate <= yAusgangsKoordinate + nachbarschaftsAbstand; yKooedinate ++ ) {
for(int zKooedinate = zAusgangsKoordinate - nachbarschaftsAbstand; zKooedinate <= zAusgangsKoordinate + nachbarschaftsAbstand; zKooedinate ++ ) {
// System.out.println(" x " + xKooedinate + " y " + yKooedinate + " z " + zKooedinate);
double gewichtungAbstandfaktor = Math.pow(abstandsFaktor, Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate));
// System.out.println(" gewichtungAbstandfaktor " + gewichtungAbstandfaktor);
gewichteteSummeBeeinflussenderParameter = gewichteteSummeBeeinflussenderParameter + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor;
schleifenzaehlerKubus ++;
// System.out.println(" gewichteter Beeinflussender Parameter " + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor + " gewichteteSummeBeeinflussenderParameter " + gewichteteSummeBeeinflussenderParameter);
}
}
}
//System.out.println("xAusgangsKoordinate " + xAusgangsKoordinate + " yAusgangsKoordinate " + yAusgangsKoordinate + " zAusgangsKoordinate " + zAusgangsKoordinate);
System.out.println("schleifenzaehlerKubus " + schleifenzaehlerKubus + " gewichteteSummeBeeinflussenderParameter Kubus " + gewichteteSummeBeeinflussenderParameter);


/* Version 2 Nickname: Kugel ***************************************************************************************************
*
* Als Optimierung im Vergleich zur Version 1 Kubus werden hier die Ecken des Kubus,
* die ja auf grund des Abstands weniger Einfluss auf den Punkt in der Mitte haben,
* abgerundet.
*
* Wirklich unschoen ist bei dieser Loesung, dass zwei Schleifen benoetigt werden.
* Die Erste errechnet vom minimalen x bis imklusiver Mitte.
* Die Zweite von eins hinter Mitte bis x maximal.
*/

// Schleife von Aussen bis einschliesslich Mittelpunkt **********************************************

int schleifenzaehlerKugel = 0; // spielt nur waehrend des Optimierungsprozess eine Rolle um Loesungen vergleichen zu koennen.
double gewichteteSummeBeeinflussenderParameter2 = 0.0; // Das Setzen dieser Groesse ist das Ziel der ganzen Aufgabe.
int xSchleifenzaehler = 0; // Wird genutzt um die Ecken des Kubus abzurunden.
for(int xKooedinate = xAusgangsKoordinate - nachbarschaftsAbstand; xKooedinate <= xAusgangsKoordinate; xKooedinate ++ ) {
for(int yKooedinate = yAusgangsKoordinate - xSchleifenzaehler; yKooedinate <= yAusgangsKoordinate + xSchleifenzaehler; yKooedinate ++ ) {
for(int zKooedinate = zAusgangsKoordinate - xSchleifenzaehler; zKooedinate <= zAusgangsKoordinate + xSchleifenzaehler; zKooedinate ++ ) {
int abstandVonDerAusgangskoordinate = Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate);
//System.out.println(" x " + xKooedinate + " y " + yKooedinate + " z " + zKooedinate);
double gewichtungAbstandfaktor = Math.pow(abstandsFaktor, abstandVonDerAusgangskoordinate);
// System.out.println(" abstandsFaktor " + abstandsFaktor + " abs(xKooedinate) " + Math.abs(xKooedinate) + " abs(yKooedinate) " + Math.abs(yKooedinate) + " abs(zKooedinate) " + Math.abs(zKooedinate));
// System.out.println(" gewichtungAbstandfaktor " + gewichtungAbstandfaktor);
gewichteteSummeBeeinflussenderParameter2 = gewichteteSummeBeeinflussenderParameter2 + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor;
schleifenzaehlerKugel ++;
// System.out.println(" gewichteter Beeinflussender Parameter " + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor + " gewichteteSummeBeeinflussenderParameter " + gewichteteSummeBeeinflussenderParameter);
}
}
xSchleifenzaehler ++;
}
// System.out.println("schleifenzaehlerKugel Zwischenwert" + schleifenzaehlerKugel + " gewichteteSummeBeeinflussenderParameter 1. Haelfte und Mitte Kugel " + gewichteteSummeBeeinflussenderParameter2);


// Schleife von exklusiev Mitte bis Aussen. **********************************************
xSchleifenzaehler = 0; // Wird genutzt um die Ecken des Kubus abzurunden.
for(int xKooedinate = xAusgangsKoordinate + 1; xKooedinate <= xAusgangsKoordinate + nachbarschaftsAbstand; xKooedinate ++ ) {
for(int yKooedinate = yAusgangsKoordinate - nachbarschaftsAbstand + 1 + xSchleifenzaehler; yKooedinate <= yAusgangsKoordinate + nachbarschaftsAbstand - 1 -xSchleifenzaehler; yKooedinate ++ ) {
for(int zKooedinate = zAusgangsKoordinate - nachbarschaftsAbstand + 1 + xSchleifenzaehler; zKooedinate <= zAusgangsKoordinate + nachbarschaftsAbstand - 1 -xSchleifenzaehler; zKooedinate ++ ) {
int abstandVonDerAusgangskoordinate = Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate);
//System.out.println(" x " + xKooedinate + " y " + yKooedinate + " z " + zKooedinate);
double gewichtungAbstandfaktor = Math.pow(abstandsFaktor, abstandVonDerAusgangskoordinate);
// System.out.println(" gewichtungAbstandfaktor " + gewichtungAbstandfaktor);
gewichteteSummeBeeinflussenderParameter2 = gewichteteSummeBeeinflussenderParameter2 + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor;
schleifenzaehlerKugel ++;
// System.out.println(" gewichteter Beeinflussender Parameter " + world[xKooedinate][yKooedinate][zKooedinate].getBeeinflussenderParameter() * gewichtungAbstandfaktor + " gewichteteSummeBeeinflussenderParameter " + gewichteteSummeBeeinflussenderParameter);
}
}
xSchleifenzaehler ++;
}
System.out.println("schleifenzaehlerKugel " + schleifenzaehlerKugel + " gewichteteSummeBeeinflussenderParameter gesamt Kugel " + gewichteteSummeBeeinflussenderParameter2);
System.out.println();
} // Ende zAusgangsKoordinate Schleife
} // Ende yAusgangsKoordinate Schleife
} // Ende xAusgangsKoordinate Schleife

}
}
[/CODE]

 

[temi]

Nur ganz kurz, obwohl es mit dem Problem nichts zu tun hat:

In Java werden Packages im lower(Camel)Case und Klassen im UpperCamelCase bezeichnet. Sich an die Konventionen zu halten, macht es für alle leichter den Code zu lesen.

 

[Canis_Lupus]

Nur ganz kurz, obwohl es mit dem Problem nichts zu tun hat:

In Java werden Packages im lower(Camel)Case und Klassen im UpperCamelCase bezeichnet. Sich an die Konventionen zu halten, macht es für alle leichter den Code zu lesen.

Werde mich bei der nächsten Version daran halten!
Der Link dazu ist gut.

 

[temi]

Ansonsten hier noch ein Hinweis auf die beiden Grundregeln für Optimierungen:

1. Tun Sie es nicht.
2. (Nur für Experten): Tun Sie es noch nicht.

M.A. Jackson

 

[Mart]

Ansonsten hier noch ein Hinweis auf die beiden Grundregeln für Optimierungen:

1. Tun Sie es nicht.
2. (Nur für Experten): Tun Sie es noch nicht.

M.A. Jackson

manchmal brauchts optimierung... in javafx 100 bilder in 8k auflösung auf einer stack pane zu laden ist nicht gerade geil für den thread dann laggt alles XD

 

[Neumi5694]

Viel wirst du nicht optimieren können, du kannst die rechenaufwändigen Gewichtungsfaktoren in einer Map speichern, entweder abhängig von den beiden Punkten oder deren Abstand zueinander
Da kleine Abweichungen nicht so tragisch sind, kannst du den Abstand für die Map auch runden, damit wird der Faktor öfters verwendet.
Alternativ speichere als Key einen Wert basierend auf den Abständer der Indizes zueinander, damit hast du nur Integer-Werte, was recht effizient ist.

Würden wir hier auf Assembler-ähnlicher Ebene arbeiten, wäre das recht witzlos, da - abhängig von der CPU - die Anzahl der aufeinanderfolgenden Kommandos nicht so wichtig ist. Ein Befehl muss immer durch die ganze Pipeline durch. Wenn mehrere hintereinander folgen, dauert das nur geringfügig länger. Ob die JVM hier was optimiert, kann ich nicht sagen.

Falls die einzelnen Ergebnisse nicht voneinander abhängig sind, kannst du als nächstes auch von der strikten Schleife abweichen und das Ganze auf mehrere parallel arbeitende Prozesse aufteilen. Stream.parallelStream() ist hier bedingt geeignet, startet bis zu 3 Threads gleichzeitig. Das nächste Set an Threads wird erst aufgerufen, wenn alle 3 vorhergehenden abgeschlossen sind. Bei einer Aufgabe wie dieser mag das sogar sinnvoll sein, wo alle Threads ungefähr die selbe Laufzeit haben. Aber wenn die Laufzeit sich stark unterscheidet, ist es besser, was Anderes zu verwenden, sonst kann's passieren, dass ein lange dauernder Thread viele kurze blockiert.

 

[mrBrown]

manchmal brauchts optimierung... in javafx 100 bilder in 8k auflösung auf einer stack pane zu laden ist nicht gerade geil für den thread dann laggt alles XD

Und das wird nicht besser, wenn das das Dekodieren des Bildes optimierst (sowas ist in dem Statement gemeint), sondern in dem du deinen "Algorithmus" änderst ( = ein Bild in passender Auflösung laden).

 

[Blut1Bart]

manchmal brauchts optimierung... in javafx 100 bilder in 8k auflösung auf einer stack pane zu laden ist nicht gerade geil für den thread dann laggt alles XD

Es schreien immer die nach Optimierungen vermeiden, die es nicht können...

 

[mrBrown]

Stream.parallelStream() ist hier bedingt geeignet, startet bis zu 3 Threads gleichzeitig. Das nächste Set an Threads wird erst aufgerufen, wenn alle 3 vorhergehenden abgeschlossen sind.

Die Anzahl an Threads kann man selbst bestimmen, wen nötig. Im Normalfall sind das Anzahl Kerne - 1. Gegenseitig blockieren sollten die sich aber eigentlich nicht, die sind unabhängig.

 

[temi]

Es schreien immer die nach Optimierungen vermeiden, die es nicht können...

Ja, z. B. Joshua Bloch, der elende Stümper.

Ok, er schreibt in Effective Java: "Optimieren Sie mit Bedacht" und nicht "Optimieren Sie niemals". Vielleicht kann er es also doch.

 

[Neumi5694]

Die Anzahl an Threads kann man selbst bestimmen, wen nötig. Im Normalfall sind das Anzahl Kerne - 1. Gegenseitig blockieren sollten die sich aber eigentlich nicht, die sind unabhängig.

Nicht "gegenseitig" blockieren, es wird nur die Abarbeitung des nächsten Sets von Aufaben blockiert. Ich hatte in meinem Beispiel 7 Aufgaben, die mit der Standard-Anzahl (3) gestartet sind. Aufgabe 1,2,3 starteten sofort, 4,5,6 aber erst, sobald all von 1-3 abgearbeitet waren, 7 erst nach 4,5,6.
Von paralleler Abarbeitung würde ich erwarten, dass Aufgabe 4 sofort startet, wenn irgend eine der vorigen Aufgaben {1,2,3} beendet wurde und nicht erst, wenn alle 3 beendet wurden. Es handelte sich hier um gleichzeitig laufenden Serveranfragen (Untersuche mehrere Seiten pro Server auf bestimmte Links und untersuche die Links, das Ganze in einer eigenen Routine pro Server, die dann parallel laufen sollten) mit deutlichen Zeitunterschieden, eine Messfehler kann ausgeschlossen werden.

Meine CPU hat 12 Kerne, virtualisiert sind's 24. Da stimmt was nicht mit der Berechnung für den Normalfall. Danke für den Hinweis, dass man die Anzahl der Threads einstellen kann, werde ich mal ausprobieren.

 

[Canis_Lupus]

Hallo @Neumi5694
und @All

Wenn ich dich richtige verstehe geht es um diese beiden Zeilen.

[CODE lang="java" title="Zeitkritsch"]int abstandVonDerAusgangskoordinate = Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate);

double gewichtungAbstandfaktor = Math.pow(abstandsFaktor, abstandVonDerAusgangskoordinate);[/CODE]

Habe ich einen nachbarschaftsAbstand (wie weit entfernte Punkte sollen mindestens berücksichtigt werden) von z. B. 8 (3) werden sie bei der Variante Kugel 1649 (119) mal duchlaufen. Und das für jeden der zu berechnenden Punkte. Ein Optimierung hier hätte also einen großen Effekt.

Bei dem nachbarschaftsAbstand 8 (3) habe ich etwa 10 (5) verschiedene Abstände. Für die ließe sich der gewichteteAbstandsfaktor bestimmen und speichern. Dann muss ich aber immer noch erst den Abstand der Punkte berechnen und danach dem Abstand den gespeicherten gewichteteAbstandsfaktor zuordnen. Also was ist schneller - nach der Berechnung des Abstands den richtgen von 10 (5) Faktoren zuzuordnen oder die Math.pow(float,int) zu errechnen? Schwer zu sagen. Ich glaube das muss man testen. Oder wagt jemand eine Prognose?

Ich könnte noch einen Schritt weiter gehen. Wenn es sich um ca. 10 (5) Abstände handelt, könnt ich Listen mit den relativen Koordinaten erstellen die den selben gewichteteAbstandsfaktor haben und würde mir so auch noch die Abstandsberechnung sparen. Auch könnte ich, da sie nur einmal berechnet werden, eine bessere Anpassung an eine Kugel machen und würde so die Anzahl der Datenpunkte und der Abstände reduzieren. Diese Listen müsste ich auch nur einmal erstellen und könnte sie dann bei allen 100x100x100 Punkten nutzen. Diese Idee mit den Listen gefällt mir so garnicht. Ist aber nur nen Bauchgefühl ich habe keine wirklichen Argumente dagegen. Was ist eure Meinung?


Parallelisierung:
Die Rechnungen sind völlig unabhängig voneinander und könnten alle gleichzeitig duchgeführt werden. (Erinnert mich gerade an einen Transputer den ich im Studium mal programmiert habe ) Ohne es nachgeschlagen zu haben. Gehe ich davon aus, dass eine Parallelisierung später hinzugefügt werden kann. Im Sinne von eine Methode Parallel ausführen oder so. Da würde ich mich gerne später drum kümmern. Ich packs aber auf den Stack!


Noch weitere Vorschläge? Ich freue mich über Input

 

[mihe7]

Und das für jeden der zu berechnenden Punkte.

Ist jede ganzzahlige Koordinate im Würfel (Kantenlänge 100 bzw. 120) ein zu berechnender Punkt oder gibt es "nur" eine gewisse Anzahl an Datenpunkten, die sich in dem Würfel befinden?

 

[Canis_Lupus]

Für jeden der 100x100x100 Pukte muss der Einfluss der Anderen berechne werden. Und genau genommen soll dies nur die kleine Rechnmatrix sein. In der Datenbank kann ein Vielfaches davon liegen und ich hole mir nur immer einen Außschnitt von 100x100x100 rüber um ihn zu berechnen um mir dann den nächsten Ausschnitt vorzunehmen.

 

[mihe7]

OK. Das hört sich mir stark nach Faltung an.

 

[kneitzel]

Nicht "gegenseitig" blockieren, es wird nur die Abarbeitung des nächsten Sets von Aufaben blockiert. Ich hatte in meinem Beispiel 7 Aufgaben, die mit der Standard-Anzahl (3) gestartet sind. Aufgabe 1,2,3 starteten sofort, 4,5,6 aber erst, sobald all von 1-3 abgearbeitet waren, 7 erst nach 4,5,6.
Von paralleler Abarbeitung würde ich erwarten, dass Aufgabe 4 sofort startet, wenn irgend eine der vorigen Aufgaben {1,2,3} beendet wurde und nicht erst, wenn alle 3 beendet wurden. Es handelte sich hier um gleichzeitig laufenden Serveranfragen (Untersuche mehrere Seiten pro Server auf bestimmte Links und untersuche die Links, das Ganze in einer eigenen Routine pro Server, die dann parallel laufen sollten) mit deutlichen Zeitunterschieden, eine Messfehler kann ausgeschlossen werden.

Meine CPU hat 12 Kerne, virtualisiert sind's 24. Da stimmt was nicht mit der Berechnung für den Normalfall. Danke für den Hinweis, dass man die Anzahl der Threads einstellen kann, werde ich mal ausprobieren.

Also generell muss man einmal schauen, was Du genau gemacht hast. Ohne ganz genaue Details kann man dazu nur relativ wenig sagen, außer eben auf die Grundlagen einzugehen.

Bei Streams kann man immer wieder Angelika Langer bringen denke ich mal:

AngelikaLanger.com - Effective Java - Angelika Langer Training/Consulting

www.angelikalanger.com

Da wird eine Grundlage etwas erläutert.

Dann ist zu diesem Fork-Join-Framework für uns ggf. relevant: Es gibt ein ForkJoinPool. Dieser wird verwendet von so einem Parallelem Stream. Kann wichtig sein, wenn man ggf. mehrere parallele Tätigkeiten hat also z.B. zwei Threads die dann beide irgendwas mit parallelen Streams machen wollen oder so ...

Die Poolgröße kann man dann natürlich anpassen:
-Djava.util.concurrent.ForkJoinPool.common.parallelism=8

Und man kann natürlich einen parallelen Stream in einem dedizierten, neuen ForkJoinPool laufen lassen.

ABER: Das ist natürlich ein Implementationsdetail. Ob eine Implementierung dies so macht oder nicht muss man an der konkreten Implementierung anschauen. Das ist etwas, das z.B. bei Oracle Java 8 so ist. Andere Anbieter oder andere Versionen können es prinzipiell anders handhaben!

Und wenn man dann parallel etwas macht, dann wird nach jedem beendeten Thread direkt der nächste gestartet. Das habe ich mal einfach als ein kleinen Test schnell zusammen geschrieben:

import java.util.List;

public class Test {
    public static void main(String[] args) {
        List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
                .parallelStream()
                .forEach(Test::doSomething);
    }

    public static void doSomething(int value) {
        int wait = (int) (Math.random()*1000);
        System.out.println("Thread STARt for " + value + " Waiting: " + wait + " ms");
        try {
            Thread.sleep(wait);
        } catch (InterruptedException ex) {}
        System.out.println("Thread END for " + value + " Waiting: " + wait + " ms");
    }
}

[CODE title="Ausgabe"]Thread STARt for 13 Waiting: 15 ms
Thread STARt for 9 Waiting: 197 ms
Thread STARt for 7 Waiting: 536 ms
Thread STARt for 12 Waiting: 28 ms
Thread STARt for 3 Waiting: 546 ms
Thread STARt for 18 Waiting: 68 ms
Thread STARt for 8 Waiting: 735 ms
Thread STARt for 2 Waiting: 112 ms
Thread END for 13 Waiting: 15 ms
Thread STARt for 15 Waiting: 483 ms
Thread END for 12 Waiting: 28 ms
Thread STARt for 11 Waiting: 524 ms
Thread END for 18 Waiting: 68 ms
Thread STARt for 20 Waiting: 370 ms
Thread END for 2 Waiting: 112 ms
Thread STARt for 1 Waiting: 134 ms
Thread END for 9 Waiting: 197 ms
Thread STARt for 10 Waiting: 78 ms
Thread END for 1 Waiting: 134 ms
Thread STARt for 5 Waiting: 889 ms
Thread END for 10 Waiting: 78 ms
Thread STARt for 6 Waiting: 588 ms
Thread END for 20 Waiting: 370 ms
Thread STARt for 19 Waiting: 819 ms
Thread END for 15 Waiting: 483 ms
Thread STARt for 14 Waiting: 18 ms
Thread END for 14 Waiting: 18 ms
Thread STARt for 17 Waiting: 581 ms
Thread END for 7 Waiting: 536 ms
Thread STARt for 16 Waiting: 881 ms
Thread END for 3 Waiting: 546 ms
Thread STARt for 4 Waiting: 408 ms
Thread END for 11 Waiting: 524 ms
Thread END for 8 Waiting: 735 ms
Thread END for 6 Waiting: 588 ms
Thread END for 4 Waiting: 408 ms
Thread END for 17 Waiting: 581 ms
Thread END for 5 Waiting: 889 ms
Thread END for 19 Waiting: 819 ms
Thread END for 16 Waiting: 881 ms

Process finished with exit code 0[/CODE]

Man erkennt also recht schön: 8 Threads wurden gestartet bei mir (Das entspricht auch der Anzahl meiner "virtuellen CPUs") und immer, wenn ein Thread beendet wurde, wurde direkt der nächste gestartet.

Das einfach einmal zu der betrachtung von paralleler Streams. Ich selbst erachte diese als eine sehr eifnache Möglichkeit, Dinge parallel abzuarbeiten. Man kann darüber in der Regel gut und schnell Dinge auf sehr einfache und gut lesbare Weise parallelisieren.

 

[Blender3D]

int abstandVonDerAusgangskoordinate = Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate);

Dir ist schon klar, dass Du damit nicht wirklich den Abstand zwischen den beiden Koordinatenpunkten berechnest?
Beispiel:
Ausganspunkt: A=( 0,0,0 );
Zielpunkt: B =(1,1,1);
echter Abstand: 1,73.. bei Dir 3
Zielpunkt: C = (3,0,0);
echter Abstand: 3.. bei Dir 3

 

[mrBrown]

Dir ist schon klar, dass Du damit nicht wirklich den Abstand zwischen den beiden Koordinatenpunkten berechnest?

Abstand mit Manhattan Metrik

 

[Canis_Lupus]

int abstandVonDerAusgangskoordinate = Math.abs(xKooedinate - xAusgangsKoordinate) + Math.abs(yKooedinate - yAusgangsKoordinate) + Math.abs(zKooedinate - zAusgangsKoordinate);

Dir ist schon klar, dass Du damit nicht wirklich den Abstand zwischen den beiden Koordinatenpunkten berechnest?
Beispiel:
Ausganspunkt: A=( 0,0,0 );
Zielpunkt: B =(1,1,1);
echter Abstand: 1,73.. bei Dir 3
Zielpunkt: C = (3,0,0);
echter Abstand: 3.. bei Dir 3

Erstmal ein gutes Neues an alle.

Wenn ich die Manhattan Metrik nehme spare ich mir das Rechnen mir double, drei mal Quadrieren und einmal Radizieren zu Lasten, dass ich 3 mal den Betrag bei Integer Zahlen bilde (Quadrratzahlen von Reellen Zahlen sind positiver und somit ist der Radiant positive). Und @Blender3D „dir ist schon klar, dass“ ;-) die Überschrift lautet, „Ein Algorithmus soll schneller werden“.

@mrBrown den Namen Manhattan Metrik dafür kannte ich nicht. Wieder was gelernt.

 

[Canis_Lupus]

@Neumi5694, @mrBrown und @kneitzel

Es ist gut, dass Ihr mich mit dem Thema Parallelisierung „angefixt“ habt. Duch das kleine Programm von kneitzel im Posting #16 ist das Thema greifbarer geworden. Die Parallelisierung wird für mein Programm die mit Abstand größte Beschleunigung werden. Aber das Thema ist ganz schön mächtig. Und da es nicht meine Art ist etwas nur irgendwie zum laufen zu bringen, muss ich mich da später reinarbeiten. Aber Ihr habt mich „angefixt“ und das wird ein riesen Spaß werden.
Euren weiteren Diskussionen dazu hier werde ich gerne folgen.

 

[mihe7]

Ich wäre nach wie vor dafür, eine auf Faltung optimierte Lib zu verwenden

 

[Canis_Lupus]

@mihe7
Nach deinem ersten Tipp vor ein paar Tagen hatte ich bei Faltung nachgeschlagen und das sah nach einer Mittelwertberechnung aus. Dann muss ich mir das wohl nochmal und diesmal gründlicher anschauen. Das kann, da ich ab Montag wieder arbeite, ein paar Tage dauern, aber ich gebe dir ne Rückmeldung oder werde vielleicht Fragen haben.

 

[mihe7]

Kann auch sein, dass ich daneben liege, aber soweit ich das Problem verstehe, geht es darum, die Summe gewichteter Werte zu berechnen.

Einfaches Beispiel (1D-Fall): nehmen wir mal die Zahlen 1,2,3,4,5,6 und jetzt soll für einen Wert an Position i (w_i) der "Einfluss" berechnet werden, z. B. indem wir sagen, dass der Wert an Position i-1 mit 1/2 und der Wert an Position i-2 mit 1/4 Einfluss nimmt. Dann haben wir ein Fenster [0,25, 0,5, 0] das wir über die Zahlen schieben und dabei die Summe der Produkte bilden:

1    2    3    4    5    6
0,25 0,5  0 --> Einfluss wäre 1*0,25 + 2*0,5 + 3*0
     0,25 0,5  0 --> Einfluss wäre 2*0,25 + 3*0,5 + 4*0

Das wäre eine Faltung. Im 2D-Fall geht man in beide Richtungen (man berechnet also den Einfluss auf den Mittelpunkt), z. B. mit einer Faltungsmatrix

0,25 0,5 0,25
0,5   0  0,5
0,25 0,5 0,25

Dafür gibt es in jedem Fall optimierte Bibliotheken (z. B. nativer Code, außerdem kann man eine Faltung durch schnelle Fourier-Transformation in O(n log n) statt in O(n²) durchführen). Unsicher bin ich mir, was den 3D-Fall betrifft. Das sollte aber durch Hintereinanderschaltung von 2D-Fällen erreichbar sein.

 

[Canis_Lupus]

@mihe7
Du liegst mit Faltung (Convolution) richtig. Habe mir das nochmal angeschaut und bin gespannt, ob das ne Beschleunigung gibt, wir werden sehen. In dem Zusammenhabng habe ich auch einige Ideeen für die Behandlung der Randpunkte gefunden.

 

[mihe7]

ob das ne Beschleunigung gibt

Das Ergebnis würde mich auch interessieren