Wie komme ich am schnellsten durch mein Array?

[Ydope]

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]

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]

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"

Gruß

[cofi]

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]

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.

[numerix]

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]

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.

[cofi]

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]

@ 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)

Gruß

[Ydope]

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]

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]

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.

[Y0Gi]

bad algos + psyco != ok

[Ydope]

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ß

[Hyperion]

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!

[Ydope]

Genau. Die Felder können auch weitere Zustände/Farben haben. Das ist z.B. hier erklärt: http://en.wikipedia.org/wiki/Langton%27 ... on.27s_ant
Außerdem kann meine Variante nicht nur auf einem Spielfeld mit quadratischen Zellen laufen, sondern auch mit sechseckigen Zellen. Da kennt der Automat dann auch nicht nur "dreh dich 90° nach links bzw. rechts", sondern er kann sich 60° und 120° in beide Richtungen drehen bevor er einen Schritt weiter geht.
Ferner können mehrere Automaten gleichzeitig rumlaufen und noch ein paar weitere Kleinigkeiten.

Wie meinst du das mit dem Merken? Ich habe momentan dieses Array oder verschachtelte Liste oder wie immer man das nennt:

Code: Alles auswählen

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

Wenn das Feld x,y besucht wurde, wird es True. In der Hauptschleife:

Code: Alles auswählen

        if feldb[self.x][self.y] == False: 
            visited_count += 1     
            feldb[self.x][self.y] = True 

visited_count zählt global die besuchten Felder.

Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?

[numerix]

Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?

Nicht in dem Sinne, dass du die Liste durchlaufen müsstest - dafür gibt es den "in"-Operator. Ob es damit schneller geht als mit den beiden parallelen Listen könntest du ja ausprobieren.

[Ydope]

Da stehe ich etwas auf dem Schlauch und weiß ncht ob wir das gleiche meinen.
Meine eigentliche Schleife ohne die Darstellung soll möglichst schnell sein. Das ist die Hauptpriorität.
Und die ist doch sicher langsamer, wenn ich nach jedem Schritt mittels "in" nachschaue, ob das Feld schon in einer Liste von Koordinatenpaaren ist (und falls es das nicht ist, anhänge), als wenn ich nur schaue, ob das eine Feld in der 2-dimensionalen Liste feldb[x][y] True ist (und falls es False ist, auf True setze). Es können ja durchaus Hunderttausende Felder schon besucht worden sein.
Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.

Gruß

[numerix]

Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.

Nein, meine ich nicht. Ich *weiß* es schlicht nicht, aber da sich der Aufwand, es zu probieren, in Grenzen hält, würde ich es einfach mal ausprobieren. Im übrigen dürfte es mit einer Menge (set) statt einer Liste evtl. schneller laufen bei dieser Größenordnung (die mir nicht bewusst war). Aber auch das lässt sich ja einfach ausprobieren und testen ...

[sea-live]

ich glaube es wäre für dich sehr nützlich unter pygame mal das Arcade spiel crush roller zu analysieren wie dieser programmierer das ganze gelöst hat.