Performance erhöhen

teamO · Beitrag von **teamO** » 11.06.2010 10:58

hi,

Ich hab unten einen Code gepostet, der Folgendes macht:
Es gibt eine Liste mit Pheromonen (geruchsstoffe über die Ameisen kommunizieren) und aus dieser Liste soll ein Array generiert werden, das die Pheromonkonzentration an jeder Position enthält.

bsp:

Code: Alles auswählen

Liste:
position 10,10
stärke 7

position 10,20
stärke 7

position 15,15
stärke 7

position 2,2
stärke 3

=> Array

2  2  2  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
2  3  2  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
2  2  2  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
1  1  1  0  0  0  0  1  1  1  1  1  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  1  1  2  2  2  2  2  1  1  0  0  0  0  0  0  0  
0  0  0  0  1  1  2  3  3  3  3  3  2  1  1  0  0  0  0  0  0  
0  0  0  0  1  2  3  3  4  4  4  3  3  2  1  0  0  0  0  0  0  
0  0  0  1  2  3  3  4  5  5  5  4  3  3  2  1  0  0  0  0  0  
0  0  0  1  2  3  4  5  6  6  6  5  5  4  3  2  1  0  0  0  0  
0  0  0  1  2  3  4  5  6  7  7  6  6  5  4  3  2  1  1  0  0  
0  0  0  1  2  3  4  5  6  7  7  7  7  6  5  4  3  2  1  1  0  
0  0  0  1  2  3  3  4  5  6  7  7  6  7  6  5  3  3  2  1  0  
0  0  0  0  1  2  3  3  5  6  7  6  7  7  6  5  4  3  3  2  1  
0  0  0  0  1  1  2  4  5  6  7  8  7  7  7  6  5  4  3  2  1  
0  0  0  0  0  2  2  4  5  6  7  8  7  8  7  6  5  4  3  2  1  
0  0  0  0  1  1  2  4  5  6  7  8  7  7  7  6  5  4  3  2  1  
0  0  0  0  1  2  3  3  5  6  7  6  7  7  6  5  4  3  3  2  1  
0  0  0  1  2  3  3  4  5  6  7  7  6  7  6  5  3  3  2  1  0  
0  0  0  1  2  3  4  5  6  7  7  7  7  6  5  4  3  2  1  1  0  
0  0  0  1  2  3  4  5  6  7  7  6  6  5  4  3  2  1  1  0  0  
0  0  0  1  2  3  4  5  6  6  6  5  5  4  3  2  1  0  0  0  0  
0  0  0  1  2  3  3  4  5  5  5  4  3  3  2  1  0  0  0  0  0  
0  0  0  0  1  2  3  3  4  4  4  3  3  2  1  0  0  0  0  0  0  
0  0  0  0  1  1  2  3  3  3  3  3  2  1  1  0  0  0  0  0  0  
0  0  0  0  0  1  1  2  2  2  2  2  1  1  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  1  1  1  1  1  0  0  0  0  0  0  0  0  0

Dazu hab ich folgenden Code geschrieben und auch schon versucht zu optimieren (und dabei möglicherweise die Lesbarkeit beeinträchtigt...). Doch es läuft immernoch zu langsam.
Die zeit geht in der Prozedur "generatePheromonMap2" verloren. Also könnt ihr euch mit euren Tipps auf die konzentrieren.
Ich bin für Vorschläge speziell zu diesem Code, aber auch für allgemeine zum Thema Optimierung (was man vermeiden sollte ect.) dankbar

hier nun der Code:

Code: Alles auswählen

height=500
width=500

pheromonStrength=20

Structure Source
amount.i
type.b
EndStructure

Structure ants
pos.point
age.w
type.b
load.source
pherStrength.w
*heap.heaps;pointer to the homeHeap of the ant
angel.f
damage.w 
EndStructure

