Wie kann ich diese große Array-Berechnung vektorisieren und beschleunigen?
Ich versuche gerade die Summe aller Subquadrate in einem 10.000 x 10.000 Array von Werten zu berechnen . Als Beispiel, wenn mein Array war:
%Vor%Ich möchte, dass das Ergebnis lautet:
%Vor%Also, als ersten Versuch habe ich einen sehr einfachen Python-Code dafür geschrieben. Wie es in O (k ^ 2.n ^ 2) war (n ist die Größe des großen Arrays und k die Größe der Subquadrate, die wir bekommen), war die Verarbeitung furchtbar lang. Ich schrieb einen anderen Algorithmus in O (n ^ 2), um es zu beschleunigen:
%Vor%Dieser Code funktioniert also gut. Bei einem Array und einer Größe von Unterquadraten wird die Summe der Werte in allen Unterquadraten zurückgegeben. Ich iteriere im Grunde über die Größe von Unterquadraten, um alle möglichen Werte zu erhalten.
Das Problem ist, dass es sich wiederum für große Arrays (mehr als 20 Tage für ein 10.000 x 10.000 Array) lang dauern sollte. Ich habe es gegoogelt und gelernt, dass ich die Iterationen über Arrays mit numpy vektorisieren kann. Allerdings konnte ich nicht herausfinden, wie es in meinem Fall so gemacht wird ...
Wenn jemand mir helfen kann, meinen Algorithmus zu beschleunigen oder mir eine gute Dokumentation zu dem Thema zu geben, werde ich froh sein!
Danke!
3 Antworten
Diese gleitenden Summierungen sind am besten geeignet, um als 2D-Faltungssummationen berechnet zu werden, und diese können effizient mit scipy's convolve2d . So könnten Sie für eine bestimmte Größe die Summierungen erhalten, so -
Um Summierungen über alle Größen hinweg zu erzielen, wäre es meiner Meinung nach der beste Weg, sowohl hinsichtlich Speicher als auch Leistungseffizienz eine Schleife zu verwenden, um alle möglichen Größen zu durchlaufen. Um also die endgültige Summe zu erhalten, hättest du -
%Vor%Beispiellauf -
%Vor%Nach der hervorragenden Idee von @Divakar würde ich vorschlagen, integrale Bilder zu verwenden, um die Windungen zu beschleunigen. Wenn die Matrix sehr groß ist, müssen Sie sie mehrmals falten (einmal für jede Kerngröße). Mehrere Faltungen (oder Auswertungen von Summen innerhalb eines Quadrats) können sehr effizient unter Verwendung integraler Bilder berechnet werden (aka summierte Flächentabellen).
Sobald ein Integralbild M berechnet ist, kann die Summe aller Werte innerhalb einer Region (x0, y0) - (x1, y1) mit nur 4 arithmetischen Berechnungen berechnet werden, unabhängig von der Größe des Fensters (Bild aus Wikipedia):
Dies kann sehr einfach in numpy vektorisiert werden. Ein integriertes Bild kann mit cumsum berechnet werden. Nach dem Beispiel:
M wird mit einer Zeile und einer Spalte von Nullen aufgefüllt, um die erste Zeile zu verarbeiten (wobei x0 = 0 oder y0 = 0 ).
Bei einer Fenstergröße W kann die Summe jedes Fensters der Größe W effizient berechnet und vollständig mit numpy als:
Man beachte, dass die oben beschriebene vektorisierte Operation die Summe jedes Fensters berechnet, d. h. jedes A, B, C und D der Matrix. Die Summe aller Fenster wird dann als
berechnet %Vor% Beachten Sie, dass für N verschiedene Größen, anders als bei Faltungen, das Integralbild nur einmal berechnet werden muss. Daher kann der Code sehr effizient geschrieben werden als:
Die Ausgabe für das Beispiel:
%Vor% Einige Timings, die Faltungen mit Integralbildern mit Matrizen unterschiedlicher Größe vergleichen. getAllSums bezieht sich auf die Faltungs-Methode von Divakar, während get_all_sums auf die oben beschriebene integral-images-basierte Methode verweist:
1) Mit R1 10x10 Matrix:
2) Mit R2 100x100 Matrix:
Beachten Sie, dass die Verwendung von integrierten Bildern 300 Mal schneller ist als die von Faltungen für Matrizen, die groß genug sind.
Basierend auf der Idee, zu berechnen, wie oft jede Zahl gezählt wurde, kam ich zu diesem einfachen Code:
%Vor%Divakars Lösung ist fantastisch, aber ich denke, meins könnte effizienter sein, zumindest in asymptotischer Zeitkomplexität (O (n ^ 3) verglichen mit Divakars O (n ^ 3logn)).
Ich bekomme jetzt eine O (n ^ 2) Lösung ...
Grundsätzlich können wir das bekommen:
%Vor% Sie können sehen, dass sum(min(k, x) * min(k, y)) in O (1) berechnet werden kann, wenn 1 & lt; = k & lt; = n / 2
Also sind wir zu diesem O (n ^ 2) -Code gekommen:
%Vor%Test:
%Vor%Sie können meinen O (n ^ 2) Python-Code in C umschreiben und ich glaube, es wird eine sehr effiziente Lösung ergeben ...
Tags und Links python algorithm arrays numpy vectorization