A mano
Se la memoria non è una risorsa molto sparsa, considero di lavorare in blocchi più grandi.
Ecco alcuni pseudo-codice.
class Chunk {
Chunk new(int size) {...}
void setPixel(int x, int y, int value) {...}
int getPixel(int x, int y) {...}
}
class Grid {
Map<int, Map<Chunk>> chunks;
Grid new(int chunkSize) {...}
void setPixel(int x, int y, int value) {
getChunk(x,y).setPixel(x % chunkSize, y % chunkSize, value);//actually the modulo could be right in Chunk::setPixel and getPixel for more safety
}
int getPixel(int x, int y) { /*along the lines of setPixel*/ }
private Chunk getChunk(int x, int y) {
x /= chunkSize;
y /= chunkSize;
Map<Chunk> row = chunks.get(y);
if (row == null) chunks.set(y, row = new Map<Chunk>());
Chunk ret = row.get(x);
if (ret == null) row.set(x, ret = new Chunk(chunkSize));
return ret;
}
}
Questa implementazione è abbastanza ingenua.
Per esempio, crea blocchi in getPixel (in pratica sarebbe meglio restituire 0 o così, se non fosse stato definito alcun blocco per quella posizione). In secondo luogo, si basa sul presupposto che si disponga di un'implementazione della mappa sufficientemente rapida e scalabile. A mia conoscenza, ogni lingua decente ne ha uno.
Inoltre dovrai giocare con la dimensione del blocco. Per bitmap densi, una grande dimensione del blocco è buona, per bitmap sparse una dimensione del blocco più piccola è migliore. Infatti per quelli molto sparsi, una "dimensione del blocco" di 1 è la migliore, rendendo i "blocchi" stessi obsoleti e riducendo la struttura dei dati a una mappa int di una mappa int di pixel.
Off the shelf
Un'altra soluzione potrebbe essere quella di esaminare alcune librerie grafiche. In realtà sono abbastanza bravi a disegnare un buffer 2D in un altro. Ciò significherebbe che dovresti semplicemente allocare un buffer più grande e avere l'originale disegnato in base alle coordinate corrispondenti.
Come strategia generale: quando si ha un "blocco di memoria a crescita dinamica", è una buona idea allocarne un multiplo, una volta esaurito. Questo è piuttosto intenso nella memoria, ma riduce significativamente i costi di allocazione e copia . La maggior parte delle implementazioni di vettori assegnano il doppio delle loro dimensioni, quando viene superata. Quindi, soprattutto se si utilizza la soluzione standard, non estendere il buffer solo di 1 pixel, poiché è stato richiesto un solo pixel. La memoria allocata è economica. La riallocazione, la copia e il rilascio sono costosi.
