Autor Beitrag
Master_of_Magic
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56

Win 98, Win XP
D6 Pers, D2005 Arch
BeitragVerfasst: Sa 04.03.06 21:43 
Ich bräuchte ein paar Optimierungs-Tipps bezgl. eines von mir erstellen Algorithmus. Es geht um folgendes:

Eine Galaxie ist in Koordinaten unterteilt. Die Koordinaten sind x,y und z - wobei z einen anderen Maßstab hat. Ein Raumschiff braucht eine gewisse Zeit um vom Startpunkt (0|0|0) zu einem Zielpunkt zu fliegen. Diese Flugzeit lässt sich mit der Funktion fxGF(...):real ermitteln. Nun möchte ich aber passende Koordinaten zu einer bestimmten Flugzeit. Da sich die Flugzeitberechnung nicht einfach so umkehren lässt (die ist etwas komplexer), muss ich quasi alle Koordinaten abarbeiten und schauen, ob die Flugzeit in einem bestimmten Bereich liegt. Dabei ermittlte ich das optimale Ergebnis im Bezug auf die Spritkosten, die mit der Entfernung sowie der Geschwindigkeit steigen.

Die Prozedur sieht so aus:
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
procedure TForm1.calcsave(size,speed,minflugzeit,maxflugzeit,maxdz,sx,sy,sz:integer; jet:boolean; out rx,ry,rz,rproz,count,jetplanet:integer; out rt:real);
var Prozent,dx,dy,dz,test,i:integer;
checktime:real;
begin
count:=0;         //zählt die Schleifendurchläufe
gauge1.MaxValue:=(size*size+size)*80;   //Fortschrittsanzeige
For Prozent:=1 to 10 do     //Geschwindigkeit kann in 10%-Schritten geregelt werden
begin
  If not (rt=999and not (rt=0then Exit; //Gibt es schon ein Ergebnis, macht das Weiterrechnen mit einer
  [...]              //höheren Geschw. keinen Sinn mehr ...
  For dx:=0 to size do
  begin
    gauge1.Progress:=count;
    For dy:=0 to dx do
    begin
      for dz := 0 to maxdz do
      begin
        inc(count,1);
        checktime:=fxGF(0,0,0,dx,dy,dz,jet)/(speed*(prozent/10));
        if (checktime>minflugzeit) and (checktime<maxflugzeit) then
        begin 
          if ((fxGD(0,0,0,dx,dy,dz)*(prozent/10))<rt) then
          begin
            rx:=dx;
            ry:=dy;
            rz:=dz;
            rproz:=prozent;
            rt:=fxGD(0,0,0,dx,dy,dz)*(prozent/10); //Spritkosten
          end;
        end;
      end;
    end;
  end;
end;
end;


Wie man sieht hab ich die Anzahl der Koordinaten bereits auf 1/8 reduzieren können, da es ja jeweils acht Koordinatenpaare (x|y) gibt, die vom Ursprung einen bestimmten Abstand haben. Die Z-Koordinate lassen wir mal beiseite ...

Das Problem: Mit size=149 und maxdz=16 ergeben sich 1.812.000 Schleifendurchläufe ...

Im Prinzip liegen die gewünschten Ergebnisse ja Kreisförmig um den Ursprung (je nach Prozent). 90% aller Koordinaten kommen also gar nicht in Frage ...

Ich hoff mal, ihr habt mein Problem verstanden und könnt mir helfen ... :wink:
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Sa 04.03.06 22:20 
Bist du sicher, dass du für die Berechnung 2 Millionen Schleifendurchläufe brauchst? Wie geht die Rechnung?
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Sa 04.03.06 22:49 
Die Funktion fxGD wird bei Dir mehrfach aufgerufen. Funktionsergebnis des ersten Aufrufs cachen und an der zweiten Stelle gleich wiederverwenden.

Insgesamt wäre es glaube hilfreich, wenn Du uns auch kurz die Funktionen fxGF und fxGD geben könntest. Insgesamt scheint hier nämlich noch einiges optimierbar zu sein.

Ein Beispiel:

Deine Funktion prüft mit folgender Häufigkeit die Umgebenden Punkte:

ausblenden Quelltext
1:
2:
3:
4:
5:
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1


Wobei der Mittlere Punkt dein Ausgangspunkt ist.

In der Mathe-Vorlesung hat uns unser Prof da mal eine relativ gute Möglichkeit gezeigt: Binomiale Zahlendarstellung ;-) Mit einigen änderungen kannst Du damit gewährleisten, dass jeder Punkt nur einmal abgefragt wird. Die genauen Details hier aber zu erklären, geht in diesem Post zu weit, erklär ich Dir aber gern auf weitere Nachfrage.

Weiterhin: Prozent/10) berechnest Du mehrfach: Auch einmal berechnen und dann gecachtes Ergebnis nutzen ...