Structure heaps
pos.point
size.i  ;size of the heap
food.i  ;stored food
numberOfEggs.i
numberOfEggCareAnts.i
colony.b
List egg.w()
EndStructure

Structure pheromonList
  Array strength.i(2)
  pos.point
EndStructure

Structure pheromonArray
  pheroList.i
  Array strength.i(2)
EndStructure

Structure colony
color.i ;color of the colony
List ant.ants()
List heap.heaps()
Array pheromonArray.pheromonArray(0) ;array, that contains pointer to the pheromon List
List pheromon.pheromonList()
EndStructure

Dim CircleTemp.w(pheromonStrength*2-2,pheromonStrength*2-2)
Dim circles.w(pheromonStrength-1,pheromonStrength*2-2,pheromonStrength*2-2) ;array that contains the strengthDistribution for each strength<=strength

Procedure generatePheromonMap2(Array colony.colony(1),colony)
  Shared circles()
  Shared width
  Shared height
 
  ForEach colony(colony)\pheromon() ;go through each pheromon of this colony
    *pher.PheromonList=colony(colony)\pheromon()
  
    For type=0 To 2 ;go through each type

 
      strength.w=*pher\strength(type)

      If strength<>0 
    
        range=strength*2-2
        For y=-strength+1 To strength-1
  
          For x=-strength+1 To strength-1
            AbsPosX=x+*pher\pos\x
            AbsPosY=y+*pher\pos\y         
            If AbsPosX>=0 And AbsPosX<width
              If AbsPosY>=0 And AbsPosY<height
                colony(colony)\pheromonArray(AbsPosX+width*(AbsPosY))\strength(type)+circles(strength-1,x+strength-1,y+strength-1);sadly only 1-dimensional array possible in structure...
              EndIf
            EndIf
          Next
        Next
        
        
      EndIf
    Next
  Next

EndProcedure

Procedure generateCircle(radius,Array ar.w(2))
  For x=1 To radius*2-1
    For y=1 To radius*2-1
      dist=Sqr((x-radius)*(x-radius)+(y-radius)*(y-radius))
      If dist<radius
        ar(x-1,y-1)=radius-dist
      Else
        ar(x-1,y-1)=0
      EndIf
    Next
  Next
EndProcedure

Procedure addPheromon(Array colony.colony(1),posX,posY,type,colony,strength)
Shared width

With colony(colony)\pheromonArray(width*posY+posX)  
  If \pheroList=0;create a new element, if it doesn't exist
    \pheroList=AddElement(colony(colony)\pheromon());create a new pheromonElement and a pointer to it, which is stored in the array
    colony(colony)\pheromon()\strength(type)=strength
    colony(colony)\pheromon()\pos\x=posX
    colony(colony)\pheromon()\pos\y=posY
  Else
    colony(colony)\pheromon()\strength(type)+strength
  EndIf
EndWith

EndProcedure

For i=1 To pheromonStrength
  generateCircle(i,CircleTemp())
  For x=0 To i*2-2
    For y=0 To i*2-2
      circles(i-1,x,y)=CircleTemp(x,y) ;fill circles() with circles of every size <= pheromonStrength
    Next
  Next
Next

Dim colony.colony(0)
Dim colony(0)\pheromonArray(width*height)

For y=0 To 99
  For x=0 To 99
    addPheromon(colony(),x,y,0,0,pheromonStrength)
  Next
Next


time=GetTickCount_()
generatePheromonMap2(colony(),0)
time=GetTickCount_()-time

; CreateFile(0,"test.txt")
; For y=0 To 110
;   For x=0 To 110
;     WriteString(0,Str(colony(0)\pheromonArray(x+y*width)\strength(0))+" ")
;   Next
;   WriteStringN(0,"")
; Next
; CloseFile(0)

MessageRequester("",Str(time))

STARGÅTE · Beitrag von **STARGÅTE** » 11.06.2010 11:22

Was ich so auf dne ersten blick sehe, sind eine menge verschachteler Schleifen.
Das ist wohl das Hauptproblem.

