Optimierung einer Berechnung

[Network]

Hi,

ich habe ein Spiel programmiert und muss innerhalb von wenigen Millisekunden an die 1000x1000 Berechnungen von einzelnen Spielfeldern durchführen.

Meine erste überlegte Variante ging schief und war viel zu langsam.

Ich weiss jetzt nicht welche Variante ich als nächstes Einsetzen sollte, vieleicht hat ja jmd. eine Entscheidungshilfe für mich.

1. Alle Felder in eine Liste (Vector/ArrayList) packen, mit einem einzigartigen Namen (Position) und dem zu verwertenden Wert.
- Nachteil: Da ich immer wieder die Nachbarfelder abfragen muss, muss ich immer wieder die gesammte Liste durchgehen und nach den Nachbarfeldern suchen.
- Vorteil: Jedoch muss ich in der Liste nicht alle Spielfelder aufnehmen sondern nur die zu berechnenden (steigende Zahl)

2. Alle Felder als Array[1000][1000] speichern.
- Nachteil: Ich muss zu jedesmal alle Felder überprüfen
- Vorteil: Ich weiss an welcher Stelle die Nachbarfelder sind

Ich weiss nicht für welche Methode ich mich entscheiden sollte... Ich möchte halt nicht eine völlig neue Methode ins Spiel implementieren, um später feststellen zu müssen, dass sie wieder viel zu langsam ist.
Besonderst ist halt die Frage ob Arrays schneller sind als Vectoren/ArrayLists

Vielen Dank schonmal

 

[bERt0r]

Du könntest eine Klasse Spielfeld machen und dem Feld seine 8 Nachbarn als Membervariablen zuweisen.

 

[Marcinek]

Das hängt davon ab, was auf den Feldern ist und welche Berechnungen es sind.

Kannst du es nicht Clustern und die Berechnungen in vier Threads machen?

Sind alle Felder gleichzeitig Sichtbar? - Wenn nein, sollte man nur den Sichtbaren bereich neu berechnen.

Gruß,

Martin

 

[Marco13]

Du solltest mehr Infos posten (was für Felder, was für Abfragen...?). Im Allgemeinen sind Arrays schon das schnellste, was man verwenden kann, und speziell wenn die Größe sich nicht ändert sollte man bei Zeitkritischen Interna schon Arrays verwenden (nur nicht über getter nach draußen geben oder so...)

 

[Landei]

Wie mein Vorredner sagte, sind hier Arrays angesagt. Um sich die Tests auf Randfelder zu sparen, wird oft ringsherum um das eigentliche Spielfeld ein "Rahmen" ungenutzer, leerer, blockierender u.s.w. Felder benutzt.

 

[Network]

-> Das ganze Prinzip zu erklären ist recht schwierig. In etwa muss so etwas wie bei "conways Game Of Life" berechnet werden. Es trifft das Spielprinzip zwar nicht, war aber meine ursprüngliche Überlegung das ganze in etwa so umzusetzen.

Du könntest eine Klasse Spielfeld machen und dem Feld seine 8 Nachbarn als Membervariablen zuweisen.

Vielen Dank, logisch, beschleunigt das ganze natürlich um einiges.

Das hängt davon ab, was auf den Feldern ist und welche Berechnungen es sind.
Kannst du es nicht Clustern und die Berechnungen in vier Threads machen?
Sind alle Felder gleichzeitig Sichtbar? - Wenn nein, sollte man nur den Sichtbaren bereich neu berechnen.

-> 4 verschiedene Threads? Da sich die Threads abwechseln und Java leider auch keine Multicoreberechnungen unterstützt... sind die 4 Threads nicht genausoschnell wie einer?
-> Letzten Punkt habe ich bereits abgehaakt. Jedenfals werden die Berechnungen abgespeckt.

Du solltest mehr Infos posten (was für Felder, was für Abfragen...?). Im Allgemeinen sind Arrays schon das schnellste, was man verwenden kann, und speziell wenn die Größe sich nicht ändert sollte man bei Zeitkritischen Interna schon Arrays verwenden (nur nicht über getter nach draußen geben oder so...)

