Mapa de bits infinito [cerrado]

Me gustaría construir un mapa de bits durante el tiempo de ejecución. El mapa de bits debe ser escalable en todos los lados y el acceso de píxeles debe ser silencioso y eficiente.

Alguna ilustración http://img546.imageshack.us/img546/4995/maptm.jpg

Entre y después de los comandos que se muestran en la imagen, Map.setPixel () y Map.getPixel () deben establecer / devolver los datos guardados en el mapa de bits.

No espero una implementación, solo un concepto de cómo asignar memoria de tal manera que setPixel () / getPixel sea lo más rápido posible.

Si la extend()operación necesita ser razonablemente rápida, un Quadtree podría ser una buena opción; en realidad ni siquiera requeriría operaciones explícitas de extensión. Es cierto que no produciría un rendimiento óptimo para el acceso aleatorio a píxeles individuales, pero su comentario dice que su operación principal es iterar sobre los píxeles, lo que un quadtree podría hacer muy rápido, tal vez casi tan rápido como una implementación basada en matriz (y más rápido si la iteración no siempre ocurre de la misma manera que se presenta la matriz).

Sus requisitos en realidad suenan como si estuviera tratando de implementar un autómata celular como el Juego de la Vida. Es posible que desee echar un vistazo a Hashlife , una forma de alto rendimiento para implementar el Juego de la Vida en una cuadrícula infinita. Tenga en cuenta que se basa en un Quadtree, pero hace algunas optimizaciones adicionales muy inteligentes basadas en la localidad de las reglas del juego.

@SecStone dijo que hay suficiente tiempo disponible para la operación de expansión, por lo que la forma más fácil y eficiente de almacenar los píxeles es usar una única matriz plana o una matriz bidimensional, ya que se puede acceder a los píxeles en un tiempo constante.

Manualmente

Si la memoria no es un recurso muy escaso, considero trabajar en fragmentos más grandes.
Aquí hay un pseudocódigo.

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;
    }
}

Esta implementación es bastante ingenua.
Por un lado, crea fragmentos en getPixel (básicamente estaría bien simplemente devolver 0 más o menos, si no se definieron fragmentos para esa posición). En segundo lugar, se basa en el supuesto de que tiene una implementación de Map lo suficientemente rápida y escalable. Que yo sepa, cada idioma decente tiene uno.

También tendrás que jugar con el tamaño del fragmento. Para mapas de bits densos, un tamaño de fragmento grande es bueno, para mapas de bits dispersos es mejor un tamaño de fragmento más pequeño. De hecho, para los muy dispersos, un "tamaño de fragmento" de 1 es el mejor, ya que los "fragmentos" quedan obsoletos y reducen la estructura de datos a un mapa int de un mapa int de píxeles.

Fuera de la plataforma

Otra solución podría ser mirar algunas bibliotecas de gráficos. En realidad, son bastante buenos para dibujar un búfer 2D en otro. Eso significaría que simplemente asignaría un búfer más grande y dibujaría el original en las coordenadas correspondientes.

Como estrategia general: cuando se tiene un "bloque de memoria en crecimiento dinámico", es una buena idea asignar un múltiplo de él, una vez que se agota. Esto es bastante intenso en memoria, pero reduce significativamente los costos de asignación y copia . La mayoría de las implementaciones de vectores asignan el doble de su tamaño, cuando se supera. Por lo tanto, especialmente si opta por la solución estándar, no extienda su búfer solo 1 píxel, porque solo se solicitó un píxel. La memoria asignada es barata. Reasignar, copiar y liberar es costoso.

Solo un par de puntos de consejo:

• Si implementa esto como una matriz de algún tipo integral (o una matriz de matrices de ...) probablemente debería aumentar la matriz de respaldo en un cierto número de bits / píxeles cada vez para evitar tener que cambiar los bits a medida que los copia. La desventaja es que usa más espacio, pero la proporción de espacio desperdiciado disminuye a medida que el mapa de bits se hace más grande.