Allerding weiß ich nicht genau was da eigentlich gemacht wird.

Es wäre hilfreich, ein paar Hintergrund Informationnen zu liefern.

Wenn an der stelle 10,10 eine Stärke 7 existiert, wie sieht die dazu gehörige Potentialgleichung aus ?
Also wie nimmt die Konzentration mit dem Radius ab ? 1/r ? 1/r² ? ...

Ich hätte nun eine völlig andere Idee.

Du nimmst DX9 zur Hilfe.

Du erzeugt zu jedem Pheromonen ein Sprite in dem die Konzentration dargestellt ist (Rot = Stärke)
und dann werde die ganzen Sprites mit einem Blendingmode (Addition der Farben) übereinander gelegt.
dann wird der Ausschnitt ausgelesen, und fertig.

So wie ich das bei dir sehe, erzeugt du ja sowas ähnliches, nur halt mit Arrays die man übereinander legt und dann auch ausließt.

Man könnte aber auch über die Potentialgleichungen zu jedem Startdort eine gesamt Potentialgleichung erstellen.
Und hätte dann eine genau formel zum berechnen der Konzentration an einem Punkt, (das wäre dann sogar für flißkommazahlen)

Wäre nett wenn du mir ein paar Hintergrundinfos geben kannst, dann schreib ich mal was selber.

STARGÅTE · Beitrag von **STARGÅTE** » 11.06.2010 11:52

Sry für das doppel Post aber
Hier mal meine "Version", wie man ein Potentialfeld darstellen kann, in dem 10 Ladungen vertielt sind (positiv und negativ)

Code: Alles auswählen

Enumeration
 #Window : #Gadget : #Image
EndEnumeration

Structure Ladung
 x.f : y.f : q.f
EndStructure

Global NewList Ladung.Ladung()

; Ladungen erstellen
RandomSeed(6)
For n = 1 To 10
  AddElement(Ladung())
  Ladung()\x = Random(63)
  Ladung()\y = Random(63)
  Ladung()\q = 255*(Random(1)*2-1)
Next

; Potentialfeld
Procedure Ladungen(x, y, QuellFarbe, ZielFarbe)
  Protected q.f, qi.f
  ForEach Ladung() : With Ladung()
    qi = \q / Sqr((x-\x)*(x-\x)+(y-\y)*(y-\y))
    q + qi
  EndWith : Next
  Color = RGB(0,255,0)
  If q <= 255
    If q >= 0 
      Color = RGB(0,q,0)
    ElseIf q >= -255
      Color = RGB(-q,0,0)
    Else
      Color = RGB(255,0,0)
    EndIf
  EndIf
  ProcedureReturn Color
EndProcedure  
 

