Finde Diagonale Summen in numpy (schneller)

Ich habe ein paar numpy Arrays wie folgt:

 array([[0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 1, 0, 0]]) 

Und ich benutze den folgenden Code, um die Summe der Elemente auf jeder n-ten Diagonale von -7 bis 8 des Brettes (und die gespiegelte Version davon) zu finden.

 n = 8 rate = [b.diagonal(i).sum() for b in (board, board[::-1]) for i in range(-n+1, n)] 

Nach einigen Profiling, dauert diese Operation etwa 2/3 der Gesamtlaufzeit und es scheint, weil von 2 Faktoren:

  • Die .diagonal Methode baut ein neues Array statt einer Ansicht auf (sieht aus wie numpy 1.7 wird eine neue .diag Methode haben, um das zu lösen)
  • Die Iteration erfolgt in Python im Listenverständnis

Also, es gibt irgendwelche Methoden, um diese Summen schneller zu finden (evtl. in der C-Schicht von numpy)?


Nach einigen weiteren Tests konnte ich 7.5x die Gesamtzeit durch Caching dieser Operation reduzieren … Vielleicht war ich auf der Suche nach dem falschen Engpass?


Eine Sache noch:

.trace gerade die .trace Methode gefunden, die die diagonal(i).sum() Sache ersetzt und … Es gab nicht viel Leistungsverbesserung (ca. 2 bis 4%).

Also das Problem sollte das Verständnis sein. Irgendwelche Ideen?

2 Solutions collect form web for “Finde Diagonale Summen in numpy (schneller)”

Es gibt eine mögliche Lösung mit stride_tricks . Dies beruht zum Teil auf der Fülle von Informationen, die in den Antworten auf diese Frage zur Verfügung stehen , aber das Problem ist einfach anders genug, denke ich, nicht als Duplikat zu zählen. Hier ist die Grundidee, angewendet auf eine quadratische Matrix – siehe unten für eine Funktion, die die allgemeinere Lösung implementiert.

 >>> cols = 8 >>> a = numpy.arange(cols * cols).reshape((cols, cols)) >>> fill = numpy.zeros((cols - 1) * cols, dtype='i8').reshape((cols - 1, cols)) >>> stacked = numpy.vstack((a, fill, a)) >>> major_stride, minor_stride = stacked.strides >>> strides = major_stride, minor_stride * (cols + 1) >>> shape = (cols * 2 - 1, cols) >>> numpy.lib.stride_tricks.as_strided(stacked, shape, strides) array([[ 0, 9, 18, 27, 36, 45, 54, 63], [ 8, 17, 26, 35, 44, 53, 62, 0], [16, 25, 34, 43, 52, 61, 0, 0], [24, 33, 42, 51, 60, 0, 0, 0], [32, 41, 50, 59, 0, 0, 0, 0], [40, 49, 58, 0, 0, 0, 0, 0], [48, 57, 0, 0, 0, 0, 0, 0], [56, 0, 0, 0, 0, 0, 0, 0], [ 0, 0, 0, 0, 0, 0, 0, 7], [ 0, 0, 0, 0, 0, 0, 6, 15], [ 0, 0, 0, 0, 0, 5, 14, 23], [ 0, 0, 0, 0, 4, 13, 22, 31], [ 0, 0, 0, 3, 12, 21, 30, 39], [ 0, 0, 2, 11, 20, 29, 38, 47], [ 0, 1, 10, 19, 28, 37, 46, 55]]) >>> diags = numpy.lib.stride_tricks.as_strided(stacked, shape, strides) >>> diags.sum(axis=1) array([252, 245, 231, 210, 182, 147, 105, 56, 7, 21, 42, 70, 105, 147, 196]) 

Natürlich habe ich keine Ahnung, wie schnell das tatsächlich sein wird. Aber ich wette, es wird schneller sein als ein Python-Listenverständnis.

Für die Bequemlichkeit, hier ist eine völlig allgemeine diagonals Funktion. Es geht davon aus, dass Sie die Diagonale entlang der längsten Achse bewegen möchten:

 def diagonals(a): rows, cols = a.shape if cols > rows: a = aT rows, cols = a.shape fill = numpy.zeros(((cols - 1), cols), dtype=a.dtype) stacked = numpy.vstack((a, fill, a)) major_stride, minor_stride = stacked.strides strides = major_stride, minor_stride * (cols + 1) shape = (rows + cols - 1, cols) return numpy.lib.stride_tricks.as_strided(stacked, shape, strides) 

Wie ich in einem Kommentar gepostet habe, würde ich nicht in C-Code gehen.

Versuche, mit PyPy zu gehen. Tatsächlich ist es numpy Unterstützung ist ruhig gut (aber es nicht unterstützen direkt array.diagonal) – Ich habe nicht überprüft, ob es andere Buidin-Methode für die. Nervenlos habe ich den folgenden Code ausprobiert:

 try: import numpypy # required by PyPy except ImportError: pass import numpy board = numpy.array([[0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 1, 0, 0]]) n=len(board) def diag_sum(i, b): s = 0 if i>=0: row = 0 end = n else: row = -i end = n+i i = 0 while i<end: s += b[row, i] i+=1 row+=1 return s import time t=time.time() for i in xrange(50000): # rate = [b.diagonal(i).sum() # for b in (board, board[::-1]) # for i in range(-n+1, n)] rate = [diag_sum(i,b) for b in (board, board[::-1]) for i in range(-n+1, n)] print time.time() - t 

Die Ergebnisse sind:

  • 0.64s PyPy mit diag_sum
  • 6.01s CPython Version mit diag_sum
  • 5.60s CPython Version mit b.diagonal
  • Python-Äquivalent von sum () mit xor ()
  • Python-Summe von Primzahlen
  • Wie würde ich ein mehrdimensionales Array in der prägnantesten Pythonschlange summieren?
  • Summe die Ziffern einer Zahl - Python
  • Summierende Fakultäten in Python
  • Python - Summe funktioniert nicht in der Liste Verständnis Syntax, wenn die Quelle Datei ist
  • Hinzufügen von Zahlen in einen String
  • Summe der Ziffern in einer Zeichenkette
  • Python-Datenrahmen: kumulative Summe der Spalte, bis die Bedingung erreicht ist und den Index zurückgibt
  • Wie kann ich sum () - Funktion für eine Liste in Python verwenden?
  • Python / Excel: Vergleichen Sie den angegebenen Wert mit dem summierten Wert
  • Python ist die beste Programmiersprache der Welt.