Structure de données pour stocker grande quantité de données?

dans mon application, je dois charger des données à partir d'un jeu d'images (images MRC) et garder les données des pixels en mémoire.(les images sont en gris, donc un octet par pixel).

mon environnement de développement est Qt framework, MinGW pour Windows et GCC pour Linux.

pour le moment, j'utilise une structure de données simple pour stocker les données voluméditées comme:

unsigned char *volumeData;

et faire une énorme allocation comme suit.

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

ce qui Suit sont des méthodes pour accéder à image-données dans un plan donné,tel que

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

avec ma structure de données simple, il était facile de mettre en œuvre les méthodes ci-dessus.

mais nous pourrions avoir besoin d'adopter à la taille du volume comme 2000x2000x1000 (~3,7 Gb) à l'avenir.Et l'infrastructure de données actuelle ne sera pas en mesure de gérer ces énormes données.

  1. Comment éviter la fragmentation ? Maintenant, même avec les données 1000x1000x200, le plantage d'application donnant bad_alloc. Quelle est la meilleure façon de changer la structure de données pour cela ? dois-je utiliser quelque chose comme la liste de liens qui chaque morceau est de taille 100mb.

  2. en outre, l'utilisateur devrait être en mesure de perfectionner certains filtres de traitement d'image sur les données de volume et devrait également être en mesure de réinitialiser à la valeur originale du pixel. Cela signifie que je devrais garder deux copies de données de volume. Avec l'actuelle mise en œuvre de ses semblables.

    non signé * volumeDataOriginal;

    non signé char * volumedataacurrent;

donc avec 2000x2000x1000 sa gamme de données va utiliser environ 8Go (4Go pour chaque volume). Mais dans Win32 , L'espace d'adresse est de 4 Go.Comment faire pour remédier à cette situation ? Je devrais choisir l'application 64bit ?

modifier : Voici un aperçu de ma demande enter image description here

en gros, je charge les données de volume (à partir d'un jeu d'images,à partir du format MRC)..etc) et les afficher dans différents Plan-viewers (XY,YX, YZ.L'Image montre un plan XY-viewer).J'ai besoin de garder au-dessus de 3 méthodes d'accès aux données pour montrer une image dans un particulier avion.à l'aide de barre de curseur utilisateur peut changer l'image à afficher dans le plan sélectionné)

Merci d'avance.

12
demandé sur Guru 2010-11-09 10:03:58

11 réponses

la solution la plus simple à votre problème serait d'utiliser des espaces d'adressage 64 bits-les Mac modernes prennent en charge Cette solution, sur Windows et Linux, vous aurez besoin d'installer la version 64 bits du système D'exploitation. Je pense que Qt peut être utilisé pour construire des applications 64 bits assez bien. Les systèmes 32 bits ne seront pas en mesure de prendre en charge des attributions simples de la taille dont vous parlez - même un Mac avec 4 Go d'espace d'adresse Disponible pour les applications ne sera pas en mesure de faire une seule attribution de 3,7 Go car il n'y aura pas de espace contigu de cette taille disponible.

pour annuler je regarderais en utilisant des fichiers de mappage de mémoire et de copie-sur-écriture pour copier le bloc:

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

cela signifie que vous n'avez pas réellement à copier toutes les données originales, le système fera des copies des pages telles qu'elles sont écrites. Cela aidera grandement la performance si vos images sont beaucoup plus grand que la mémoire réelle et vous ne changez pas chaque partie de la image. Il ressemble à boost:: map_file avec accès "privé" pourrait être utile pour cela.

si vous avez vraiment, vraiment besoin de prendre en charge des systèmes 32 bits, votre seule alternative est de briser ces gros blocs en quelque sorte, typiquement en avions ou sous-volumes. Les deux sont horribles à travailler avec quand il s'agit d'appliquer des filtres 3D, etc. bien que, donc j'éviterais vraiment cela si vous le pouvez.

si vous optez pour la route des sous-volumes, un truc est de sauvegarder tous les sous-volumes dans fichiers mappés en mémoire, et la carte dans votre espace d'adressage uniquement lorsque vous en avez besoin. Lorsqu'ils ne sont pas captés à partir de l'espace d'adresse, ils doivent rester dans le cache tampon unifié jusqu'à ce qu'ils soient purgés, ce qui signifie que vous pouvez utiliser plus de RAM que vous n'avez d'espace d'adresse (en particulier sur Windows où les applications 32 bits n'obtiennent que 2 Go d'espace d'adresse par défaut).

enfin, sur les fenêtres 32 bits, vous pouvez aussi regarder le commutateur /3 Go dans le boot.ini. Cela vous permet d'allouer 3 GO d'adresse espace pour les applications plutôt que la normale 2 Go. Du problème que vous décrivez Je ne pense pas que cela vous donnera assez d'espace d'adresse, cependant il peut vous aider avec quelques plus petits volumes. Notez que le commutateur /3GB peut causer des problèmes avec certains pilotes car il réduit l'espace d'adresse Disponible pour le noyau.