Ok, Array habe ich jetzt eingesetzt. Wobei ich etwas neugierig bin was das getter angeht. So schlimm?
Jedem Objekt, dass das Array unbedingt benötigt, habe ich die Addresse des Arrays übergeben.

 

[Fu3L]

-> 4 verschiedene Threads? Da sich die Threads abwechseln und Java leider auch keine Multicoreberechnungen unterstützt... sind die 4 Threads nicht genausoschnell wie einer?

Das würde ja Threads bis auf bei nicht-blockierenden GUIs ad absurdum führen und noch mehr sowas neues wie das fork&join-Framework wie Zeitverschwendung erscheinen lassen^^

Ich kann nicht sicher sagen, dass du unrecht hast, aber es würde mich sehr wundern, wenn es stimmen würde 😉

 

[theuserbl]

Im Allgemeinen sind Arrays schon das schnellste, was man verwenden kann, und speziell wenn die Größe sich nicht ändert sollte man bei Zeitkritischen Interna schon Arrays verwenden (nur nicht über getter nach draußen geben oder so...)

Ok, Array habe ich jetzt eingesetzt. Wobei ich etwas neugierig bin was das getter angeht. So schlimm?

Die Aussage mit dem Getter und Setter finde ich auch sehr interessant.
Das klingt so, als sollte man objektorientiert und mit Setter und Getter programmieren, wenn das Programm leicht lesbar und wartbar sein soll.
Will man jedoch performante Programe schreiben, sollte man hingen möglichst nur statische Methoden erstellen und nutzen und schön prozedural programmieren. 🙂

Grüße
theuserbl

 

[Fu3L]

Ich verstehe es so, als wenn man sein Array nicht per Getter nach außen geben sollte, weil sonst jeder drin rumwursten und alles verändern kann und das zu Chaos führt. Man muss also nach außen das Array wieder abstrahieren.
Also sowas: getInformation(Point xy). Die Klasse, die das Array beinhaltet, sucht dann anhand der Koordinaten die Information aus dem Array.

 

[theuserbl]

@ Fu3L: Oh man, das wird jetzt etwas off topic. Aber als ich Dein Posting las, mußte ich erst mal lachen... 😀

Ich verstehe es so, als wenn ...

Der Witz ist: Da schreibt ein Forumsmitglied etwas ins Forum und die restlichen Forenmitglieder fangen an zu interpretieren, wie es gemeint sein könnte. :lol:

Grüße
theuserbl

 

[Marco13]

Ja, und was ist daran so lustig? (Hm... ich bin wohl humorlos... und drücke mich unklar aus). Ich meinte nur, dass es Nachteilhaft sein kann, wenn man sowas macht wie

class Board {
    private int array[][];
    public int[][] getArray() { return array; }
}

und jeder dann sowas macht wie

void drawSomething() {
    drawLine(board.getArray()[12][45], board.getArray()[4][67]);
    ...
}

Einerseits, weil jeder darin rumpfuschen kann, aber der wichtigere Grund ist, dass man auf diesen Array festgelegt ist: Bei einem 1000x1000-Feld würde überall davon ausgegangen, dass das ein [c]int array[1000][1000] [/c] ist. Wenn es irgendwann mal ein int[1000*1000] oder gar einen long[][] werden soll, oder noch mehr, oder wenn man in Anlehung an Landei's Hinweis dann einen 1002x1002-Array verwenden will, um ein 1000x1000-Feld zu modellieren, ist man ge'screw'ed....

 

[tagedieb]

Das würde ja Threads bis auf bei nicht-blockierenden GUIs ad absurdum führen und noch mehr sowas neues wie das fork&join-Framework wie Zeitverschwendung erscheinen lassen^^

Ich kann nicht sicher sagen, dass du unrecht hast, aber es würde mich sehr wundern, wenn es stimmen würde 😉

Hab mal von einem Projekt gehoert, da haben sie eine ambitionierte Multithreadingloesung entwickelt und alles schoen ueber die Konfiguration gesteuert. Am Schluss mussten Sie leidlich feststellen, dass die Sofware mit nur 1 Thread am schnellsten laeuft, da das Zielsytem nur einen Prozessor hatte.... :autsch:

 

[parabool]

Die Position der zu berechnenden Felder im Array könnte man in einer Liste speichern.
Wenn Du z.B. nur 10 Felder hast musst Du auch nur diese im Array abfragen.

