¿Estructura de datos para almacenar una gran cantidad de datos?

Question

En mi aplicación, tengo que cargar datos volumétricos del conjunto de imágenes (imágenes MRC) y mantener los datos de píxeles en la memoria (las imágenes se escalan en grises, por lo tanto, un byte por píxel).

Mi entorno de desarrollo es QT framework, MinGW para Windows y GCC para Linux.

Por el momento, utilizo una estructura de datos sencilla para almacenar volumedata como:

unsigned char *volumeData; 

y realice una enorme asignación de la siguiente manera.

volumeData=new unsigned char[imageXsize * imageYsize * numofImages]; 

Los siguientes son los métodos importantes para acceder a los datos de imagen-en un plano dado, como

unsigned char* getXYPlaneSlice(int z_value); 
unsigned char* getYZPlaneSlice(int x_value); 
unsigned char* getZXPlaneSlice(int y_value); 

Con mi simple estructura de datos que era fácil de implementar métodos anteriores.

Pero es posible que tengamos que adoptar un tamaño de volumen como 2000x2000x1000 (~ 3.7Gb) en el futuro. Y la estructura de datos actual no podrá manejar esos enormes datos.

1. Cómo evitar la fragmentación? Ahora, incluso con datos de 1000x1000x200, la falla de la aplicación da como resultado bad_alloc. ¿Cuál es la mejor manera de cambiar la estructura de datos para esto? ¿Debería usar algo así como lista enlazada que cada pedazo es de tamaño 100mb?

2. Además, el usuario debe ser capaz de perfumar algunos filtros de procesamiento de imágenes en los datos de volumen y también debe ser capaz de restablecer el valor de píxel original. Eso significa que debería conservar dos copias de datos de volumen. Con la implementación actual es similar.

   unsigned char * volumeDataOriginal;

   unsigned char * volumeDataCurrent;

Con un rango de datos de 2000x2000x1000 va a utilizar aproximadamente 8 Gb (4 Gb por cada volumen). Pero en Win32, el espacio de direcciones es de 4 GB. ¿Cómo abordar esto? Debo ir con la aplicación de 64 bits?

EDIT: Aquí es una instantánea de mi solicitud

Básicamente, me carga los datos de volumen-(de conjunto de imágenes, de MRC format..etc) y mostrarlos en diferentes planas-espectadores (XY , YX, YZ.La imagen muestra XY-plane-viewer). Necesito mantener por encima de 3 métodos de acceso a datos para mostrar una imagen en un plano particular.utilizando el usuario de la barra deslizante puede cambiar qué imagen mostrar en el plano seleccionado)

Gracias de antemano.

Answer 1

La solución más simple a su problema sería utilizar espacios de direcciones de 64 bits: los Mac modernos admiten esto de fábrica, en Windows y Linux necesitarán instala la versión de 64 bits del sistema operativo. Creo que Qt puede usarse para crear aplicaciones de 64 bits bastante bien. Los sistemas de 32 bits no podrán admitir asignaciones únicas del tamaño del que estás hablando, incluso una Mac con 4 GB de espacio de direcciones disponible para las aplicaciones no podrá realizar una sola asignación de 3.7 GB ya que no habrá ser un espacio contiguo de ese tamaño disponible.

Para deshacer Me gustaría ver el uso de archivos mapeados en memoria y copia en escritura para copiar el bloque:

http://en.wikipedia.org/wiki/Copy-on-write

Esto significa que en realidad no tiene que copiar todos los datos originales, el sistema hará copias de las páginas tal como están escritas. Esto ayudará mucho al rendimiento si sus imágenes son significativamente más grandes que la memoria real y no está cambiando cada parte de la imagen. Parece que boost::map_file con acceso "privado" puede ser útil para esto.

Si realmente necesita admitir sistemas de 32 bits, su única alternativa es romper esos grandes bloques de alguna manera, generalmente en planos o subvolúmenes. Sin embargo, es horrible trabajar con ellos cuando se trata de aplicar filtros 3D, etc., así que realmente evitaría esto si es posible.

Si va por la ruta del subvolúmen, un truco es guardar todos los subvolúmenes en archivos mapeados en memoria, y asignarlos a su espacio de direcciones solo cuando los necesite. Cuando no se asignan desde el espacio de direcciones deben permanecer en la memoria caché unificada hasta que se purguen, esto significa que puede utilizar más RAM que espacio de direcciones (particularmente en Windows donde las aplicaciones de 32 bits solo obtienen 2 GB de espacio de direcciones de manera predeterminada) .