CreateImage(#Image, 64, 64, 24)

StartDrawing(ImageOutput(#Image))
  DrawingMode(#PB_2DDrawing_CustomFilter)
  CustomFilterCallback(@Ladungen())
  Box(0,0,64,64)
StopDrawing()

ResizeImage(#Image, 512, 512)

SetClipboardImage(#Image)


OpenWindow(#Window, 0, 0, ImageWidth(#Image), ImageHeight(#Image), "Image", #PB_Window_MinimizeGadget|#PB_Window_ScreenCentered)
  ImageGadget(#Gadget, 0, 0, ImageWidth(#Image), ImageHeight(#Image), ImageID(#Image))

Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow

teamO · Beitrag von **teamO** » 11.06.2010 16:10

Wow, gleich ein beispielcode! Danke!

Das Potential hat in meinem beispiel linear abgenommen, das wollt ich aber später noch auf 1/r^2 ändern. Bei deinem Beispiel wars dann ja aber sowieso schon so

Hat ne weile gedauert, bis ich erkannt hab, wo der Trick liegt. Ich hab mich zwar gleich gewundert, wieso du das Bild resizest, aber habs dann auskommentiert und war dann enttäuscht, wieso das bei gleichen Bedingungen wie mein Programm gut 20x so lange dauert.
Bis dann beim Mittagessen die Erleuchtung kam und ich gemerkt hab, dass ich deinen Trick elegant umgangen hab

Aber jetzt, wo ichs blick muss ich sagen: Genial!
Die Genauigkeit der Karte nimmt dann zwar etwas ab, aber das müsste verkraftbar sein.

Ich werde deutlich höhere Konzentrationen als 255 haben. Zumal wenn ich die Karte auf 1/64 der Größe zusammenschrumpfe. Ich denke ich werde dann halt für jeden der 3 Typen ein extra Bild zeichnen müssen.

Das Auslesen wird dann wohl über die Point(x,y) funktion gehen. ist das schnell genug, um 500*500 Pixel pro Frame durchzugehn?

EDIT
Aber so ganz klar ist mir immernoch nicht, was du da genau machst:
Du setzt den Zeichenmodus auf eigenen Filter und rufst dann Box auf, was jetzt irgendwie deinen Filter verwendet.
Und wo können die Parameter Quellfarbe und Zielfarbe an Ladungen() übergeben werde?

STARGÅTE · Beitrag von **STARGÅTE** » 11.06.2010 16:29

Das Resize ist eigentlich nicht bestandteil der Demo, wi man ein Potentialfeld erstellt, sonden einfach nur um die sache größer zu machen.

Du kannst bei mir auch das Bild gleich auf 512 bringen, das läuft immer noch schneller als deins, aber man sieht halt nciht mehr ^^

Auch das mit den Farben war nur ein Beispiel ...

Aber klar, kannst du das Resize auch als "Hochrechnung" nehmen, um Zeit zu sparen.

Beim auslesen kannst du auch mit DrawingBuffer arbeiten und dann direkt aus dem Speicher lesen!
(nur mit dem Format aufpassen!)

@7x7

7x7 · Beitrag von **7x7** » 11.06.2010 16:29

tjaja, unser STARGÅTE; manchmal wirkt er wirklich etwas "ausserirdisch"?

teamO · Beitrag von **teamO** » 11.06.2010 17:00

mein edit kam 3 Minuten zu spät

STARGÅTE hat geschrieben: Du kannst bei mir auch das Bild gleich auf 512 bringen, das läuft immer noch schneller als deins, aber man sieht halt nciht mehr ^^

Naja, ich hab mein Programm mit 10000 Pheromonen und einer Auflösung von 500*500 laufen lassen und es hat etwas weniger als 1 sec gedauert. Dein Programm hat für die selbe Aufgabe etwa 10 Minuten gebraucht (aber es macht schöne Bilder: http://img202.imageshack.us/gal.php?g=stargate01.png) . Oder mach ich da was falsch???

was ich geändert hab ist nur:

Code: Alles auswählen

For n = 1 To 10000; für die 10.000 Pheromone
  AddElement(Ladung())
  Ladung()\x = Random(500-1)
  Ladung()\y = Random(500-1)
  Ladung()\q(0) = Random(10);es gibt 3 typen von Ladungen, aber nur positive
  ladung()\q(1) = Random(10)
  ladung()\q(2) = Random(10)
Next

CreateImage(#Image, 500, 500, 24);für meine Auflösung

  Box(0,0,500,500);s.o.

und ein paar Kleinigkeiten in der Procedure, aber nichts prinzipielles (glaub ich zumindest...):

Procedure Ladungen(x, y, QuellFarbe, ZielFarbe)
  Protected q.f, qi.f
  Dim temp(3)
  ForEach Ladung() : With Ladung()
      For i=0 To 2
      qi = \q(i) / Sqr((x-\x)*(x-\x)+(y-\y)*(y-\y))
      temp(i) + qi
    Next
  EndWith : Next
  

  For i=0 To 2
    If temp(i) > 255
      temp(i)=255
    EndIf
  Next
  color = RGB(temp(0),temp(1),temp(2))
  ProcedureReturn Color
EndProcedure

STARGÅTE · Beitrag von **STARGÅTE** » 11.06.2010 17:34

Sehe gerade nicht mehr durch, erstell mal bitte noch mal zwei ausführebare Codes, die das "gleiche" ergebnis Bringen aber eben deine und meine Methode haben ...

Aber klar das bei 10.000 Pheromone
das ding lange dauert, weil er halt für jedne Pixel alle 10k durchgeht.

teamO · Beitrag von **teamO** » 11.06.2010 18:07

Dein Code (mit 10k Pheromonen)

Code: Alles auswählen

Enumeration
#Window : #Gadget : #Image
EndEnumeration

Structure Ladung
x.f : y.f : Array q.f(3)
EndStructure

Global NewList Ladung.Ladung()

; Ladungen erstellen
;RandomSeed(6)
For n = 1 To 10000 ;10k Pheromonen der Stärke 40 und des Typs 0
  AddElement(Ladung())
  Ladung()\x = Random(500-1)
  Ladung()\y = Random(500-1)
  Ladung()\q(0) = 40
Next

; Potentialfeld
Procedure Ladungen(x, y, QuellFarbe, ZielFarbe)
  Protected q.f, qi.f
  Dim temp(3)
  ForEach Ladung() : With Ladung()
      If x=\x And y=\y
        temp(i)+\q(i)
      Else
        For i=0 To 2
          qi = \q(i) / Sqr((x-\x)*(x-\x)+(y-\y)*(y-\y))
          temp(i) + qi
        Next
      EndIf
  EndWith : Next
  

  For i=0 To 2
    If temp(i) > 255
      temp(i)=255
    EndIf
  Next
  color = RGB(temp(0),temp(1),temp(2))
  ProcedureReturn Color
EndProcedure 


CreateImage(#Image, 500, 500, 24);500*500 Pixel

StartDrawing(ImageOutput(#Image))
  DrawingMode(#PB_2DDrawing_CustomFilter)
  CustomFilterCallback(@Ladungen())
  Box(0,0,500,500);ebenfalls 500*500p
StopDrawing()



SetClipboardImage(#Image)


OpenWindow(#Window, 0, 0, ImageWidth(#Image), ImageHeight(#Image), "Image", #PB_Window_MinimizeGadget|#PB_Window_ScreenCentered)
  ImageGadget(#Gadget, 0, 0, ImageWidth(#Image), ImageHeight(#Image), ImageID(#Image))

Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow

mein code:

Code: Alles auswählen

height=500;500*500
width=500

pheromonStrength=40

Structure Source
amount.i
type.b
EndStructure

Structure ants
pos.point
age.w
type.b
load.source
pherStrength.w
*heap.heaps;pointer to the homeHeap of the ant
angel.f
damage.w 
EndStructure

Structure heaps
pos.point
size.i  ;size of the heap
food.i  ;stored food
numberOfEggs.i
numberOfEggCareAnts.i
colony.b
List egg.w()
EndStructure

Structure pheromonList
  Array strength.i(2)
  pos.point
EndStructure

Structure pheromonArray
  pheroList.i
  Array strength.i(2)
EndStructure

Structure colony
color.i ;color of the colony
List ant.ants()
List heap.heaps()
Array pheromonArray.pheromonArray(0) ;array, that contains pointer to the pheromon List
List pheromon.pheromonList()
EndStructure

Dim CircleTemp.w(pheromonStrength*2-2,pheromonStrength*2-2)
Dim circles.w(pheromonStrength-1,pheromonStrength*2-2,pheromonStrength*2-2) ;array that contains the strengthDistribution for each strength<=strength

Procedure generatePheromonMap2(Array colony.colony(1),colony)
  Shared circles()
  Shared width
  Shared height
 
  ForEach colony(colony)\pheromon() ;go through each pheromon of this colony
    *pher.PheromonList=colony(colony)\pheromon()
  
    For type=0 To 2 ;go through each type

 
      strength.w=*pher\strength(type)

      If strength<>0 
    
        range=strength*2-2
        For y=-strength+1 To strength-1
  
          For x=-strength+1 To strength-1
            AbsPosX=x+*pher\pos\x
            AbsPosY=y+*pher\pos\y         
            If AbsPosX>=0 And AbsPosX<width
              If AbsPosY>=0 And AbsPosY<height
                colony(colony)\pheromonArray(AbsPosX+width*(AbsPosY))\strength(type)+circles(strength-1,x+strength-1,y+strength-1);sadly only 1-dimensional array possible in structure...
              EndIf
            EndIf
          Next
        Next
        
        
      EndIf
    Next
  Next

EndProcedure

Procedure generateCircle(radius,Array ar.w(2))
  For x=1 To radius*2-1
    For y=1 To radius*2-1
      dist=Sqr((x-radius)*(x-radius)+(y-radius)*(y-radius))
      If dist<radius
        ar(x-1,y-1)=radius-dist
      Else
        ar(x-1,y-1)=0
      EndIf
    Next
  Next
EndProcedure

Procedure addPheromon(Array colony.colony(1),posX,posY,type,colony,strength)
Shared width

With colony(colony)\pheromonArray(width*posY+posX)  
  If \pheroList=0;create a new element, if it doesn't exist
    \pheroList=AddElement(colony(colony)\pheromon());create a new pheromonElement and a pointer to it, which is stored in the array
    colony(colony)\pheromon()\strength(type)=strength
    colony(colony)\pheromon()\pos\x=posX
    colony(colony)\pheromon()\pos\y=posY
  Else
    colony(colony)\pheromon()\strength(type)+strength
  EndIf
EndWith

EndProcedure

For i=1 To pheromonStrength
  generateCircle(i,CircleTemp())
  For x=0 To i*2-2
    For y=0 To i*2-2
      circles(i-1,x,y)=CircleTemp(x,y) ;fill circles() with circles of every size <= pheromonStrength
    Next
  Next
Next

Dim colony.colony(0)
Dim colony(0)\pheromonArray(width*height)

For y=0 To 100
  For x=0 To 100
    addPheromon(colony(),x,y,0,0,40) ;10000 Pheromone stärke 40 des typs 0
  Next
Next


time=GetTickCount_()
generatePheromonMap2(colony(),0)
time=GetTickCount_()-time

; CreateFile(0,"test.txt")
; For y=0 To 499
;   For x=0 To 499
;     WriteString(0,Str(colony(0)\pheromonArray(x+y*width)\strength(0))+"  ")
;   Next
;   WriteStringN(0,"")
; Next
; CloseFile(0)

MessageRequester("",Str(time))

das sind jetzt natürlich nicht genau gleiche Ergebnisse: die Pheromonkonzentration nimmt bei mir linear ab und hat deswegen auch keine unbegrenzte Reichweite.
aber es läuft eindeutig schneller^^

Hab grad gesehn, dass ich mich mit der Zeit vertan hab: ich hatte eine niedrige Pheromonstärke eingestellt. bei einer stärke von 40 braucht er 2 sec.

PureLust · Beitrag von **PureLust** » 11.06.2010 18:31

@STARGÅTE:

STARGÅTE hat geschrieben:Procedure Ladungen(x, y, QuellFarbe, ZielFarbe)
...
EndProcedure

CustomFilterCallback(@Ladungen())

Na das ist ja mal geil.

Zum ersten mal, dass ich für CustomFilterCallback() ein sinnvolles (und auch für mich nachvollziehbares) Beispiel sehe.
Da eröffnen sich einem ja ungeahnte Möglichkeiten. Vielen Dank dafür !!!

PureBoard

Performance erhöhen

Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen

Re: Performance erhöhen