Eu gostaria de criar um bitmap durante o tempo de execução. O bitmap deve ser escalável em todos os lados e o acesso a pixels deve ser silenciosamente eficiente.
Alguma ilustração http://img546.imageshack.us/img546/4995/maptm.jpg
Entre e após os comandos mostrados na figura, Map.setPixel () e Map.getPixel () devem definir / retornar dados salvos no bitmap.
Não espero que uma implementação seja apenas um conceito de como alocar memória de forma que o setPixel () / getPixel seja o mais rápido possível.
extendX
métodos para tornar ossetPixel
egetPixel
mais rápidos?Respostas:
Se a
extend()
operação precisar ser razoavelmente rápida, um Quadtree pode ser uma boa opção; na verdade, nem exigiria operações de extensão explícitas. É certo que ele não produziria um desempenho ideal para acesso aleatório a pixels individuais, mas seu comentário diz que sua operação principal é iterativa sobre os pixels, o que um quadtree poderia fazer muito rápido, talvez quase tão rápido quanto uma implementação baseada em matriz (e mais rápido se a iteração nem sempre ocorrer da mesma maneira que a matriz é definida).Seus requisitos realmente parecem que você está tentando implementar um autômato celular como o Jogo da Vida. Você pode dar uma olhada no Hashlife , uma maneira de desempenho extremamente alto para implementar o Jogo da Vida em uma grade infinita. Observe que ele é baseado em um Quadtree, mas faz algumas otimizações adicionais muito inteligentes com base na localidade das regras do jogo.
fonte
A @SecStone disse que há tempo suficiente disponível para a operação de expansão; portanto, a maneira mais fácil e eficiente de armazenar os pixels é usar uma única matriz plana ou uma matriz bidimensional, pois os pixels podem ser acessados em tempo constante.
fonte
À mão
Se a memória não é um recurso muito escasso, considero trabalhar em partes maiores.
Aqui estão alguns pseudo-códigos.
Essa implementação é bastante ingênua.
Por um lado, ele cria chunks no getPixel (basicamente seria bom simplesmente retornar 0 ou mais, se nenhum chunks fosse definido para essa posição). Em segundo lugar, é baseado no pressuposto de que você possui uma implementação suficientemente rápida e escalável do Map. Que eu saiba, toda linguagem decente tem uma.
Além disso, você terá que jogar com o tamanho do pedaço. Para bitmaps densos, um tamanho grande de fragmento é bom; para bitmaps esparsos, um tamanho menor de fragmento é melhor. De fato, para os muito esparsos, um "tamanho de pedaço" igual a 1 é o melhor, tornando os "pedaços" obsoletos e reduzindo a estrutura de dados a um mapa int de um mapa int de pixels.
Fora da prateleira
Outra solução pode ser procurar em algumas bibliotecas gráficas. Eles são realmente muito bons em desenhar um buffer 2D em outro. Isso significaria que você simplesmente alocaria um buffer maior e teria o original desenhado nas coordenadas correspondentes.
Como estratégia geral: ao ter um "bloco de memória que cresce dinamicamente", é uma boa idéia alocar um múltiplo dele, uma vez usado. Isso é bastante intenso na memória, mas reduz significativamente os custos de alocação e cópia . A maioria das implementações de vetores aloca duas vezes seu tamanho, quando é excedida. Portanto, especialmente se você optar pela solução pronta para uso, não estenda seu buffer apenas em 1 pixel, porque apenas um pixel foi solicitado. A memória alocada é barata. Realocar, copiar e liberar é caro.
fonte
Apenas alguns conselhos:
Se você implementar isso como uma matriz de algum tipo integral (ou uma matriz de matrizes de ...), provavelmente deverá aumentar a matriz de backup em um número de bits / pixels por vez para evitar alterar os bits à medida que os copia. O lado negativo é que você usa mais espaço, mas a proporção de espaço desperdiçado diminui à medida que o bitmap aumenta.
Se você usar uma estrutura de dados baseada em mapa, poderá resolver o problema de aumentar o bitmap simplesmente realocando os argumentos das coordenadas x, y das chamadas
getPixel
esetPixel
.Se você usar uma estrutura de dados baseada em mapa, precisará apenas de entradas de mapa para as "unidades". Os "zeros" podem ser indicados pela ausência de uma entrada. Isso economiza uma quantidade significativa de espaço, especialmente se o bitmap for principalmente zeros.
Você não precisa usar um mapa de mapas. Você pode codificar um
int
par x, y como um únicolong
. Um processo análogo pode ser usado para mapear uma matriz de matrizes para uma matriz.Finalmente, você precisa equilibrar três coisas:
getPixel
esetPixel
,extend*
operações, efonte
Antes de tentar qualquer outra coisa mais complicada, e a menos que você não consiga guardar tudo na memória, mantenha as coisas simples e use uma matriz bidimensional juntamente com as informações sobre a origem do seu sistema de coordenadas. Para expandi-lo, use a mesma estratégia, como, por exemplo, o C ++ std :: vector: faça uma distinção entre o tamanho real de sua matriz e a capacidade da matriz e expanda a capacidade em blocos sempre que o limite for atingido. "capacidade" aqui deve ser definida em termos de intervalos (from_x, to_x), (from_y, to_y).
Isso pode precisar de uma realocação completa da memória de tempos em tempos, mas, desde que isso não ocorra com muita frequência, pode ser rápido o suficiente para o seu objetivo (na verdade, você deve tentar / criar um perfil).
fonte
A maneira mais rápida e absoluta de acessar pixels é uma matriz bidimensional de pixels endereçáveis individualmente.
Para extensões, comece com uma implementação simples que realoque e copie sempre (já que você precisará desse código). Se a criação de perfil não indicar que você está gastando muito tempo, não há necessidade de refinar ainda mais.
Se o perfil revelar uma necessidade de manter o número de realocações baixo e você não tiver restrição de memória, considere a alocação excessiva de uma porcentagem em cada direção e armazenar um deslocamento na origem. (Por exemplo, se você iniciar um novo bitmap em 1x1 e alocar uma matriz 9x9 para retê-lo, a inicial
x
e asy
compensações seriam4
.) A compensação aqui é ter que fazer cálculos extras durante o acesso ao pixel para aplicar a compensação.Se as extensões forem realmente caras, você pode tentar um ou ambos:
Manuseie extensões verticais e horizontais de maneira diferente. A extensão vertical de uma matriz em qualquer direção pode ser conseguida alocando um novo bloco e fazendo uma única cópia de toda a matriz existente para o deslocamento apropriado na nova memória. Compare isso com extensões horizontais, onde você deve executar essa operação uma vez por linha, porque os dados existentes não são contíguos no novo bloco.
Mantenha o controle da quantidade e direção de extensão mais frequentes. Use essas informações para selecionar um novo tamanho e deslocamento, o que reduzirá a probabilidade de ter que fazer uma re-alocação e cópia para qualquer extensão.
Pessoalmente, duvido que você precise de um deles, a menos que a taxa de acesso de pixel a extensão seja baixa.
fonte
Map.setPixel()
eMap.getPixel()
que modifica um pixel por vez, também forneça métodos que copiem e modifiquem um retângulo de pixels por vez. Isso permitirá que o chamador escolha a forma mais eficiente de acesso, dependendo das informações disponíveis para o chamador.(Não vamos votar nas respostas hilárias ...)
fonte
A implementação mais flexível e talvez confiável é uma lista vinculada com estruturas que fornecem coordenadas x, coordenadas y e valor de bits. Eu construiria isso primeiro e o faria funcionar.
Então, se for muito lento e / ou grande, tente as formas usuais de acelerar: matriz, matriz, bitmap, compactação, armazenamento em cache, inversão, armazenando apenas valores '1' etc.
É mais fácil fazer uma implementação correta lenta mais rapidamente do que consertar uma implementação rápida e com bugs. E ao testar sua segunda implementação 'rápida', você tem um padrão de referência para compará-lo.
E, quem sabe, você provavelmente descobrirá que a versão lenta é rápida o suficiente. Enquanto toda a estrutura se encaixa na memória, as coisas já são surpreendentemente rápidas.
fonte
Proponho a seguinte implementação em Python:
Tem as seguintes vantagens:
map[(1,2)]
pode ser consideradoO(1)
.fonte
Se você realmente precisa de um bitmap de qualquer tamanho arbitrário - e eu quero dizer algo entre 1x1 e 1000000x1000000 amd, e precisa ser expansível sob demanda ... uma maneira possível é usar um banco de dados. Pode parecer contra-intuitivo no começo, mas o que você realmente tem é um problema de armazenamento. Um banco de dados permitirá acessar pixels individuais e armazenar essencialmente qualquer quantidade de dados. Eu não quero dizer necessariamente um db SQL, btw.
Será rápido o suficiente para seus propósitos? Não posso responder, pois não há contexto aqui sobre o que você está fazendo com este bitmap. Mas, se for para exibição na tela, considere que geralmente você só precisará puxar as linhas adicionais de varredura para exibir à medida que a tela rola, e não todos os dados.
Dito isto, não posso deixar de me perguntar se você está fazendo algo errado. Talvez você deva usar gráficos baseados em vetor e rastrear entidades individuais na memória e renderizar um bitmap apenas do tamanho necessário para a tela?
fonte
Aqui estão as etapas para fazê-lo funcionar corretamente:
exemplo de implementação seria:
Obviamente, para uma implementação real, o XSize () e o YSize () não funcionariam, mas você precisará de MinX (), MaxX (), MinY (), MaxY () ou algo parecido para manter os números de índice consistentes.
fonte