5
répondu Bids 2010-11-18 22:55:28

je pense que vous devriez jeter un coup d'oeil à hdf5. Il s'agit d'un format binaire pour stocker d'énormes quantités de données recueillies à partir de choses comme les télescopes, les expériences en physique, et les machines de séquençage des gènes. Les avantages d'utiliser quelque chose comme ceci sont nombreux, mais trois pensées immédiates sont: (1) testé, (2) prend en charge la sélection hyperslab, et (3) vous obtenez la compression gratuite.

il existe des bibliothèques C/C++, java, python, matlab.

14
répondu jimmyb 2010-11-09 07:27:01

64 bits est probablement la meilleure façon de gérer cela... laissez la faute OS dans les pages que vous utilisez. Autrement, il est difficile de trouver beaucoup de choses sans connaître vos modèles d'accès à travers les données. Si vous scannez régulièrement les images pour trouver la valeur aux mêmes coordonnées pixel, alors il est inutile de dire avoir des pointeurs vers des images qui sauvegardent et rechargent à la demande.

Pour annuler les données, vous pouvez garder une copie de sauvegarde complète comme vous le suggérez, ou vous pouvez essayer avoir une opération undo qui regarde le changement fait et est responsable de trouver une mise en œuvre efficace. Par exemple, si vous avez simplement retourné les bits, alors c'est non destructif et vous avez juste besoin d'un foncteur pour la même opération de bit-flip pour annuler le changement. Si le réglage de tous les pixels à la même tonalité était une opération courante (par exemple remplir, effacer), alors vous pourriez avoir un booléen et un pixel simple pour encoder cet état d'image, et utiliser le tampon complet pour undo.

5
répondu Tony Delroy 2010-11-09 07:12:45

Vous pouvez utiliser des fichiers cartographiés en mémoire pour gérer de grands ensembles de données avec une mémoire limitée. Cependant, si vos tailles de fichier vont être de 4 Go, alors aller à 64 bits est recommandé. Le projet boost a une bonne bibliothèque de cartographie mémoire multi-plateforme qui fonctionne très proche de ce que vous recherchez.

http://en.wikipedia.org/wiki/Memory-mapped_file http://www.boost.org/doc/libs/1_44_0/libs/iostreams/doc/classes/mapped_file.html pour obtenir vous avez commencé. Quelques exemples de code ci-dessous --

#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();

Merci, Nathan

4
répondu Naveen 2010-11-15 21:37:17

une option que je considérerais est la cartographie de mémoire, au lieu de cartographier toutes les images, maintenir une liste liée d'images qui sont chargés paresseusement. Lorsque votre filtre fonctionne à travers la liste des images, chargez-le au besoin. Dans la phase de chargement, cartographiez un bloc anonyme (ou d'un fichier temporaire fixe) de la même taille et copiez l'image là comme votre sauvegarde. Et comme vous appliquez des filtres, vous juste sauvegarder sur cette copie. Comme @Tony l'a dit ci-dessus, 64-bit est votre meilleure option, et pour les fichiers multi-plate-forme de mappage de mémoire, regardez à stimuler interprocessus.

3
répondu Nim 2010-11-09 09:18:53

Utiliser STXXL: Bibliothèque de modèles Standard pour plus de Grands Ensembles de Données.

j'ai d'abord entendu parler sur :)

3
répondu log0 2017-05-23 12:01:09

vous pourriez utiliser une structure à deux niveaux: Un tableau de pointeurs vers les images ou (beaucoup mieux) un tas d'images. Vous pouvez donc garder 20 images dans un bloc de mémoire et mettre les pointeurs vers les 20-images-blocs dans le tableau. Ceci est encore rapide (comparé à une liste liée) quand on fait un accès aléatoire.

vous pouvez alors implémenter un algorithme de paging simple: au début tous les pointeurs dans le tableau sont nuls. Lorsque vous accédez pour la première fois à un bloc d'image, vous chargez les 20 images de ce bloc en mémoire et d'écriture le pointeur dans le tableau. Le prochain accès à ces images ne charge rien.

si votre mémoire devient faible parce que vous avez chargé et chargé de nombreux blocs d'image, vous pouvez supprimer le bloc d'image que vous avez le moins utilisé (vous devez ajouter un second champ à côté du pointeur où vous mettez la valeur d'un compteur que vous comptez à chaque fois que vous chargez un bloc d'image). Le bloc d'image avec le compteur le plus bas est le moins utilisé et peut être supprimé (la mémoire est réutilisée pour le nouveau bloc et le pointeur est NULL).