Ansonsten wie gesagt: Gib mir einmal die besagten fehlenden Funktionen, vielleicht findet sich da auch noch einiges für die Optimierung.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Master_of_Magic Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56

Win 98, Win XP
D6 Pers, D2005 Arch
BeitragVerfasst: Sa 04.03.06 23:43 
@delfiphan
Wie gesagt, ich sehe keine anderen Möglichkeit als das Ausprobieren-Prinzip. Die entsprechenden Formeln sind unten. Dadurch, dass bei der Flugberechnung die Flugzeit nochmal um Flugstrecke*8 gekürzt wird, habe ich bisher keine sinnvolle Möglichkeit gefunden, das Ganze umzukehren ...

@BenBe
Die Funktionen fxGD und fxGF sind leider ziemlich grausam zu lesen, da es sich um Java-Script-Umsetzungen handelt ... ;-)
Ich glaube nicht, daß man dort viel verbessern kann, höchstens das eine oder andere Ausklammern ...

Hier der entprechende Abschnitt:
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
function TForm1.ixSD(s,z:Integer):Integer;
var size:integer;
begin
  if argala.ItemIndex=1 then size:=300 else size:=100;
  result:= Math.min(Math.Min(abs(s mod size - z mod size),abs(z mod size - (s mod size + (size-1)))),abs(z mod size - (s mod size -(size-1)))); //subtraktion 99 durch 299 ersetzt
end//kürzeste Entfernung --> bei Randposition

function TForm1.fxGD(sx,sy,sz,zx,zy,zz:integer):real;
begin
  if (sx=zx) and (sy=zy) then
    result:= abs(sz-zz)*0.020 //im gleichen System nur z-Abstand
  else
    result:= ((((hypot(ixSD(sx,zx),ixSD(sy,zy))*100))/100)-1) + (100+(abs(sz-zz)*1.2))/100;
end//Gesamtabstand der Planeten (Hypotenuse+z-Abstand)

function TForm1.fxGF(sx,sy,sz,zx,zy,zz:integer;jetstream:boolean):real;
var fFlugzeit,fStrecke:real;
begin
  if (sx=zx) and (sy=zy) and (sz=zz) then
  begin
    result:= 320000//selber Planet --> Standarddauer  fFlugZeit = 60*(fxGD(sx,sy,sz,zx,zy,zz)/5.0+1.0);
    if jetstream then result:=result/2;
    exit;
  end;
  fStrecke:=fxGD(sx,sy,sz,zx,zy,zz);
  fFlugZeit := 60*(fStrecke/5.0+1.0);
  if (sx<>zx) or (sy<>zy) then fFlugZeit := fFlugZeit+30.0//anderes System --> mehr Flugzeit
  fFlugZeit := fFlugZeit-(hypot(ixSD(sx,zx)*1.0,ixSD(sy,zy)*1.0)*8.0);//Zeit um Flugstrecke*8 kürzen?
  if jetstream then
  begin
    if fStrecke>40 then result:=(fFlugZeit * 640000)/roundTo((fStrecke/40)+1,-2)
    else result:= fFlugZeit * 320000
  end
  else result:= fFlugZeit * 640000;
  if argala.ItemIndex=2 then result:=round(result/3.2);
end;


Im Bezug auf das cachen hast du allerdings recht, das könnte ich machen. Werd morgen gleich mal testen, obs was bringt.