• Si utiliza una estructura de datos basada en mapas, puede resolver el problema de aumentar el mapa de bits simplemente reubicando los argumentos de coordenadas x, y de las llamadas getPixely setPixel.

• Si utiliza una estructura de datos basada en mapas, solo necesita entradas de mapa para los "unos". Los "ceros" pueden indicarse por la ausencia de una entrada. Esto ahorra una cantidad significativa de espacio, especialmente si el mapa de bits es principalmente ceros.

• No necesita usar un mapa de mapas. Puede codificar un intpar x, y como un solo long. Se puede utilizar un proceso análogo para mapear una matriz de matrices a una matriz.

Finalmente, necesitas equilibrar 3 cosas:

1. el desempeño de getPixely setPixel,
2. el desempeño de las extend*operaciones, y
3. La utilización del espacio.

Antes de intentar algo más complicado, y a menos que no pueda guardar todo en la memoria, mantenga las cosas simples y use una matriz bidimensional junto con la información sobre el origen de su sistema de coordenadas. Para expandirlo, use la misma estrategia como, por ejemplo, el C ++ std :: vector hace: hacer una distinción entre el tamaño real de su matriz y la capacidad de la matriz, y expandir la capacidad en fragmentos cada vez que se alcanza el límite. "capacidad" aquí debe definirse en términos de intervalos (from_x, to_x), (from_y, to_y).

Esto puede necesitar una reasignación completa de la memoria de vez en cuando, pero siempre que esto no suceda con demasiada frecuencia, puede ser lo suficientemente rápido para su propósito (de hecho, debe probar / perfilar esto).

La forma más rápida de acceder a píxeles es una matriz bidimensional de píxeles direccionables individualmente.

Para las extensiones, comience con una implementación simple que reasigne y copie cada vez (ya que necesitará ese código de todos modos). Si la elaboración de perfiles no indica que está pasando mucho tiempo en ello, no hay necesidad de refinarlo más.

Si la creación de perfiles revela la necesidad de mantener baja la cantidad de reasignaciones y no tiene limitaciones de memoria, considere la asignación excesiva en un porcentaje en cada dirección y almacene un desplazamiento al origen. (Por ejemplo, si comienza un nuevo mapa de bits en 1x1 y asigna una matriz de 9x9 para mantenerlo, la inicial xy las ycompensaciones serían 4). La compensación aquí es tener que hacer cálculos matemáticos adicionales durante el acceso de píxeles para aplicar el desplazamiento.

Si las extensiones resultan ser realmente caras, puede probar uno o ambos de estos:

• Maneje las extensiones verticales y horizontales de manera diferente. La extensión de una matriz verticalmente en cualquier dirección se puede lograr asignando un nuevo bloque y haciendo una sola copia de toda la matriz existente al desplazamiento apropiado en la nueva memoria. Compare eso con las extensiones horizontales, donde tiene que hacer esa operación una vez por fila porque los datos existentes no son contiguos en el nuevo bloque.

• Mantenga un registro de la cantidad y dirección de extensión más frecuentes. Use esa información para seleccionar un nuevo tamaño y desplazamiento que reducirá la probabilidad de tener que reasignar y copiar cualquier extensión.

Personalmente, dudo que necesite alguno de esos, a menos que la relación de acceso de píxeles a extensión sea baja.

• Tamaño constante de mosaico (por ejemplo, 256x256, pero con infinidad de azulejos)
• Proporcione un contenedor de mapa de bits que permita coordenadas de píxeles negativas (para dar la impresión de que una imagen se puede expandir en las cuatro direcciones sin tener que volver a calcular / sincronizar referencias a valores de coordenadas existentes)
  • Sin embargo, la clase de mapa de bits real (que funciona debajo del contenedor) solo debe admitir coordenadas absolutas (no negativas).
