Muestreo rasterizado eficiente de miles de millones de polígonos (cuadros delimitadores)

Question

¿Cómo se puede calcular un raster de forma eficiente (en Python), dado un conjunto formado por miles de millones de cuadros delimitadores (leídos secuencialmente de un archivo), y dado que los valores del raster para cada celda deben dar el número de cuadros delimitadores superpuestos?

Para una trama de 4000 * 4000

He cronometrado la creación de la matriz numpy:

$ python -m timeit 'import numpy' 'a = numpy.zeros(shape=(4000,4000))'
10 loops, best of 3: 51.7 msec per loop

Creación de matrices estándar en python:

$ python -m timeit 'a = 4000*[0]' 'for i in range(4000):' ' a[i]=4000*[0]'
10 loops, best of 3: 218 msec per loop

Así que numpy es más rápido, pero todavía 50 mseg por bucle, con mil millones de iteraciones, produce un tiempo de ejecución igual a un año (0,05mseg * 1000000000 / 60 / 60 / 24 / 365 = 1,5 años)

Así que no es una opción muestrear cada polígono. ¿Cuál es el enfoque típico para este problema?

Answer 1

Su timeit incluye la importación de numpy, lo que añadiría cierta sobrecarga. Así que, ¿por qué no escribes el código para un subconjunto de los cuadros delimitadores y cronometras ese bucle, y luego lo multiplicas para estimar el tiempo total de ejecución?

Resolverlo en un solo ordenador es, por su naturaleza, en serie, y con una operación relativamente sencilla, es posible que no se obtenga ninguna optimización significativa de un algoritmo ya de por sí sencillo. Podrías intentar dividirlo en una especie de operación manual de map-reduce (sé que tienes una advertencia de "no map-reduce"), y ejecutar tantas instancias como núcleos tengas. Mosaico/fusión n (el paso de reducción) es una operación trivial y rápida. Esto probablemente será menos doloroso de codificar que una solución multihilo.

Alternativamente (o adicionalmente), se podría escribir un programa para combinar ciertas cajas delimitadoras como las superpuestas o anidadas - esto requeriría un índice espacial. Si no tienes uno, puede que crear uno te resulte beneficioso, especialmente si acabas paralelizando localmente el algoritmo principal.

Además, no hay que descartar de plano la paralelización en varios ordenadores. Si tu mejor estimación es de más de un año, entonces tienes que sumar el dinero que te costará la versión de un solo ordenador y sopesarlo con la contratación de tiempo de computación en la nube. Como dice @whuber, 1024 GPUs se llevarán los datos tan rápidamente que no te costará casi nada, incluso si te pasas una semana dándole vueltas a CUDA. Si es tu jefe el que te prohíbe probarlo en más de un ordenador, haz el análisis de costes y entrégale algunos números concretos; entonces sopesará el valor de los datos frente al valor de tu tiempo.

Answer 2

Si he entendido bien, lo que quieres es como renderizar tu conjunto de miles de millones de cajas delimitadoras a una imagen. Sólo que en lugar de "pintar" cada polígono sobre una celda (píxel) los cuentas (o acumulas).

Puedes utilizar un código (relativamente) sencillo (en OpenGL, Vulcan, Direct3D) para renderizar los polígonos y acumular el recuento en el buffer del stencil. Ten cuidado para que los polígonos caigan exactamente en los límites de los píxeles, y elige un tipo de datos para el búfer del stencil para que el recuento no se desborde. Yo esperaría que se ejecute en unos pocos segundos en una sola GPU...