Und was die Häufigkeit der Punkte angeht:
Bist du dir mit deiner Verteilung sicher? Folgendes ist gegeben:

1. die Galaxie hat die Größe 299*299
2. wird der Rand überschritten, gehts auf der anders Seite weiter. Der Abstand von (299|15) und (001|15) ist also 1 --> dafür sorgt die Funktion ixSD
3. ein zentriertes Koordinatensystem ergibt einen Maximalen x/y-Wert von 149
4. Vereinfacht sieht die x/y-Schleife ja so aus:
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
For x:=0 to 149 do
begin
  For y:=0 to x do
  begin
  end;
end;


Wenn ich mich nicht vertan habe, müsste dadurch die Hälfte des ersten Quadranten durchgerechnet werden, also
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
       y
       |     1
       |    11
       |   111
       |  1111
       | 11111
       |111111
-------|-------x
       |
       |
       |

und damit müsste ja das ganze System abgedeckt sein, da sich die restlichen Punkte durch Spiegelung erreichen lassen ...
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 05.03.06 00:49 
hmmm, bzgl. der Quadranten hast Du recht, hab da was übersehen gehabt. Du hättest damit aber trotzdem die diagonalen immer doppelt besucht. Dassollte aber weniger ins gewischt fallen.

Deine Funktion ixSD kann aber noch stark optimiert werden.

Du hast ATM dort nämlich eine Doppeldeutigkeit drin, die Dir das Leben unnötig schwer macht: Nimm die Werte s und z doch einfach Nullbasiert, dann kannst Du bei Mod wesentlich einfacher Rechnen (MOD ist eine Division und daher IMMER langsam):

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
function TForm1.ixSD(s,z:Integer):Integer;
var size:integer;
    dist:integer;
begin
  if argala.ItemIndex=1 then size:=299 else size:=99;
  //s := s - 1; //Entfällt, weil's sich aufhebt
  //z := z - 1; //Das hier auch ...
  dist := abs(s - z) mod size; 
  if dist < size - dist then
    result := dist
  else
    result := size - dist;
end//kürzeste Entfernung --> bei Randposition


Ansonsten seh ich nur sehr unübersichtlichen Source ... Schonmal was von DelFor gehört *g*

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: So 05.03.06 18:11 
Also ich weiss jetzt nicht ob ich was falsch verstanden hab. Du schreibst ja selbst:
Zitat:
Im Prinzip liegen die gewünschten Ergebnisse ja Kreisförmig um den Ursprung (je nach Prozent).

Aber? Oder wo liegt jetzt die Schwierigkeit? Eine Kugelschale zu voxelisieren?
Master_of_Magic Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 56

Win 98, Win XP
D6 Pers, D2005 Arch
BeitragVerfasst: So 05.03.06 21:05 
@BenBE
Deine optimierte Funktion funktioniert prima. Ich hätte nicht gedacht, dass das so einfach geht, da die Berechnung 'über den Rand' die jeweilige Rand- und Nullposition überspringen muss... aber es klappt prima und ist immerhin 25% schneller als vorher.

... und was DelFor angeht, davon hab ich wirklich noch nix gehört ;-) schätze aber mal, dass es sich um eine Art Sprach-Konsortium wie das W3C bei HTML handelt ... dazu kann ich nur wiederholen, dass die Funktionen nicht von mir sind sondern nur 1:1 in Delphi umgesetzt wurden. Und du kannst mir glauben, wenn ich sage: Das Javascript sah noch schlimmer aus... :D

@delfiphan
Genau da liegt das Problem:
1. Kennt nicht mal mein Duden das Wort 'voxelisieren' :wink:
2. Hab ich keinen Ansatz, wie ich meinen Algorithmus so umbauen kann, dass er nur diesen Kreisbereich berechnet und die Koordinaten dazwischen überspringt. Ich weiß ja den Radius nicht und der 'schwankt' ja auch leicht, da die Koordinaten ganzzahlig sind ...
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: So 05.03.06 21:30 
Okay vielleicht lass ichs lieber sein. Noch einen Versuch ;)