• Debajo del contenedor, proporcione acceso a nivel de mosaico (nivel de bloque) utilizando E / S mapeadas en memoria
• Además de Map.setPixel()y Map.getPixel()que modifica un solo píxel a la vez, también proporciona métodos que copian y modifican un rectángulo de píxeles a la vez. Esto permitirá a la persona que llama elegir la forma más eficiente de acceso dependiendo de la información disponible para la persona que llama.
  • Las bibliotecas comerciales también brindan métodos para actualizar: una fila de píxeles, una columna de píxeles, actualizaciones de dispersión / recopilación y operaciones aritméticas / lógicas blitter en un solo paso (para minimizar la copia de datos).

(No votemos por las divertidísimas respuestas ...)

La implementación más flexible y quizás más confiable es una lista vinculada con estructuras que dan coordenadas x, coordenadas y y valor de bit. Construiría eso primero y lo haría funcionar.

Luego, si es demasiado lento y / o grande, pruebe las formas habituales de acelerarlo: matriz, matriz, mapa de bits, compresión, almacenamiento en caché, inversión, almacenando solo valores '1', etc.

Es más fácil hacer una implementación lenta y correcta más rápido que arreglar una implementación rápida con errores. Y mientras prueba su segunda implementación 'rápida', tiene un estándar de referencia para compararlo.

Y, quién sabe, probablemente descubrirá que la versión lenta es lo suficientemente rápida. Mientras toda la estructura encaje en la memoria, las cosas ya son increíblemente rápidas.

Propongo la siguiente implementación en Python:

class Map(dict): pass

Tiene las siguientes ventajas:

1. Obtener / Establecer acceso a través de map[(1,2)]puede ser considerado O(1).
2. La necesidad de extender explícitamente la cuadrícula desaparece.
3. Hay poco espacio para errores.
4. Se actualiza fácilmente a 3D, si alguna vez es necesario.

Si realmente necesita un mapa de bits de cualquier tamaño arbitrario, y me refiero a cualquier cosa, desde 1x1 hasta 1000000x1000000 amd, y lo necesita expandible a pedido ... una posible forma es usar una base de datos. Puede parecer contradictorio al principio, pero lo que realmente tiene es un problema de almacenamiento. Una base de datos le permitirá acceder a píxeles individuales y almacenar esencialmente cualquier cantidad de datos. No necesariamente me refiero a un SQL db, por cierto.

¿Será lo suficientemente rápido para tus propósitos? Eso no puedo responder, ya que no hay contexto aquí con respecto a lo que está haciendo con este mapa de bits. Pero si esto es para la visualización de la pantalla, considere que generalmente solo necesitaría retirar las filas de escaneo adicionales para mostrar a medida que la pantalla se desplaza, no todos los datos.

Dicho esto, no puedo evitar preguntarme si estás haciendo algo mal. ¿Debería, en cambio, usar gráficos vectoriales y rastrear entidades individuales en la memoria, y luego renderizar un mapa de bits tan grande como sea necesario para la pantalla?

Aquí hay pasos para que funcione correctamente:

1. use el reenvío de una interfaz a otra para construir un árbol de objetos que juntos representan el mapa de bits
2. cada "extensión" del mapa de bits asignará su propia memoria y le proporcionará otra interfaz

3. ejemplo de implementación sería:

   template<class T, class P>
   class ExtendBottom {
   public:
      ExtendBottom(T &t, int count) : t(t), count(count),k(t.XSize(), count) { }
      P &At(int x, int y) const { if (y<t.YSize()) return t.At(x,y); else return k.At(x, y-t.YSize()); }
      int XSize() const { return t.XSize(); }
      int YSize() const { return t.YSize()+count; }
   private:
      T &t;
      int count;
      MemoryBitmap k;
   };
   

Obviamente para una implementación real, XSize () y YSize () no funcionarían, pero necesitará MinX (), MaxX (), MinY (), MaxY () o algo así para mantener los números de índice consistentes.