1
répondu mmmmmmmm 2010-11-16 18:25:16

la tendance de nos jours dans le travail avec des données de très grand volume est de briser les données en briques de données plus petites de dire 64x64x64. Si vous voulez faire le rendu de volume avec l'éclairage, alors vous devriez avoir un chevauchement de 1 voxel entre les briques voisines de sorte que les briques individuelles peuvent être rendues sans avoir besoin de briques voisines. Si vous voulez faire un traitement d'image plus complexe avec les briques, alors vous pouvez augmenter le chevauchement (au détriment du stockage).

L'avantage de cette approche est qu'il vous suffit de charger les briques qui sont nécessaires dans la mémoire. Le temps de rendu/traitement pour un volume à base de briques n'est pas significativement plus lent qu'un volume de base non-briqué.

pour une discussion plus impliquée de ce côté du rendu de volume, consultez les documents sur L'Octreemizer. Voici un lien vers un sur citeseer.

1
répondu Eric 2010-11-17 07:59:17

Le principal problème est probablement, si vous voulez total d'accès aléatoire à vos données.

La meilleure approche serait de réfléchir à l' algorithmes vous souhaitez utiliser, et ils ne peuvent pas être écrits que la principalement la foulée par les données en seulement direction. Ok, ce n'est pas toujours possible.

si vous voulez coder une solution de poids moyen vous-même, vous devriez le faire comme ceci:

  • utiliser mmap() pour la carte tranches de votre structure de données en mémoire
  • encapsuler les données dans une classe, vous pouvez intercepter l'accès de l'heure non mappé données
  • mmap() la région requise sur demande, alors.

(en fait, c'est ce que L'OS fait de toute façon, si vous mmap() le fichier entier à la fois, mais en prenant un peu de contrôle, vous pouvez faire de l' demande algorithme plus intelligent, au fil du temps, et vous convient exigence.)

encore une fois, ce n'est pas amusant si vous sautez sur ces voxels d'image. Votre algorithme doit correspondre à l'accès aux données -- pour chaque solution que vous choisissez de stocker vos données. Total Accès Aléatoire va "casser" tout, si vos données sont plus grandes que votre mémoire physique.

1
répondu towi 2010-11-18 12:59:03

si le matériel et le système D'exploitation le permettent, j'irai 64 bits, et mapperai le fichier en mémoire (voir CreateFileMapping sur Windows et mmap sur Linux).

Sur Windows, vous pouvez faire une vue sur le fichier mappé qui permet de copie sur écriture. Je suis sûr que vous pouvez obtenir cette fonctionnalité sur Linux. Quoi qu'il en soit, si vous créez une vue en lecture seule sur le fichier source, alors ce sera vos "données originales". Ensuite, vous créez une copie sur écriture, vue sur le fichier source qui sera le "courant données."

lorsque vous modifiez des données courantes, les pages sous-jacentes modifiées seront copiées et attribuées pour vous, et les pages pour les données source resteront intactes. Si vous vous assurez que vous n'écrivez pas des données identiques à vos "données actuelles", vous obtiendrez également une utilisation optimale de la mémoire, parce que vos données actuelles et les données originales partageront des pages de mémoire. Vous devez prendre l'alignement de page en considération cependant, parce que la copie-sur-écrit fonctionne sur la base de la page.

également, revenir des données actuelles aux données originales est un travail simple. Tout ce que vous devez faire est de recréer de la cartographie pour les "données actuelles".

en utilisant la cartographie de fichiers, le travail fastidieux de gestion de la mémoire sera géré par L'OS. Il sera en mesure d'utiliser toute la mémoire disponible dans une manière très efficace. Bien plus efficace que ce que tu pourrais jamais accomplir avec des allocations normales.

je commencerais par rechercher CreateFileView() et MapViewOfFile() pour les utiliser sur Windows. Pour Linux vous ont mmap(), mais c'est aussi loin que mes connaissances en va. Je n'ai touché à rien depuis 2000...

1
répondu Jörgen Sigvardsson 2010-11-18 19:18:36

regardez SciDB. Je ne suis pas un expert, mais de son exemple de cas d'utilisation et un document décrivant, il vous permet de cartographier naturellement vos données dans un tableau 3D (+1D pour time/versioning) comme ceci:

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

Et pour mettre en œuvre votre requête getXYPlaneSlice:

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

pour éviter la duplication des données quand seulement une partie des données est changée, vous n'avez pas besoin de remplir tout le tableau pour la version 1 puisque SciDB supporte sparse tableau. Puis, quand vous avez besoin de charger les données les plus récentes, vous pouvez charger avec version = 0 pour obtenir l'ancienne version, et mettre à jour le résultat avec un autre chargement avec version = 1.

0
répondu eddie_c 2010-11-16 19:16:07