Finalmente, en Windows de 32 bits también puede ver el modificador/3GB en boot.ini. Esto le permite asignar 3 GB de espacio de direcciones a las aplicaciones en lugar de los 2 GB normales. A partir del problema que describes, no creo que esto te proporcione suficiente espacio de direcciones, sin embargo, puede ayudarte con algunos volúmenes más pequeños. Tenga en cuenta que el modificador/3GB puede causar problemas con algunos controladores, ya que reduce la cantidad de espacio de direcciones disponible para el kernel.

Answer 2

64 bit es probablemente la forma más fácil de manejar esto ... deje que el SO falle en las páginas a medida que las utiliza. De lo contrario, es difícil ofrecer mucho sin conocer sus patrones de acceso a través de los datos. Si está escaneando regularmente las imágenes para encontrar el valor en las mismas coordenadas de píxel, no tiene sentido hablar de decir punteros a las imágenes que se guardan y vuelven a cargar a pedido.

Para los datos de deshacer, puede mantener una copia de seguridad completa tal como sugiere, o podría intentar tener una operación de deshacer que observe el cambio realizado y sea responsable de encontrar una implementación eficiente. Por ejemplo, si solo volteaste los bits, entonces eso no es destructivo y solo necesitas un funtor para la misma operación de inversión de bits para deshacer el cambio. Si configurar todos los píxeles al mismo tono era una operación común (por ejemplo, relleno, borrado), entonces podría tener un booleano y un píxel único para codificar ese estado de imagen, y usar el búfer completo para deshacer.

Answer 3

Creo que debería echar un vistazo a hdf5. Este es un formato binario para almacenar grandes cantidades de datos recopilados de cosas como telescopios, experimentos de física y máquinas de secuenciación de genes. Los beneficios de usar algo como esto son muchos, pero tres pensamientos inmediatos son: (1) probado, (2) admite la selección de hipersaltos, y (3) obtiene la compresión de forma gratuita.

Hay librerías C/C++, java, python, matlab disponibles.

Answer 4

Una opción que consideraría es la asignación de memoria, en lugar de mapear todas las imágenes, mantener una lista vinculada de imágenes que están cargadas de forma perezosa. A medida que su filtro funciona a través de la lista de imágenes, cárguelo según sea necesario. En la fase de carga, mapee un bloque anónimo (o de algún archivo temporal fijo) del mismo tamaño y copie la imagen como copia de seguridad. Y a medida que aplica los filtros, solo hace una copia de seguridad de esta copia. Como @Tony dijo anteriormente, 64 bits es tu mejor opción, y para los archivos mapeados en la plataforma multiplataforma, mira impulsar el interproceso.

Answer 5

Puede usar una memoria de archivos asignados para administrar grandes conjuntos de datos con memoria limitada. Sin embargo, si el tamaño de sus archivos va a ser de 4 GB, se recomienda ir a 64 bits. El proyecto de impulso tiene una buena biblioteca de mapas de memoria multiplataforma que funciona muy cerca de lo que estás buscando.

http://en.wikipedia.org/wiki/Memory-mapped_file http://www.boost.org/doc/libs/1_44_0/libs/iostreams/doc/classes/mapped_file.html para que pueda empezar. Un código de ejemplo a continuación -

#include <boost/iostreams/device/mapped_file.hpp> 
boost::iostreams::mapped_file_source input_source; 
input_source.open(std::string(argv[1])); 
const char *data = input_source.data(); 
long size = input_source.size(); 
input_source.close(); 

Gracias, Nathan

Answer 6

Usted podría utilizar una estructura de dos niveles: una matriz de punteros a las imágenes individuales o (mucho mejor) un montón de imágenes. Para que pueda mantener, es decir, 20 imágenes en un bloque de memoria y poner los punteros a los 20 bloques de imágenes en el conjunto. Esto sigue siendo rápido (en comparación con una lista vinculada) cuando se realiza un acceso aleatorio.

A continuación, puede implementar un algoritmo de paginación simple: Al principio, todos los punteros de la matriz son NULL. Cuando accede por primera vez a un bloque de imágenes, carga las 20 imágenes de ese bloque en la memoria y escribe el puntero en la matriz. El siguiente acceso a esas imágenes no carga nada.

Si su memoria baja porque ha cargado y cargado muchos bloques de imágenes puede eliminar el bloque de imágenes que menos ha utilizado (debe agregar un segundo campo al lado del puntero donde ingrese el valor de un contador que usted cuenta cada vez que carga un bloque de imagen). El bloque de imagen con el contador más bajo es el menos utilizado y puede soltarse (la memoria se reutiliza para el nuevo bloque y el puntero se establece en NULO).

