Datenstruktur zum speichern riesige Menge von Daten?
In meiner Anwendung,ich habe zum laden volumedata aus einer Reihe von Bildern (MRC-Bilder) und halten Sie die pixel-Daten im Speicher.(Bilder sind grayscaled ,also ein byte pro pixel).
Meine Entwicklungsumgebung framework QT ,MinGW für Windows und GCC für Linux.
Im moment verwende ich eine einfache Datenstruktur zum speichern von volumedata als :
unsigned char *volumeData;
und eine riesige Verteilung wie folgt.
volumeData=new unsigned char[imageXsize * imageYsize * numofImages];
Folgenden sind die wichtigsten Methoden zum Zugriff auf Bild-Daten in einer bestimmten Ebene,wie
unsigned char* getXYPlaneSlice(int z_value);
unsigned char* getYZPlaneSlice(int x_value);
unsigned char* getZXPlaneSlice(int y_value);
Mit meiner einfachen Daten-Struktur, es war einfach zu implementieren, die oben genannten Methoden.
Aber könnten wir annehmen müssen, um zu der volume-Größe als 2000x2000x1000 (~3.7 Gb) in die Zukunft.Und aktuelle datastructure nicht in der Lage sein zu handhaben, dass große Datenmengen.
-
Wie eine Zersplitterung zu vermeiden ? Jetzt,auch mit 1000x1000x200 Daten -, Anwendungs-crash geben bad_alloc.
Was ist der beste Weg, um das datastructure für diese ? soll ich so etwas wie verkettete Liste, die jeder chunk ist mit der Größe 100 MB. -
Zudem,Benutzer sollten in der Lage sein, um perfome einige Bild-processing-Filter auf volume-Daten und sollten auch in der Lage sein, einen reset auf original-pixel-Wert.
Das heißt, ich sollte halten Sie zwei Kopien von volume-Daten.
Mit aktuellen implemetation wie seine.unsigned char *volumeDataOriginal;
unsigned char *volumeDataCurrent;
Also mit 2000x2000x1000 Daten-Bereich, sein gehen, nutzen über 8 GB (4 GB für jedes volume).
Aber in der Win32-der Adressraum beträgt 4GB.Wie bewältigen Sie diese ? Ich sollte gehen mit 64bit-Anwendung ?
BEARBEITEN :
Hier ist ein Schnappschuss von meiner Anwendung
Grundsätzlich lade ich die Lautstärke-Daten (aus einer Reihe von Bildern,von MRC-format..etc), und zeigen Sie in verschiedenen Flugzeug-Zuschauer (XY,YX,YZ.Bild zeigt die XY-Ebene-viewer).Ich brauche, um oben 3-Daten-Zugriffs-Methoden zu zeigen, ein Bild in einer bestimmten Ebene.mit Schieberegler-bar kann der Benutzer ändern das Bild zu zeigen, in der ausgewählten Ebene)
Vielen Dank im Voraus.
- Möchten Sie vielleicht zu erkunden, das Fliegengewicht design-pattern und greifen das problem auf einer höheren Ebene. Die Absicht ist es, "Nutzen-sharing zu unterstützen eine große Anzahl von feinkörnigem Objekte effizient."
- Was machst du mit diesem riesigen Speicher chunk? Wie hat sich der user interagieren? Es ist schwer zu sagen, aus Ihrer aktuellen Beschreibung, ob die Bildqualität beeinträchtigt werden kann, ob der gesamte Inhalt hat, sich in Erinnerung zu allen Zeiten etc.
- Man könnte auch überlegen, Address Windowing Extension: msdn.microsoft.com/en-us/library/aa366527(VS.85).aspx
- hier ist ein Schnappschuss von der Anwendung , i.imgur.com/tABMP.png . Ganz einfach es gibt 3 Flugzeug-Viewer für jeden einzelnen Ebene XY,YZ,ZX und Benutzer erkennen, die Zellrahmen mit Kontur-Erkennung von algorithmen.Und anwenden von Bild-processing-Filter, wenn er will.
- meine Anwendung sollte ausgeführt werden, auf Windows,Linux und Mac.So könnte ich etwas brauchen, Multiplattform.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die einfachste Lösung für dein problem wäre die Verwendung von 64-bit-Adressräume - moderne Macs unterstützen, dieses out of the box, unter Windows und Linux müssen Sie die Installation der 64-bit-version des OS. Ich glaube, Qt kann verwendet werden zum erstellen von 64-bit-apps ganz nett. 32-bit-Systeme nicht in der Lage, Unterstützung von einzelnen Zuteilungen an die Größe, die Sie sprechen - auch ein Mac mit 4 GB Adressraum zur Verfügung, um Anwendungen, die nicht in der Lage sein, um eine einzelne 3.7 GB Zuteilung gibt es nicht einen zusammenhängenden Speicherbereich in der Größe erhältlich.
Rückgängig würde ich schauen über die memory-mapped-Dateien und copy-on-write zu kopieren block:
http://en.wikipedia.org/wiki/Copy-on-write
Bedeutet dies, dass Sie eigentlich nicht haben, um kopieren Sie alle der ursprünglichen Daten, das system Kopien der Seiten, wie Sie geschrieben werden. Dies wird deutlich-Hilfe-Leistung, wenn Ihre Bilder sind deutlich größer als realer Speicher-und bist du nicht ändern, jeder Teil des Bildes. Es sieht aus wie boost::map_file mit "private" der Zugriff kann hilfreich sein für diese.
Wenn Sie wirklich, wirklich brauchen, um Unterstützung für 32-bit-Systeme, ist Ihre einzige alternative ist, zu brechen die großen Blöcke nach unten irgendwie, typischerweise in Ebenen oder sub-volumes. Beide sind schrecklich, mit zu arbeiten, wenn es um die Anwendung von 3D-Filter usw. obwohl, so würde ich wirklich vermeiden, wenn man kann.
Wenn man die sub-volume-route, ein trick ist, zum speichern der sub-volumes in memory-mapped-Dateien, und ordnen Sie Sie in Ihren Adressraum nur, wenn Sie Sie benötigen. Wenn nicht zugeordnete aus dem Adressraum Sie sollten erhalten bleiben, um in der unified buffer cache, bis gelöscht, effektiv bedeutet dies können Sie nutzen, mehr Arbeitsspeicher als Adressraum (besonders unter Windows, wo die 32-bit-Anwendungen nur 2 GB Adressraum standardmäßig).
Schließlich auf 32-bit-Windows können Sie auch die Option /3GB in boot.ini. Dies ermöglicht die Zuweisung von 3 GB Adressraum für Anwendungen anstatt der üblichen 2 GB. Aus dem problem, das Sie beschreiben, ich glaube nicht, dass diese Ihnen genügend Adressraum, aber es kann Ihnen helfen, mit einigen kleineren Volumina. Beachten Sie, dass die Option /3GB kann es zu Problemen mit einigen Treibern, wie es reduziert die Menge an Adressraum zur Verfügung, um die kernel.
Ich denke, Sie sollten einen Blick auf im HDF5. Dies ist ein binäres format für die Speicherung von riesigen Datenmengen, die von den Sachen wie Teleskope, Physik-Experimente und gen-Sequenzierung-Maschinen. Die Vorteile der Verwendung von so etwas wie dieses gibt es viele, aber drei ersten Gedanken sind: (1) getestet, (2) unterstützt hyperslab Auswahl, und (3) erhalten Sie die Komprimierung für Sie kostenlos.
Gibt es C/C++, java, python, matlab-Bibliotheken zur Verfügung.
64 bit ist wahrscheinlich der einfachste Weg, dies zu behandeln... lassen Sie die OS die Schuld in die Seiten, wie Sie Sie verwenden. Ansonsten ist es schwer zu sugegst viel, ohne zu wissen, Ihre Zugriffsmuster durch die Daten. Wenn Sie regelmäßig Scannen durch die Bilder, um den Wert an der gleichen pixel-Koordinaten, dann ist es sinnlos, zu sprechen, zu sagen, dass Zeiger auf Bilder speichern und neu laden auf Nachfrage.
Für undo Daten, die Sie halten konnte eine vollständige backup-Kopie, wie Sie vorschlagen, oder Sie könnten versuchen, um eine rückgängig-operation sieht der ath ändern und ist verantwortlich für die Suche nach einer effizienten Implementierung. Zum Beispiel, wenn Sie sich nur umgedreht, die bits, dann ist nicht-destruktiv und Sie brauchen nur einen Funktor in die gleiche bit-flip-operation, um die änderung rückgängig machen. Wenn die Einstellung alle Pixel um den gleichen Ton wurde eine gemeinsame operation (z.B. Befüllung, Reinigung), dann könnte man einen boolean und einen einzelnen pixel zu codieren, dass Bild Stand, und den kompletten Puffer für undo-Schritte.
Können Sie eine memory-mapped-Dateien zum verwalten von großen Datenmengen mit begrenztem Speicher. Allerdings, wenn Ihre Datei-Größen gehen, um die 4 GB dann 64 bit ist zu empfehlen. Das boost-Projekt ist eine gute multi-Plattform-Speicher-mapping-Bibliothek, führt sehr nahe an dem, was Sie suchen.
http://en.wikipedia.org/wiki/Memory-mapped_file
http://www.boost.org/doc/libs/1_44_0/libs/iostreams/doc/classes/mapped_file.html
um Ihnen den Einstieg. Einige Beispiel-code unten --
Dank,
Nathan
Einer option würde ich prüfen, ist Speicher-mapping, statt der Zuordnung alle Bilder, erhalten Sie eine verknüpfte Liste von Bildern, die träge geladen. Als filter funktioniert über die Bild-Liste, laden wie nötig. In der Ladephase Karte eine anonyme (oder einige Feste temporäre Datei) - block der gleichen Größe, und kopieren Sie das Bild dort als backup. Und wie Sie Filter anwenden, die Sie gerade backup zum kopieren. Wie @Tony schon oben gesagt, 64-bit ist Ihre beste option, und für multi-Plattform-memory-mapped-Dateien, betrachten steigern Interprozesskommunikation.
Verwenden STXXL: Standard Template Library for Extra Large Data Sets.
Ich das erste mal davon hörte auf SO 🙂
Könnte man eine zwei-Ebenen-Struktur:
Ein array von Zeigern auf die einzelnen Bilder oder (viel besser) ein paar Bilder.
So könnte man halten, d.h. 20 Bilder in einem memory-block und setzen Sie den Zeiger auf die 20-Bilder-Blöcke in das array.
Dies ist immer noch schnell (im Vergleich zu einer verketteten Liste), wenn dabei der random access.
Können Sie dann implementieren Sie einen einfachen paging-Algorithmus: zuerst werden alle Zeiger im array sind NULL. Beim ersten Zugriff auf eine Bild-block laden Sie die 20 Bilder, die block in den Speicher und schreiben Sie den Zeiger in das array.
Der nächste Zugriff auf diese Bilder wird nicht geladen, nichts.
Wenn Ihr Gedächtnis nachlässt, weil Sie geladen haben geladen und viele Bild-Blöcke, die Sie entfernen können, das Bild-block-Sie haben am wenigsten genutzt wird (sollten Sie fügen Sie ein zweites Feld neben dem Mauszeiger, wo Sie in den Wert ein Zähler, zählen Sie bis jedes mal, wenn Sie ein Bild laden-block). Das Bild-block mit dem niedrigsten Zähler ist die am wenigsten verwendet und kann gelöscht werden (Speicher wiederverwendet wird für den neuen block und die Zeiger auf NULL gesetzt ist).
Den trend in diesen Tagen, in der Arbeit mit sehr großen Datenmengen ist das aufteilen der Daten in kleinere Daten-Steine sagen, von 64x64x64. Wenn Sie wollen, zu tun, volume-rendering mit Beleuchtung, dann sollten Sie haben eine 1 voxel überlappung zwischen benachbarten Ziegel, so dass die einzelnen Steine dargestellt werden können, ohne dass die benachbarten Steine. Wenn Sie wollen mehr tun, komplexe Bildverarbeitung mit den Steinen, dann erhöhen Sie die überlappung (auf Kosten der Aufbewahrung).
Der Vorteil dieses Ansatzes ist, dass Sie brauchen nur zu laden, die Steine, die notwendig sind, in den Speicher. Die rendering - /Verarbeitungszeit für ein backstein-volume ist nicht wesentlich langsamer als ein nicht-gemauerten Basis-volume.
Für eine mehr beteiligt Diskussion dieser von der volume-rendering-Seite, check-out-Papiere auf den Octreemizer. Hier ist ein link zu einem auf citeseer.
Das Hauptproblem ist wahrscheinlich, wenn Sie wollen total random access auf Ihre Daten.
Der beste Ansatz wäre, zu denken, über die algorithmen, die Sie verwenden möchten, und Sie können nicht geschrieben werden, dass vor allem die Schrittlänge durch die Daten nur eine Richtung. Ok, das ist nicht immer möglich.
Wenn Sie wollen, um code, der eine Mitte-Gewicht-Lösung selbst, Sie sollten es so machen:
mmap()
zuordnen Scheiben Ihrer Datenstruktur in den Speichermmap()
der gewünschten region auf die Nachfrage, dann.(Eigentlich das ist, was das OS tut, jedenfalls, wenn Sie
mmap()
die ganze Datei auf einmal, aber, indem Sie ein wenig Kontrolle, Sie könnte die on-demand - Algorithmus schlauer, im Laufe der Zeit, und passen Sie den Anforderungen).Erneut, das ist kein Spaß, wenn Sie springen um auf diese Bild-voxels. Ihr Algorithmus muss die Daten passen-Zugang -- für jede Lösung, die Sie wählen, um Ihre Daten zu speichern. Insgesamt Random-Access - "Pause" alles, wenn Ihre Daten größer ist dann Ihre physischen Speicher.
Wenn die hardware und das Betriebssystem es zulässt, würde ich gehen, 64 bit, und anzeigen der Datei in den Speicher (siehe CreateFileMapping auf Windows-und mmap unter Linux).
Unter Windows, können Sie einen Blick auf die zugeordnete Datei, die erlaubt copy-on-write. Ich bin sicher, dass Sie bekommen können, dass die Funktionalität unter Linux, als auch. Jedenfalls, wenn Sie, erstellen Sie eine nur-lese-Ansicht über die Quelle der Datei, dann wird Ihre "original-Daten". Dann erstellen Sie ein copy-on-write-Sicht auf den source-Datei - dies wird die "aktuellen Daten".
Beim ändern von aktuellen Daten, die die modifizierte zugrunde liegenden Seiten werden kopiert und reserviert für Sie, und die Seiten für die Quell-Daten bleiben erhalten. Wenn Sie sicherstellen, dass Sie nicht schreiben, identische Daten zu Ihrem "aktuellen Daten", erhalten Sie auch eine optimale Nutzung des Speichers, weil Ihre aktuellen Daten und den ursprünglichen Daten teilen sich Speicher-Seiten. Sie tun müssen, nehmen Sie die Seitenausrichtung in Betracht, wenn, weil copy-on-write arbeitet auf basis Seite.
Auch, wieder vom aktuellen zu den ursprünglichen Daten ist ein einfacher job. Alles, was Sie tun müssen, ist, erstellen Sie die Zuordnung für die "aktuellen Daten".
Durch die Verwendung von mapping-Datei, die mühsame Arbeit der Verwaltung des Speichers erfolgt über den OS. Es wird in der Lage sein, alle verfügbaren Speicher auf sehr effiziente Weise. Effizienter als Sie jemals erreichen, mit normalen heap-Zuweisungen.
Ich würde beginnen Sie mit der Erforschung CreateFileView() und MapViewOfFile() für den Einsatz auf Windows. Für Linux haben Sie mmap(), aber soweit reicht mein wissen. Ich habe nicht berührt, nichts *nix-seit 2000...
Haben Sie einen Blick auf SciDB. Ich bin kein Experte, aber aus seiner Beispiel-use-cases und ein Papier beschreibt es, ermöglicht es Ihnen, auf Natürliche Weise ordnen Sie Ihre Daten in ein 3D (+1D Zeit - /Versionsverwaltung) - array wie dieses:
Und Umsetzung Ihrer Abfrage
getXYPlaneSlice
:Doppelarbeit zu vermeiden Daten, wenn nur ein Teil der Daten geändert wird, werden Sie nicht brauchen, um füllen Sie das gesamte array für die version 1 seit SciDB unterstützt sparse-array. Dann wenn Sie benötigen, laden Sie die neuesten Daten, die Sie laden konnte mit
version = 0
um die alte version, und aktualisieren Sie das Ergebnis mit einem anderen laden mitversion = 1
.