Wie kann ein Raster effizient berechnet werden (in Python), wenn ein Satz aus Milliarden von Begrenzungsrahmen besteht (nacheinander aus einer Datei gelesen) und die Rasterwerte für jede Zelle die Anzahl der überlappenden Begrenzungsrahmen angeben?
Für ein 4000 * 4000 Raster
Ich habe die Erstellung der Numpy-Matrix zeitlich festgelegt:
$ python -m timeit 'import numpy' 'a = numpy.zeros(shape=(4000,4000))'
10 loops, best of 3: 51.7 msec per loop
Standard-Python-Matrix-Erstellung:
$ python -m timeit 'a = 4000*[0]' 'for i in range(4000):' ' a[i]=4000*[0]'
10 loops, best of 3: 218 msec per loop
Numpy ist also schneller, aber immer noch 50 ms pro Schleife mit einer Milliarde Iterationen ergeben eine Laufzeit von etwa einem Jahr (0,05 ms * 1000000000/60/60/24/365 = 1,5 Jahre).
Es ist also keine Option, jedes Polygon abzutasten. Was ist ein typischer Ansatz für dieses Problem?
Antworten:
Sie
timeitenthalten den Numpy-Import, der zusätzlichen Aufwand verursachen würde. Warum schreiben Sie nicht den Code für eine Teilmenge der Begrenzungsrahmen und die Zeit dieser Schleife und multiplizieren ihn dann, um die Gesamtlaufzeit zu schätzen?Das Lösen auf einem einzelnen Computer erfolgt naturgemäß seriell, und mit einer relativ einfachen Operation erhalten Sie möglicherweise keine signifikante Optimierung durch einen bereits einfachen Algorithmus. Sie könnten versuchen, es in eine Art manuellen Kartenreduzierungsvorgang aufzuteilen (ich weiß, dass Sie eine Einschränkung "Keine Kartenreduzierung" haben) und so viele Instanzen auszuführen, wie Sie Kerne haben. Das Mosaikieren / Zusammenführen von n Rastern (der Reduzierungsschritt) ist eine trivial schnelle Operation. Dies ist für den Code wahrscheinlich weniger schmerzhaft als eine Multithread-Lösung.
Alternativ (oder zusätzlich) könnten Sie ein Programm schreiben, um bestimmte Begrenzungsrahmen wie überlappende oder verschachtelte zu kombinieren - dies würde einen räumlichen Index erfordern. Wenn Sie keine haben, ist es möglicherweise von Vorteil, eine zu erstellen, insbesondere wenn Sie den Hauptalgorithmus lokal parallelisieren.
Entlassen Sie auch die Parallelisierung mehrerer Computer nicht ohne weiteres. Wenn Ihre beste Schätzung mehr als ein Jahr beträgt, müssen Sie addieren, wie viel Geld Ihre Zeit für die Ausführung der Einzelcomputerversion kostet, und sie gegen die Einstellung von Cloud-Rechenzeit abwägen. Wie @whuber sagt, werden 1024 GPUs die Daten so schnell durchsuchen, dass Sie so gut wie nichts kosten, selbst wenn Sie eine Woche damit verbringen, sich mit CUDA vertraut zu machen. Wenn es Ihr Chef ist, der Ihnen verbietet, es auf mehr als einem Computer zu versuchen, führen Sie die Kostenanalyse durch und geben Sie ihm einige harte Zahlen - er wird dann den Wert der Daten gegen den Wert Ihrer Zeit abwägen.
quelle
Wenn ich das richtig verstanden habe, möchten Sie Ihre Milliarden Begrenzungsrahmen zu einem Bild rendern. Anstatt jedes Polygon über eine Zelle (Pixel) zu "malen", zählen (oder akkumulieren) Sie sie.
Sie können (relativ) einfachen Code (in OpenGL, Vulcan, Direct3D) verwenden, um die Polygone zu rendern und die Anzahl im Schablonenpuffer zu akkumulieren. Achten Sie darauf, dass Polygone genau auf die Pixelgrenzen fallen, und wählen Sie einen Datentyp für den Schablonenpuffer, damit die Anzahl nicht überläuft. Ich würde erwarten, dass es in wenigen Sekunden auf einer einzelnen GPU ausgeführt wird ...
quelle