Wie komme ich am schnellsten durch mein Array?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Wie komme ich am schnellsten durch mein Array?

Beitragvon Ydope » Freitag 12. Dezember 2008, 17:55

Hallo,

um etwas fitter in Python zu werden, habe ich eine aufgebohrte Version von Langtons Ameise, einem Zellularautomaten programmiert. Ziel ist erstmal hohe Geschwindigkeit.
Das ganze spielt sich auf einem Spielfeld ab, was ich folgendermaßen definiert habe:

Code: Alles auswählen

feld = [[0 for x in xrange(fsize)] for y in xrange(fsize)] #feldzustand
feldb = [[False for x in xrange(fsize)] for y in xrange(fsize)] #feld besucht(y/n)

In feld [][] liegt der jeweilige Zustand des Feldes (zw. 0 und 255) und in feldb ist gespeichert, ob das Feld schonmal besucht wurde.
Die Darstellung mache ich mit pygame.
Bei höherer Geschwindigkeit will ich das Spielfeld nicht nach jedem Schritt aktualisieren, sondern nur z.B. nach jedem 100.000. Schritt.

Code: Alles auswählen

    screen.fill (backgr)  # hintergrundfarbe
    for x in xrange(fsize):
        for y in xrange(fsize):
            if zoom <> .5:
                if feldb[x][y]:
                    pixel_col = col[feld[x][y]] # col enthält für jeden Zustand eine andere Farbe
                    if zoom > 1:
                        if maxrichtung == 3:               
                            xy = [(x-fz) * zoom + width/2,(y-fz) * zoom + height/2,zoom,zoom]
                        screen.fill(pixel_col, xy)

    pygame.display.flip()


Mal zoom und maxrichtung außen vorgelassen (man nehme bspw. an zoom = 2), wie kann ich das beschleunigen?
So durchläuft die Schleife ja sehr viele unnütze Felder, die noch gar nicht besucht wurden und für große Spielfelder (z.B. 2000x2000) wird das schon sehr lahm.
Gleichzeitig will ich den eigentlichen Ablauf nicht verlangsamen, indem ich z.B. nach jedem Schritt eine "Bounding Box" aktualisiere, auf die ich mich dann bei der Darstellung mit der äußeren Schleife beschränken kann, denn das Kernprogramm soll unabhängig von der Darstellung erstmal so schnell laufen wie möglich.

Ich hoffe, das Them ist hier richtig aufgehoben, da es ja nicht so sehr um pygame geht, sondern um diese Art der Schleife.

Besten Gruß
BlackJack

Beitragvon BlackJack » Freitag 12. Dezember 2008, 18:25

Also am einfachsten lässt sich das wohl beschleunigen, wenn Du das Feld gar nicht erst komplett darstellst. Die "Ameise" verändert pro Schritt ja nur ein Feld, also wäre es am günstigsten, auch immer nur dieses eine Feld in der Darstellung zu verändern und nicht alle die sich vom letzten Schritt gar nicht verändert haben.

Ansonsten könntest Du noch Invarianten aus den Schleifen herausziehen. So wie's aussieht verändert sich `zoom` während der Schleifen nicht. Die Bedinungen sind auch eigenartig. Wozu der erste Test? Man könnte vor beiden Schleifen mal testen, ob ``zoom > 1`` und nur wenn das der Fall ist, die Schleifen überhaupt erst ausführen.

So etwas wie ``width / 2`` sollte man dann auch heraus ziehen.

Und warum zwei Felder?
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Freitag 12. Dezember 2008, 19:02

Hi, danke für deine Anregungen.

Ich habe auch eine Darstellungsvariante, die immer nur das letzte Feld aktualisiert, die läuft auch ziemlich flott. Einige 1000 Schritte/s. Um das aber noch schneller laufen lassen zu können, brauche ich eine Varinate, die seltener darstelt, denn der eigentliche Kern läuft beträchtlich schneller, wenn ich nicht jeden Schritt darstelle. Dafür wechselt er dann auf diese Variante.

