Ich habe ein Problem, an dem ich arbeite, wo ich eine Art zweidimensionales Array verwenden muss. Das Array hat eine feste Breite (vier Spalten), aber ich muss im laufenden Betrieb zusätzliche Zeilen erstellen.
Um dies zu tun, habe ich Vektoren von Vektoren verwendet, und ich habe einige verschachtelte Schleifen verwendet, die dies enthalten:
%Vor%um die Zeilen und deren Inhalt hinzuzufügen. Das Problem ist, dass mir die Anzahl der Elemente, die ich erstellen wollte, nicht mehr ausreicht. Daher habe ich die Anzahl der verwendeten Elemente reduziert. Aber dann fing ich an, über Deque zu lesen, und dachte, es würde mir erlauben, mehr Speicher zu verwenden, weil es nicht zusammenhängend sein muss. Ich habe alle Erwähnungen von "Vektor" zu "Deque", in dieser Schleife, sowie alle Deklarationen geändert. Aber dann sah es so aus, als wäre mir wieder der Speicher ausgegangen, diesmal sogar mit der reduzierten Anzahl von Zeilen.
Ich habe mir angeschaut, wie viel Speicher mein Code benutzt, und wenn ich deque benutze, steigt der Speicher stetig auf über 2GB, und das Programm schließt bald darauf, selbst wenn ich die kleinere Anzahl von Zeilen verwende. Ich bin mir nicht sicher, wo genau in dieser Schleife es ist, wenn es nicht genügend Speicher hat.
Wenn ich Vektoren verwende, liegt die Speicherauslastung (für die gleiche Anzahl von Zeilen) immer noch unter 1 GB, selbst wenn die Schleife beendet wird. Es geht dann zu einer ähnlichen Schleife, wo mehr Zeilen hinzugefügt werden, immer noch nur etwa 1,4 GB.
Also meine Frage ist. Ist das normal für deque, mehr als das Doppelte des Gedächtnisses von Vektor zu verwenden, oder mache ich eine falsche Annahme im Denken ich kann das Wort "vector" einfach durch "deque" in den Deklarationen / Initialisierungen und dem obigen Code ersetzen?
Vielen Dank im Voraus.
Ich benutze: MS Visual C ++ 2010 (32-Bit) Windows 7 (64-Bit)
Alles hängt von der internen Implementierung von deque ab (ich werde nicht über vector sprechen, da es relativ einfach ist).
Fakt ist, deque hat völlig andere Garantien als vector (der wichtigste ist, dass er O (1) -Einfügung an beiden Enden unterstützt, während vector nur O (1) -Einfügung hinten unterstützt). Dies bedeutet wiederum, dass die von deque verwalteten internen Strukturen komplexer sein müssen als vector .
Um dies zu ermöglichen, teilt eine typische deque -Implementierung ihren Speicher in mehrere nicht zusammenhängende Blöcke auf. Aber jeder einzelne Speicherblock hat einen festen Overhead, um die Speicherverwaltung zu ermöglichen (z. B. unabhängig von der Größe des Blocks, das System benötigt möglicherweise weitere 16 oder 32 Bytes oder was auch immer, nur für die Buchhaltung). Da im Gegensatz zu einem vector ein deque viele kleine, unabhängige Blöcke erfordert, stapelt sich der Overhead, was den Unterschied erklärt, den Sie sehen. Beachten Sie auch, dass diese einzelnen Speicherblöcke verwaltet werden müssen (möglicherweise in separaten Strukturen?), Was wahrscheinlich auch (oder eine Menge) zusätzlichen Aufwand bedeutet.
Wie Sie Ihr Problem lösen können, können Sie versuchen, was @BasileStarynkevitch in den Kommentaren vorgeschlagen, dies wird zwar Ihre Speicherauslastung reduzieren, aber es wird Sie nur so weit bringen, weil Sie irgendwann keinen Speicher mehr haben . Und was, wenn Sie versuchen, Ihr Programm auf einem Rechner mit nur 256 MB RAM auszuführen? Jede andere Lösung, die darauf abzielt, den Speicherbedarf zu reduzieren und dennoch versucht, alle Ihre Daten im Speicher zu halten, leidet unter den gleichen Problemen.
Eine richtige Lösung bei der Verarbeitung großer Datensätze wie Ihrer wäre die Anpassung Ihrer Algorithmen und Datenstrukturen, um kleine Partitionen gleichzeitig mit dem gesamten Datenbestand verarbeiten und diese Partitionen je nach Bedarf laden / speichern zu können Raum für die anderen Partitionen. Leider bedeutet das wahrscheinlich, dass man auf die Festplatte zugreifen kann, aber es bedeutet auch einen großen Leistungsabfall, aber hey, man kann den Kuchen nicht essen und auch nicht essen.
Die wirkliche Antwort hier hat wenig mit der Kerndatenstruktur zu tun. Die Antwort ist, dass MSVCs Implementierung von std :: deque besonders schrecklich ist und zu einem Array von Zeigern zu einzelnen Elementen degeneriert, anstatt zu dem Array von Arrays, das es sein sollte. Offen gesagt, ist nur die doppelte Speicherbelegung von Vektor überraschend. Wenn Sie eine bessere Implementierung von Deque hätten, würden Sie bessere Ergebnisse erzielen.
Es gibt zwei gebräuchliche Methoden, um eine Deque effizient zu implementieren: entweder mit einem modifizierten dynamischen Array oder mit einem doppelt verknüpfte Liste .
Das modifizierte dynamische Array ist im Grunde genommen ein dynamisches Array, das von beiden Seiten her wachsen kann und manchmal array deques genannt wird. Diese Array-Deques haben alle Eigenschaften eines dynamischen Arrays, wie z. B. zeitkontinuierlicher Direktzugriff , gute Referenzlokalität und ineffiziente Einfügung / Entfernung in der Mitte mit der Hinzufügung einer amortisierten Konstantenzeiteinfügung / Entfernung an beiden Enden statt nur an einem Ende.
Es gibt mehrere Implementierungen des modifizierten dynamischen Arrays:
Zuweisung von Deque-Inhalten von der Mitte des zugrunde liegenden Arrays, und Ändern der Größe des zugrunde liegenden Arrays, wenn eines der beiden Enden erreicht ist. Dies Ansatz erfordert möglicherweise häufigere Anpassungen und mehr Speicherplatz verschwenden , besonders wenn Elemente nur an einem Ende eingefügt werden .
Speichern von Deque-Inhalten in einem Ringpuffer und nur dann, wenn die Größe geändert wird Der Puffer wird voll. Dies verringert die Häufigkeit von Resizierungen.
Inhalte in mehreren kleineren Arrays speichern und zusätzliche zuweisen Arrays am Anfang oder Ende nach Bedarf. Die Indizierung erfolgt durch Halten eines dynamischen Arrays, das Zeiger zu jedem der kleineren enthält Arrays.
Verschiedene Bibliotheken können Deques auf unterschiedliche Weise implementieren, aber im Allgemeinen als modifiziertes dynamisches Array . Höchstwahrscheinlich verwendet Ihre Standardbibliothek den Ansatz # 1, um std::deque zu implementieren, und , da Sie Elemente nur an einem Ende anhängen, wodurch Sie letztendlich viel Speicherplatz verschwenden . Aus diesem Grund macht es eine Illusion, dass std::deque mehr Platz belegt als üblich std::vector .
Wenn std::deque außerdem als doppelt verkettete Liste implementiert würde, würde dies ebenfalls zu Platzverschwendung führen, da jedes Element zusätzlich zu Ihren benutzerdefinierten Daten zwei Zeiger aufnehmen müsste.
Die Implementierung mit Ansatz # 3 (auch modifizierter dynamischer Array-Ansatz) würde wiederum zu Platzverschwendung führen, um zusätzliche Metadaten wie Zeiger auf all diese kleinen Arrays unterzubringen.
In jedem Fall ist std::deque in Bezug auf den Speicher weniger effizient als das einfache alte std::vector . Ohne zu wissen, was Sie erreichen wollen, kann ich nicht mit Sicherheit vorschlagen, welche Datenstruktur Sie benötigen. Wie auch immer, es scheint so, als wüsstest du nicht einmal, wofür Deques sind, also was du wirklich in deiner Situation willst, ist std::vector . Deques, im Allgemeinen, haben unterschiedliche Anwendung.
Deque kann zusätzlichen Speicher-Overhead über den Vektor haben, da es aus ein paar Blöcken statt aus benachbarten besteht.
Aus de.cppreference.com/w/cpp/container/deque :
Im Gegensatz zu
std::vectorwerden die Elemente einesdequenicht zusammenhängend gespeichert: typische Implementierungen verwenden eine Folge von individuell zugewiesenen Arrays fester Größe.
Das primäre Problem ist, dass nicht genügend Arbeitsspeicher zur Verfügung steht.
Also, brauchen Sie alle Daten im Speicher auf einmal?
Sie werden das vielleicht niemals schaffen.
Sie sollten in Betracht ziehen, die Daten in "Chunks" oder kleinere Submatrizen zu verarbeiten. Verwenden Sie beispielsweise das Standardrechteckgitter:
Wenn Sie nach einem Partikel oder einer Menge von Daten suchen, können Sie dies tun, ohne den gesamten Datensatz in den Speicher einzulesen.
Wenn Ihre Anwendung die Rohdaten von einer Eingabequelle (außer einer Datei) empfängt, möchten Sie die Daten für die spätere Verarbeitung speichern.
Dies erfordert mehr als einen Puffer und ist effizienter, wenn mindestens zwei Ausführungsthreads verwendet werden.
Der Lese-Thread liest Daten in einen Puffer, bis der Puffer voll ist. Wenn der Puffer voll ist, liest er Daten in eine andere leere.
Der Schreib-Thread wartet zunächst, bis entweder der erste Lese-Puffer voll ist oder die Lese-Operation beendet ist. Als nächstes entnimmt der Schreib-Thread Daten aus dem Lese-Puffer und schreibt in eine Datei. Der Schreib-Thread beginnt dann mit dem Schreiben aus dem nächsten Lese-Puffer.
Diese Technik wird Double Buffering oder Multiple Buffering genannt.
Wenn in der Matrix viele Null- oder nicht verwendete Daten vorhanden sind, sollten Sie Sparse-Matrizen verwenden. Im Wesentlichen ist dies eine Liste von Strukturen, die die Koordinaten der Daten und den Wert enthalten. Dies funktioniert auch, wenn die meisten Daten einen anderen Wert als Null haben. Dies spart viel Speicherplatz; kostet aber ein bisschen mehr Ausführungszeit.
Sie können auch Ihre Algorithmen ändern, um Datenkomprimierung zu verwenden. Die Idee hier ist, den Datenort, den Wert und die Anzahl oder zusammenhängende gleiche Werte zu speichern (a.k.a. runs). Anstatt also 100 aufeinanderfolgende Datenpunkte desselben Werts zu speichern, würden Sie die Startposition (des Laufs), den Wert und 100 als die Menge speichern. Dies spart viel Platz, erfordert jedoch mehr Verarbeitungszeit beim Zugriff auf die Daten.
Es gibt Bibliotheken, die eine Datei als Speicher behandeln können. Im Wesentlichen lesen sie eine "Seite" der Datei in den Speicher ein. Wenn die Anfragen die "Seite" verlassen, lesen sie auf einer anderen Seite. All dies wird "hinter den Kulissen" durchgeführt. Alles, was Sie tun müssen, ist die Datei wie Speicher zu behandeln.
Arrays und Deques sind nicht Ihr Hauptproblem, die Datenmenge ist. Ihr Hauptproblem kann gelöst werden, indem Sie kleine Datenstücke gleichzeitig verarbeiten, den Datenspeicher komprimieren oder die Daten in der Datei als Speicher behandeln. Wenn Sie Streaming-Daten verarbeiten möchten, tun Sie dies nicht. Im Idealfall sollten Streaming-Daten in einer Datei gespeichert und später verarbeitet werden. Ein historischer Zweck einer Datei besteht darin, Daten zu enthalten, die nicht in den Speicher passen.
Tags und Links c++ visual-c++ vector ram deque