Python - Vergleichen von Elementen der Liste mit "Nachbar" -Elementen

Question

Dies könnte eher eine "Annäherung" oder eine konzeptionelle Frage sein.

Grundsätzlich habe ich eine Python eine mehrdimensionale Liste wie folgt:

my_list = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

Was muss ich durch das Array tun durchlaufen und jedes Element mit jenen vergleichen, direkt es, als ob die Liste umliegenden layed war als eine Matrix aus.

Zum Beispiel gegeben das erste Element der ersten Reihe, my_list[0][0], muß ich wissen, den Wert von my_list[0][1] wissen, my_list[1][0] und my_list[1][1]. Der Wert der umgebenden Elemente bestimmt, wie das aktuelle Element bearbeitet werden soll. Für ein Element im Herzen des Arrays sind natürlich 8 Vergleiche notwendig.

Nun weiß ich, ich könnte einfach durch das Array iterieren und mit den indizierten Werten vergleichen, wie oben. Ich war neugierig, ob es einen effizienteren Weg gibt, der die erforderliche Iteration begrenzt. Sollte ich das Array iterieren, so wie es ist, oder iterieren und nur Werte auf jeder Seite vergleichen und dann das Array transponieren und es erneut ausführen. Dies würde jedoch diese Werte auf die Diagonale ignorieren. Und sollte ich die Ergebnisse der Element-Lookups speichern, damit ich den Wert des gleichen Elements nicht mehrmals festlege?

Ich vermute, dass dies einen grundlegenden Ansatz in der Informatik haben kann, und ich bin bestrebt, Feedback zu erhalten über den besten Ansatz mit Python im Gegensatz zu auf der Suche nach einer spezifischen Antwort auf mein Problem.

Jede Hilfe sehr geschätzt.

Answer 1

Sie können schneller und möglicherweise noch einfacher Code mit numpy oder andere Alternativen (siehe unten für Details). Aber von einem theoretischen Standpunkt aus gesehen, ist das Beste, was Sie erreichen können, O (N * M), und Sie können das mit Ihrem Design (wenn ich es richtig verstehe) erreichen. Zum Beispiel:

def neighbors(matrix, row, col): 
    for i in row-1, row, row+1: 
     if i < 0 or i == len(matrix): continue 
     for j in col-1, col, col+1: 
      if j < 0 or j == len(matrix[i]): continue 
      if i == row and j == col: continue 
      yield matrix[i][j] 

matrix = [[0,1,1,1,0,1], [1,1,1,0,0,1], [1,1,0,0,0,1], [1,1,1,1,1,1]] 

for i, row in enumerate(matrix): 
    for j, cell in enumerate(cell): 
     for neighbor in neighbors(matrix, i, j): 
      do_stuff(cell, neighbor) 

Dies hat nimmt N * M * 8 Stufen (eigentlich ein bisschen weniger als das, weil viele Zellen werden weniger als 8 Nachbarn haben). Und algorithmisch gibt es keine Möglichkeit, besser als O (N * M) zu machen. Also, du bist fertig.

---

(In einigen Fällen können Sie die Dinge einfacher-ohne wesentliche Änderung oder so machen leistungs durch in Bezug auf Iterator Transformationen zu denken. Zum Beispiel können Sie leicht eine Grouper über benachbarte Drillinge aus einer Liste erstellen a durch richtig Zippen a, a[1:], und a[2:], und Sie können dies zu benachbarten 2-dimensionalen Nonsets erweitern.Aber ich denke in diesem Fall würde es nur Ihren Code komplizierter machen, dass das Schreiben eines expliziten neighbors Iterator und explizite for Schleifen über die Matrix.)

---

Allerdings praktisch, können Sie eine Menge schneller, auf verschiedene Arten. Zum Beispiel:

• Mit numpy können Sie eine Größenordnung oder so schneller erhalten. Wenn Sie eine enge Schleife durchlaufen und einfache Arithmetik durchführen, ist das eine der Sachen, bei denen Python besonders langsam ist, und numpy können Sie stattdessen in C (oder Fortran) tun.
• Mit Ihrer bevorzugten GPGPU-Bibliothek können Sie Ihre Operationen explizit vektorisieren.
• Mit multiprocessing können Sie die Matrix in Stücke zerbrechen und mehrere Stücke parallel auf separaten Kernen (oder sogar separaten Maschinen) durchführen.

Natürlich für eine einzige 4x6 Matrix, keiner von ihnen sind es wert, zu tun ... außer vielleicht für numpy, die Ihren Code einfacher machen können sowie schneller, solange Sie Ihre Operationen natürlich in Matrix/Broadcast ausdrücken Begriffe.

In der Tat, auch wenn Sie nicht einfach die Dinge auf diese Weise zum Ausdruck bringen können, nur numpy-Speicher die Matrix verwenden, können die Dinge ein wenig einfacher (und etwas Speicher zu sparen, wenn es ankommt). Beispielsweise können Sie mit numpy auf eine einzelne Spalte aus einer Matrix zugreifen, während Sie in reinem Python so etwas wie [row[col] for row in matrix] schreiben müssen.

---

Also, wie würdest du das mit numpy angehen?

Zuerst sollten Sie über numpy.matrix und ufunc lesen (oder, besser, ein höheres Tutorial, aber ich habe kein zu empfehlen), bevor Sie zu viel weiter gehen.

Wie auch immer, es hängt davon ab, was Sie mit jeder Gruppe von Nachbarn tun, aber es gibt drei grundlegende Ideen.

Erstens, wenn Sie Ihre Operation in einfache Matrix Mathematik konvertieren können, ist das immer am einfachsten.

Wenn nicht, können Sie 8 "Nachbarmatrizen" erstellen, indem Sie einfach die Matrix in jede Richtung verschieben und dann einfache Operationen für jeden Nachbarn ausführen. In einigen Fällen kann es einfacher sein, mit einer N + 2 × N + 2-Matrix mit geeigneten "leeren" Werten (normalerweise 0 oder Nan) im äußeren Rand zu beginnen. Alternativ können Sie die Matrix verschieben und leere Werte eingeben. Oder für einige Operationen benötigen Sie keine Matrix mit identischer Größe. Sie können also die Matrix zuschneiden, um einen Nachbarn zu erstellen. Es hängt wirklich davon ab, welche Operationen Sie ausführen möchten.

Zum Beispiel der Eingabe als Fest 6x4-Board für die Game of Life unter:

def neighbors(matrix): 
    for i in -1, 0, 1: 
     for j in -1, 0, 1: 
      if i == 0 and j == 0: continue 
      yield np.roll(np.roll(matrix, i, 0), j, 1) 

matrix = np.matrix([[0,0,0,0,0,0,0,0], 
        [0,0,1,1,1,0,1,0], 
        [0,1,1,1,0,0,1,0], 
        [0,1,1,0,0,0,1,0], 
        [0,1,1,1,1,1,1,0], 
        [0,0,0,0,0,0,0,0]]) 
while True: 
    livecount = sum(neighbors(matrix)) 
    matrix = (matrix & (livecount==2)) | (livecount==3) 

(Beachten Sie, dass dies nicht der beste Weg ist, um dieses Problem zu lösen, aber ich denke, es ist relativ leicht zu verstehen, und wahrscheinlich zu beleuchten, was auch immer Ihr tatsächliches Problem ist.)