Como uma varredura pode ser computada com eficiência (em Python), considerando um conjunto que consiste em bilhões de caixas delimitadoras (lidas sequencialmente em um arquivo) e considerando que os valores da varredura para cada célula devem fornecer o número de caixas delimitadoras sobrepostas?
Para uma varredura de 4000 * 4000
Eu cronometrei a criação de matriz numpy:
$ python -m timeit 'import numpy' 'a = numpy.zeros(shape=(4000,4000))'
10 loops, best of 3: 51.7 msec per loopCriação de matriz python padrão:
$ python -m timeit 'a = 4000*[0]' 'for i in range(4000):' ' a[i]=4000*[0]'
10 loops, best of 3: 218 msec per loopTão entorpecido é mais rápido, mas ainda assim 50 mseg por loop, com um bilhão de iterações, gera um tempo de execução igual a cerca de um ano (0,05 ms * 1000000000/60/60/24/365 = 1,5 anos)
Portanto, não é uma opção para provar cada polígono. Qual é uma abordagem típica para esse problema?
Respostas:
Você
timeitinclui a importação numpy, o que adicionaria alguma sobrecarga. Então, por que você não escreve o código para um subconjunto das caixas delimitadoras e o tempo desse loop e multiplica-o para estimar o tempo total de execução?Resolvê-lo em um único computador é, por natureza, serial e, com uma operação relativamente simples, você pode não obter nenhuma otimização significativa de um algoritmo já simples. Você pode tentar dividi-lo em uma espécie de operação manual de redução de mapa (eu sei que você tem uma ressalva "sem redução de mapa") e executar o número de instâncias que tiver núcleos. Fazer mosaicos / mesclar n rasters (a etapa de redução) é uma operação trivialmente rápida. Provavelmente será menos doloroso para codificar do que uma solução multiencadeada.
Como alternativa (ou adicionalmente), você pode escrever um programa para combinar certas caixas delimitadoras, como sobrepostas ou aninhadas - isso exigiria um índice espacial. Se você não tiver um, pode ser útil criar um benéfico, especialmente se você acabar localizando paralelamente o algoritmo principal.
Além disso, não descarte a paralelização de vários computadores imediatamente. Se sua melhor estimativa for superior a um ano, você precisará adicionar quanto dinheiro seu tempo custará na execução da versão para computador único e ponderá-la contra a contratação de algum tempo de computação em nuvem. Como o @whuber diz, 1024 GPUs analisam os dados tão rapidamente que custam quase nada, mesmo que você gaste uma semana tentando entender a CUDA. Se o seu chefe o proibir de experimentá-lo em mais de um computador, faça a análise de custos e entregue a ele alguns números concretos - ele então pesará o valor dos dados contra o valor do seu tempo.
fonte
Se bem entendi, o que você quer é como renderizar seu conjunto de bilhões de caixas delimitadoras em uma imagem. Exceto que, em vez de "pintar" cada polígono sobre uma célula (pixel), você os conta (ou acumula).
Você pode usar código (relativamente) simples (em OpenGL, Vulcan, Direct3D) para renderizar os polígonos e acumular a contagem no buffer de estêncil. Cuidado para que os polígonos caiam exatamente nos limites de pixel e escolha um tipo de dados para o buffer de estêncil para que a contagem não ultrapasse. Eu esperaria que ele fosse executado em alguns segundos em uma única GPU ...
fonte