Ja, zoom ist eine Invariante in der Schleife, genau wie fz, width und height. Aber meine große Frage ist jetzt, wie ziehe ich die da raus? OK, width/2 kann ich z.B. vor der Schleife berechnen, aber ansonsten?

Die Bedingungen mit zoom <>.5 usw sehen etwas komisch aus, liegen aber daran, dass Verschiedenes gemacht werden muss, je nachdem ob der zoom 0.5, 1, oder höher ist. maxrichtung kann auch =5 sein, dann ist das Ganze hexagonal. Die ungekürzte Schleife sieht daher so aus, sie wird alle 100k Schritte (oder seltener) ausgeführt:

Code: Alles auswählen

def screenupdatefull():
    screen.fill (backgr)
    for x in xrange(fsize):
        for y in xrange(fsize):
            if zoom <> .5:
                if feldb[x][y]:
                    pixel_col = col[feld[x][y]]
                    if zoom > 1:
                        if maxrichtung == 3:               
                            xy = [(x-fz) * zoom + width/2,(y-fz) * zoom + height/2,zoom,zoom]
                        elif maxrichtung == 5:
                            if y%2 != 0:
                                xy = [(x-fz)*zoom + width/2 +zoom/2,(y-fz) * zoom + height/2, zoom,zoom]
                            if y%2 == 0:
                                xy = [(x-fz)*zoom + width/2,(y-fz) * zoom + height/2, zoom,zoom]
                        screen.fill(pixel_col, xy)
                    else:  #zoom=1
                        screen.set_at((int((x-fz) + width/2),int((y-fz) + height/2)), pixel_col)
            else:
                if x % 2 == 0 and y % 2 == 0:
                    if feldb[x][y] or feldb[x+1][y] or feldb[x][y+1] or feldb[x+1][y+1]:
                        RR=(col[feld[x][y]][0]+col[feld[(x+1)%fsize][y]][0]+col[feld[x][(y+1)%fsize]][0]+col[feld[(x+1)%fsize][(y+1)%fsize]][0])
                        GG=(col[feld[x][y]][1]+col[feld[(x+1)%fsize][y]][1]+col[feld[x][(y+1)%fsize]][1]+col[feld[(x+1)%fsize][(y+1)%fsize]][1])
                        BB=(col[feld[x][y]][2]+col[feld[(x+1)%fsize][y]][2]+col[feld[x][(y+1)%fsize]][2]+col[feld[(x+1)%fsize][(y+1)%fsize]][2])
                           
                        pixel_col = (RR/4,GG/4,BB/4)
                        screen.set_at((int((x-fz)*zoom + width/2),int((y-fz)*zoom + height/2)), pixel_col)
   
    draw_alltxt()
    pygame.display.flip()


Zwei "Spielfelder", weil ein Feld auch den Zustand 0 haben kann, obwohl es schon besucht wurde und weil ich dachte, es könnte die Darstellung beschleunigen.

Wie ich den eigentlichen Kern noch schneller kriegen kann, frage ich vielleich ein andermal, momentan ist das hier aber meine "Engstelle" :roll:

Gruß
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Beitragvon cofi » Freitag 12. Dezember 2008, 19:22

Zwei kleine Sachen: `<>' ist deprecated. Verwende `!='