Dich interessiert ja eh nur *ein* Resultat, welches im vorgegebenen Bereich liegt... Wie ich sehe nimmst du ja einfach das erst beste Resultat...

Wieso also die ganze Rechnerei? Ist das Problem vielleicht, dass die z-Koordinate nicht gleich skaliert ist wie x/y? Also Bestünde die Aufgabe darin, eine Kugel mit einem Ellipsoid zu schneiden und einen beliebigen Schnittpunkt in die Spritkosten-Funktion zu übergeben?
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 05.03.06 21:38 
user profile iconMaster_of_Magic hat folgendes geschrieben:
@BenBE
Deine optimierte Funktion funktioniert prima. Ich hätte nicht gedacht, dass das so einfach geht, da die Berechnung 'über den Rand' die jeweilige Rand- und Nullposition überspringen muss... aber es klappt prima und ist immerhin 25% schneller als vorher.

Naja, ich wollte nicht gleich mit der ASM-eule ankommen ;-) Meist bringt es auch schon viel, seinen Pascal-Source sauber zu schreiben ;-)

user profile iconMaster_of_Magic hat folgendes geschrieben:
... und was DelFor angeht, davon hab ich wirklich noch nix gehört ;-) schätze aber mal, dass es sich um eine Art Sprach-Konsortium wie das W3C bei HTML handelt ... dazu kann ich nur wiederholen, dass die Funktionen nicht von mir sind sondern nur 1:1 in Delphi umgesetzt wurden. Und du kannst mir glauben, wenn ich sage: Das Javascript sah noch schlimmer aus... :D

@DelFor: Nope, ist einfach ein Tool, mit dem man sauigen Source sehr schnell übersichtlicher machen kann.

Schau Dir diesbezüglich mal den Econos-Standard an, der dort verlinkt ist. Wenn man sich halbwegs daran hält, ist der Source sowohl übersichtlich, als auch relativ schnell. Für Spezial-Optimierungen gibt's im Inet relativ vielee Pages. Wichtig ist bei deinem Source aber vor allem erstmal: Mit weniger Variablen mehr ausführen.

Die CPU hat 3 Register zur freien Verwendung für den Compiler, sowie 3 weitere, die bedingt freigegeben sind. Um nun zu verhindern, dass der Compiler Daten in den RAM auslagert, was zwangsläufig zum Ausbremsen des Programms führt, sollte man dafür sorgen, dass man immer nur mit 2 bis 3 Variablen gleichzeitig arbeitet (Bei Gleitkomma sieht das nochmal etwas anders aus). Weiterhin nutzt die CPU Caching um auf häufig benötigte Daten schnell zugreifen zu können. Dieser Cache ist aber auf bestimmte größen beschränkt - um ihn also richtig nutzen zu können, muss man bei der Arbeit mit Arrays immer in bestimmten Datenblöcken (von ~64KB) bleiben, da jegliche Zugriffe außerhalb unnötig bremsen.

Weiterhin kannst Du in deiner Routine noch Geschwindigkeit rausholen, wenn Du die Zugriffe auf das Array nicht jedes mal neu Berechnen lässt, sondern mit einem Pointer das zu bearbeitende Element einmal fixierst und einfach im nächsten Schritt die Position mit Inc oder durch Setzen des Zeigers anpasst. Auch das bringt nochmal wertvolle Zyklen ;-)

user profile iconMaster_of_Magic hat folgendes geschrieben:
@delfiphan
Genau da liegt das Problem:
1. Kennt nicht mal mein Duden das Wort 'voxelisieren' :wink:

Dann klär uns mal auf *g*

user profile iconMaster_of_Magic hat folgendes geschrieben:
2. Hab ich keinen Ansatz, wie ich meinen Algorithmus so umbauen kann, dass er nur diesen Kreisbereich berechnet und die Koordinaten dazwischen überspringt. Ich weiß ja den Radius nicht und der 'schwankt' ja auch leicht, da die Koordinaten ganzzahlig sind ...