Nebenbei: Wenn sich bei den Berechnungen die Zustände der Felder ändern können bzw. Felder wegfallen/hinzukommen, muss der vorherige Zustand der Matrix berücksichtigt werden.

(Bei Game Of Life: Alle Felder beziehen sich bei den Berechnungen auf dieselbe Generation/Berechnungsdurchlauf)

 

[Marco13]

Am Schluss mussten Sie leidlich feststellen, dass die Sofware mit nur 1 Thread am schnellsten laeuft, da das Zielsytem nur einen Prozessor hatte.... :autsch:

Man kann davon ausgehen, dass die Anzahl der Kerne in einem Desktop-PC sich alle 18 Monate verdoppeln wird. Im Moment sind 4 normal, in 1.5 Jahren werden 8 normal sein....

 

[bERt0r]

Zu deiner Ursprünglichen frage bzgl dem Game of life:
Du könntest ein 1000x1000 boolean Array und ein Hashset machen, in dem Du die Koordinaten der lebenen Zellen speicherst, z.b. als Point.
Pro zyklus iterierst du das Hashset durch, angrenzende Punkte kannst du bequem über das Array überprüfen. Das hashset verhindert auch, dass du Zellen mit gleichen Koordinaten doppelt hineinspeicherst.

 

[Network]

Einerseits, weil jeder darin rumpfuschen kann, aber der wichtigere Grund ist, dass man auf diesen Array festgelegt ist: Bei einem 1000x1000-Feld würde überall davon ausgegangen, dass das ein [c]int array[1000][1000] [/c] ist. Wenn es irgendwann mal ein int[1000*1000] oder gar einen long[][] werden soll, oder noch mehr, oder wenn man in Anlehung an Landei's Hinweis dann einen 1002x1002-Array verwenden will, um ein 1000x1000-Feld zu modellieren, ist man ge'screw'ed....

Done 😉

Die Position der zu berechnenden Felder im Array könnte man in einer Liste speichern.
Wenn Du z.B. nur 10 Felder hast musst Du auch nur diese im Array abfragen.

Nette Idee die ich auch hatte. Da ich jedoch eh jedes Feld durchgehe um das Spielfeld zu zeichnen, hab ich darin auch die Abfrage für jedes Feld integriert, fals notwendig - was sich entscheidet ob das Feld aktiv ist oder nicht.

Zu deiner Ursprünglichen frage bzgl dem Game of life:
Du könntest ein 1000x1000 boolean Array und ein Hashset machen, in dem Du die Koordinaten der lebenen Zellen speicherst, z.b. als Point.
Pro zyklus iterierst du das Hashset durch, angrenzende Punkte kannst du bequem über das Array überprüfen. Das hashset verhindert auch, dass du Zellen mit gleichen Koordinaten doppelt hineinspeicherst.

Auch eine sehr gute Idee, lässt sich bei mir leider nicht umsetzen. Da mein Spielprinzip weitaus komplizierter ist oder wird 🙂


Ich habe jetzt die meisten Tipps soweit es möglich war(evt. leicht modifiziert) ins Game eingebaut und ich muss sagen: TOP! :toll:
Es ist wunderbar schnell... leider kommt jetzt die repaint-methode nicht mehr mit, während repaint noch beim zeichnen ist, wird repaint bis zu 10 mal erneut aufgerufen . Ich wusste nicht, dass repaint ein eigener Thread ist. Tja extrem schnell ist dann halt doch manchmal ein Nachteil 😀

Ich Bedanke mich herzlich.

 

[Fu3L]

Rufst du zwischenzeitlich immer Thread.sleep(someTimeInMillis) auf? Das empfiehlt sich (insbesondere auf Einkernprozessoren). Dann kommt auch der andere Thread* mit dem Zeichnen hinterher 😉
Wenn du eh nicht schneller malen kannst, nützt es ja auch nichts, den Spielzustand öfters zu berechnen^^

*: Zweifle gerade wegen seines Namens daran, ob das der Event Dispatch Thread macht, wovon ich eigentlich ausging?^^

 

[bERt0r]

Also ich bin ja mehr ein Fan von yield(), da kriegst du auch keine InterruptedExceptions.