Answer 7

Eche un vistazo a SciDB.No soy un experto de ella, sino de su sample use cases y a paper describing it, que permite asignar de forma natural sus datos en un 3D (+ 1D para el tiempo/control de versiones) matriz de esta manera:

CREATE ARRAY Pixels [ 
    x INT, 
    y INT, 
    z INT, 
    version INT 
] (
    pixel INT 
); 

Y para poner en práctica su consulta getXYPlaneSlice :

Slice (Pixels, z = 3, version = 1); 

para evitar la duplicación de datos cuando se cambia sólo una parte de los datos, no es necesario llenar toda la gama de la versión 1 desde SciDB apoya matriz dispersa. Luego, cuando necesite cargar los datos más nuevos, puede cargar con version = 0 para obtener la versión anterior y actualizar el resultado con otra carga con version = 1.

Answer 8

Uso STXXL: biblioteca de plantillas estándar para conjuntos de datos extragrandes.

escuché por primera vez sobre él en SO :)

Answer 9

La tendencia en estos días en el trabajo con los datos de volumen muy importante es romper los datos hasta en ladrillos de datos más pequeños de decir 64x64x64. Si desea hacer un renderizado de volumen con iluminación, entonces debe tener una superposición de 1 voxel entre los ladrillos vecinos para que los ladrillos individuales se puedan representar sin necesidad de ladrillos vecinos. Si desea hacer un procesamiento de imágenes más complejo con los ladrillos, puede aumentar la superposición (a expensas del almacenamiento).

La ventaja de este enfoque es que solo necesita cargar los ladrillos necesarios en la memoria. El tiempo de renderizado/procesamiento para un volumen basado en bloques no es significativamente más lento que un volumen base no bricked.

Para una discusión más detallada de esto desde el lado de la representación del volumen, consulte los documentos en el Octreemizer. Here is a link to one on citeseer.

Answer 10

El problema principal es probablemente si desea acceso aleatorio total a sus datos.

El mejor enfoque sería pensar acerca de los algoritmos que desea utilizar, y de que no se puede escribir que la zancada principalmente a través de los datos en un solo una dirección. Ok, eso no siempre es posible.

Si desea codificar una solución de peso medio a sí mismo, debe hacerlo de esta manera:

• uso mmap() para mapear rebanadas de la estructura de datos en la memoria
• encapsulan los datos en una clase, por lo que puede obtener acceso a los datos actualmente no mapeados
• mmap() la región requerida bajo demanda, entonces.

(En realidad, esto es lo que el sistema operativo está haciendo de todos modos, si mmap() todo el archivo a la vez, pero tomando un poco de control, que podría hacer que el bajo demanda algoritmo inteligente, con el tiempo y se ajustan a sus necesidades).

De nuevo, esto no es divertido si saltas con esos vóxeles de imagen. Su algoritmo debe ajustarse al acceso a datos, por cada solución que elija para almacenar sus datos.Total Acceso aleatorio "romperá" todo, si sus datos son más grandes que su memoria física.

Answer 11

Si el hardware y el sistema operativo lo permiten, iría 64 bit, y asignaría el archivo a la memoria (vea CreateFileMapping en Windows y mmap en Linux).

En Windows, puede hacer una vista sobre el archivo asignado que permite copiar y escribir. Estoy seguro de que puede obtener esa funcionalidad en Linux también. De todos modos, si creas una vista de solo lectura sobre el archivo fuente, entonces esos serán tus "datos originales". Luego, crea una vista de copia sobre escritura sobre el archivo fuente; estos serán los "datos actuales".

Al modificar los datos actuales, las páginas subyacentes modificadas se copiarán y asignarán, y las páginas de los datos de origen permanecerán intactas. Si se asegura de que no escribe datos idénticos a sus "datos actuales", también obtendrá un uso óptimo de la memoria, porque sus datos actuales y originales compartirán páginas de memoria. Sin embargo, debe tener en cuenta la alineación de página, ya que la copia por escritura funciona en la página.

Además, revertir de la información actual a la original es un trabajo simple. Todo lo que necesita hacer es recrear la asignación de los "datos actuales".

Al utilizar la asignación de archivos, el tedioso trabajo de administración de la memoria será manejado por el sistema operativo. Podrá usar toda la memoria disponible de una manera muy eficiente. Mucho más eficiente de lo que podrías lograr con asignaciones de montón normales.

Comenzaría investigando CreateFileView() y MapViewOfFile() para su uso en Windows. Para Linux tienes mmap(), pero eso es lo que yo sepa. No he tocado nada * nix desde 2000 ...