Das könntest Du halbwegs gut über die Binomiale Zahlendarstellung machen. Ansonsten: Radius berechnen (Dazu müsste ich die Entfernungsformeln mir mal genauer angucken) und dann die Minimale Entfernung und die maximale Entfernung Einschränken.
Damit könnte man dann über den Geometrischen Pythagoras die Zutreffenden Punkte ermitteln. Mehr dazu auf Nachfrage ^^

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
zemy
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 207

Win XP Prof.
D7
BeitragVerfasst: Sa 11.03.06 20:22 
Ne andere Idee: wie währe es mit (einer zugegeben etwas größeren) LookUp-Tabelle mit 800'000 Einträgen? Die sortierst du dann einfach nach der Entfernung.

Wenn du Jetzt nen Plani zum Saven suchst, gibst du eine Min-Time ein. Mit der kannst du dann die Mindestdistanz errechnen. Dann suchst du in der Liste den ersten Wert > der Mindestdistanz. Wenn diese Distanz kleiner als die Maxdistanz ist, gibts keine Lösung mit der Geschwindigkeit. Ergo-> Geschwindigkeit erhöhen und noch mal von vorn. Sonst haste deine Lösung

Das hätte noch den Vorteil, das sich da einige Werte noch rauskürzen (es ist egal, ob ich nach (149|0|0) oder (0|149|0) Fliege [OK, die haste ja schon rausgestrichen] und es ist fast egal, ob ich nach (149|0|0) oder (149|0|1) fliege.

... Joahr. Proggen musste selbst ^^

MfG

EDIT: Hatte ein bissel lange weile, hier mal ne geupdatete Version von fxGF. Aber keine Garantie, das es richtig ist. Hab im Moment kein Delphi-Compieler zur Hand... Die Performance, wie er die falschen Ergebnise ausrechnet, müsste allerdings deutlich höher liegen... Aber falls es falsch sein sollte, kannste es ja mal selbst nachvollziehen:

-> Divisionen surch eine konstante kann durch die Multiplikation der Inversen ersetzt werden (Foo/40 = Foo*0.025)
-> Wenn nur ein bestimmter Wertebereich abgefragt wird, brauch man nicht auf Sonderfälle prüfen (fxID fällt weg.
-> Manchmal hilft durchmultiplizieren (60(Foo+1) = 60*Foo + 60)
-> Wenn man Werte einer Funktion (wie z.B. den Abstand) häufiger brauch-> Zwischenspeichern! (Strecke usw.)
-> Wieso runden, wenn man den exakten Wert haben kann? (außer natürlich, wenn es von bedeutung ist^^
-> usw.

Hier die Funktion:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
function TForm1.fxGF(sx,sy,sz,zx,zy,zz:integer;jetstream:boolean):real;
var fFlugzeit,fStrecke:real;
begin
  abst_xy := sqrt( (sx-zx)*(sx-zx) + (sy-zy)*(sy-zy));
  abst_z := abs(sz-zz);
  fStrecke  := abst_xy + abst_z*0.012;
  
  fFlugZeit := fStrecke*12 + 60;
  
  if abst_xy<>0 then 
  fFlugZeit := fFlugZeit+192000//anderes System --> mehr Flugzeit

  if jetstream then
  result:=fFlugZeit/fStrecke*40
  else 
  result:= fFlugZeit;
  
  if argala.ItemIndex=2 then 
  result:=result*0.3125;
end;


MfG zum 2.

_________________
LifeIsToShortToThinkAboutTheShortness
Andy77
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 17



BeitragVerfasst: Mi 06.09.06 21:35 
Ich weiß nicht genau, ob ich das Problem richtig verstanden habe.
Meine Idee ist, nicht alles komplett durchzurechnen, sondern ein Optimierungsalgorithmus anzuwenden, z.B. Newton-Verfahren. Dafür bestimmst Du die Richtung, in der es besser wird und gehst solange, bis das Ergebnis nicht mehr besser wird. Dann nochmal neue Richtungssuche usw.
Hat den Vorteil, daß man nur wenige Male den komplexen Funktionsaufruf rechnen muß.

Gruß,
Andreas