Die `width/2' und die anderen Berechnungen ziehst du heraus indem du sie vor der Schleife einer Variablen zuweist:

Code: Alles auswählen

halfwidth = width / 2
for x ...:
    xfz = x - fz #wtf ist fz?
    for y ...:
        yfz = y - fz
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Freitag 12. Dezember 2008, 19:32

Ok, danke, wird gemacht. zoom kann ich aber schwerlich da rausziehen oder?
fz ist das zentrale Feld/Anfangsfeld. D.h. wenn das Spielfeld 600x600 Felder hat, ist fz = 300.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 12. Dezember 2008, 20:49

Ydope hat geschrieben:Ok, danke, wird gemacht. zoom kann ich aber schwerlich da rausziehen oder?


Nicht vollständig, aber ein bisschen was geht noch:

Code: Alles auswählen

    dw, dh, dz = width/2, height/2, zoom/2
    for x in xrange(fsize):
        dx = x-fz
        dxzw = dx*zoom+dw
        for y in xrange(fsize):
            dy = y-fz
            dyz = dy*zoom+dh
            if zoom != .5:
                if feldb[x][y]:
                    pixel_col = col[feld[x][y]]
                    if zoom > 1:
                        if maxrichtung == 3:               
                            xy = [dxzw, dyzh, zoom, zoom]
                        elif maxrichtung == 5:
                            xy = [dxzw+(y&1)*dz, dyzh, zoom, zoom]
                        screen.fill(pixel_col, xy)
                    else:  #zoom=1
                        screen.set_at((int(dx+dw), int(dy+dh)), pixel_col)
            else:
                # usw...
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Freitag 12. Dezember 2008, 21:35

Danke, ich werde die Schleifen und ifs noch etwas umgruppieren, damit die herausgezogenen Berechnungen nur durchgeführt werden, wenn sie auch später gebraucht werden.
Benutzeravatar
cofi
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Beitragvon cofi » Freitag 12. Dezember 2008, 21:35

Da hatte ich wohl noch ein paar vergessen ;)
Aber wenn du das so häufig immer wieder ausrechnet, dann wundert mich das nicht, dass das langsam ist ;)

Nochwas:

Code: Alles auswählen

else:  #zoom=1

*hust* Warum beschreibst du das im Kommentar und nicht im Code?

Code: Alles auswählen

elif zoom == 1:
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Freitag 12. Dezember 2008, 21:49

@ numerix:
Wobei, wenn ich nochmal drüber nachdenke, macht das "Herausziehen" bei der inneren Schleife wenig Sinn, denn es wird sowieso für jedes y nur einmal der ausgerechnete y-Wert gebraucht und oft wird er auch gar nicht gebraucht.
Bis auf width/2, height/2 und zoom/2 ist ein Herausziehen hier wohl sogar potentiell verlangsamend.

@ cofi:
Auf gute Fragen gibt es manchmal keine gute Antworten (Auch wenns rhetorische Fragen sind) :wink:

Gruß
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Freitag 12. Dezember 2008, 22:50

So, habe das nun umgesetzt. Mir ist noch aufgefallen, dass der y-Wert ja folgendermaßen ausgerechnet wird:
(y-fz) * zoom + height/2. Wenn man die Klammer auflöst, hat man y*zoom - fz*zoom + height/2 und der hintere Teil ist invariant, kann also vor der Klammer ausgerechnet werden.
Im Ergebnis siehts nun so aus:

Code: Alles auswählen

def screenupdatefull():
    screen.fill (backgr)
    w2, h2, z2 = width/2, height/2, zoom/2
    yzh = -(fz*zoom) + h2
    for x in xrange(fsize):
        xzw = (x - fz) * zoom + w2
        for y in xrange(fsize):
            if zoom != .5:
                if feldb[x][y]:
                    pixel_col = col[feld[x][y]]
                    if zoom > 1:
                        if maxrichtung == 3:               
                            xy = [xzw, y * zoom + yzh, zoom, zoom]
                        elif maxrichtung == 5:
                            xy = [xzw + (y&1) * z2, y * zoom + yzh, zoom, zoom]
                        screen.fill(pixel_col, xy)
                    elif zoom == 1:
                        screen.set_at((xzw, y + yzh), pixel_col)
            elif zoom == .5:
                if x % 2 == 0 and y % 2 == 0:
                    if feldb[x][y] or feldb[x+1][y] or feldb[x][y+1] or feldb[x+1][y+1]:
                        RR=(col[feld[x][y]][0]+col[feld[(x+1)%fsize][y]][0]+col[feld[x][(y+1)%fsize]][0]+col[feld[(x+1)%fsize][(y+1)%fsize]][0])
                        GG=(col[feld[x][y]][1]+col[feld[(x+1)%fsize][y]][1]+col[feld[x][(y+1)%fsize]][1]+col[feld[(x+1)%fsize][(y+1)%fsize]][1])
                        BB=(col[feld[x][y]][2]+col[feld[(x+1)%fsize][y]][2]+col[feld[x][(y+1)%fsize]][2]+col[feld[(x+1)%fsize][(y+1)%fsize]][2])
                           
                        pixel_col = (RR/4,GG/4,BB/4)
                        screen.set_at((int(xzw), int(y * zoom + yzh)), pixel_col)
   
    draw_alltxt()
    pygame.display.flip()


Mein Grundproblem ist allerdings immer noch, dass es bei großen Spielfeldern noch ziemlich lange dauert, auch wenn die Felder noch gar nicht besucht wurden, einfach weil die Schleifen insgesamt durch Millionen von leeren Feldern durch laufen müssen, ohne was zu machen. Aber soweit, so gut. Danke!
BlackJack

Beitragvon BlackJack » Samstag 13. Dezember 2008, 00:21

Wenn es wirklich nur wenige interessante Felder im Verhältnis zur Gesamtanzahl sind, dann solltest Du vielleicht besser ein Dictionary statt einer verschachtelten Liste zum Speichern verwenden.
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Samstag 13. Dezember 2008, 14:51

Leider kann es später auch vorkommen, dass das ganze Spielfeld betreten wurde.
Aber ich habe nun Psyco mit reingenommen und das hat eine massive Beschleunigung bedeutet (Faktor 4-5), so dass ich nun ganz zufrieden bin. 8)
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Beitragvon Y0Gi » Samstag 13. Dezember 2008, 15:45

bad algos + psyco != ok

;)
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Sonntag 14. Dezember 2008, 22:02

So, konnte nun doch noch einiges beschleunigen.
Erstmal habe ich die if zoom == ... Abfragen aus der Schleife genommen. Dafür steht jetzt zwar dreimal die Schleife da, aber es ist natürlich schneller.
Außerdem habe ich das mit der verschachtelte Liste feldb [x][y] so umgebaut, dass für jedes x ein rowb = feldb[x] genommen wird, sodass ich dann innen in der der Doppelschleife sagen kann if rowb[y]: statt if feldb[x][y]:
Dieser Trick bringt auch nochmal eine klare Verbesserung, gerade bei recht leeren Spielfeldern.
Das Gleiche auch bei feld[x][y] zu machen, geht leider nicht direkt, weil ich davon ausgehen muss, dass in vielen Reihen nicht auf feld[x][y] zugegriffen wird (weil die Reihe nicht besucht wurde).

So siehts nun aus:

Code: Alles auswählen

def screenupdatefull():
    screen.fill (backgr)
    w2, h2, z2 = width/2, height/2, zoom/2
    yzh = -(fz*zoom) + h2
    if zoom == .5:
                ...
    elif zoom == 1:
        for x in xrange(fsize):
            xzw = (x-fz) * zoom + w2
            rowb = feldb[x]
            for y in xrange(fsize):
                if rowb[y]:
                    pixel_col = col[feld[x][y]]
                    screen.set_at((xzw, y + yzh), pixel_col)
    else:  #zoom > 1
        for x in xrange(fsize):
            xzw = (x-fz) * zoom + w2
            rowb = feldb[x]
            for y in xrange(fsize):
                if rowb[y]:
                    pixel_col = col[feld[x][y]]
                    if maxrichtung == 3:               
                        xy = [xzw, y * zoom + yzh, zoom, zoom]
                    elif maxrichtung == 5:
                        xy = [xzw + (y&1) * z2, y * zoom + yzh, zoom, zoom]
                    screen.fill(pixel_col, xy)
    draw_alltxt()
    pygame.display.flip()


Es geht bestimmt noch was, aber momantan weiß ich nicht was und bin daher erstmal wieder zufrieden.

Gruß 8)
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Montag 15. Dezember 2008, 20:25

Könntest Du mir noch einmal in lang erklären, was Du mit aufgebohrt meinst? (Dass Deine Felder nicht nur weiß und schwarz sind? Oder was ist da mit 256 Zuständen pro feld gemeint?)

Wieso merkst Du Dir nicht einfach bereits besuchte Felder? Somit könntest Du die doch direkt anspringen und ändern!

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]