Speichergröße während der Laufzeit ändern - wie?

Luka_one

Hallo zusammen,
nach langer Zeit muss ich mich wieder dem Programmieren widmen.

Da ich keine schöne Lösung gefunden habe, hoffe ich hier Anregungen zu finden. - Vll sogar eine Lösung?

Nach jeder Iteration meines Programmes erweitert sich die Datenmenge um 1 oder ein Element wird gelöscht.

Aussehen soll das Ergebnis nach verschiedenen Iterationsschritten z.B. so:
{1}
{1,2}
....
{1,2,3,4,5,6,7,8,9}
...
{1,3,5,8}
...
{3,8}

Diesmal muss es nicht nur einfach funktionieren, sondern auch Speicher- und Laufzeiteffizient sein.
Ich hatte gelesen, dass sich Listen für diese Aufgabe gut eignen, die soll ich aber nicht verwenden.

Die Speichergröße sollte sich während der Laufzeit anpassen.

Arbeite ich mit 2 arrays, deren Größe ich mit malloc() festlege, so muss ich Daten mit einer for-Schleife kopieren, was bei großen Datenmengen und vielen Iterationsschritten zu einer zu langen Laufzeit führt.

Ich kenne nur einige Grundlagen von C, C++ spezifische Befehle sind mir noch nicht so geläufig.
Vielleicht gibt es noch Möglichkeiten, die ich völlig übersehen habe.
Mit struct / array / Listen /... ???

Wenn also jemand Tips hat, wie man das obige Beispiel realisieren kann, dann nur her damit.

Du darfst also die bereits existierenden Container wie z.B. std::list, std::vector, etc. nicht verwenden?

In dem Fall musst du dir wohl selber etwas überlegen. Dabei sind die Ansätze je nach Fall sehr unterschiedlich.

Brauchst du z.B. Zugriff auf einzelne Elemente? Soll nur hinten angefügt werden oder auch vorne bzw. mitten drin? Musst du die Elemente durchsuchen können?

Eventuell eignet sich für dich eine einfach bzw. doppelt verkettete Liste? Hier kannst du sehr billig Elemente anhängen oder auch löschen (am Ende der Liste).

Nachteil ist aber ein vergleichsweise höherer Speicherverbrauch.

Du wirst vermutlich abwägen müssen, was bei deinem Programm entscheidender ist: Die Laufzeit oder der Speicherverbrauch. Speicher ist heutzutage billig und sowieso schon recht groß dimensioniert. Außerdem glaube ich nicht, dass du den Speicher tatsächlich so stark belasten wirst.

Daher ist eine einfach verkettete Liste vermutlich der beste Ansatz. Im Zweifelsfall musst du eben mehrere Varianten implementieren und im konkreten Fall ausprobieren.

TyRoXx

jkljkljkl schrieb:

Du darfst also die bereits existierenden Container wie z.B. std::list, std::vector, etc. nicht verwenden?

Das hat er nicht gesagt.

Die kurze Antwort: Nimm std::vector .

jkljkljkl schrieb:

Eventuell eignet sich für dich eine einfach bzw. doppelt verkettete Liste? Hier kannst du sehr billig Elemente anhängen oder auch löschen (am Ende der Liste).

Im Gegenteil: Beides ist bei einer Liste sehr teuer.
vector ist viel besser.

Luka_one

Danke für eure schnellen Antworten.

Innerhalb des Programms habe ich bereits andere Datenmengen in Arrays 'gestopft'.

Nehmen wir an, ich würde Spannungen, Ströme und Widerstände mit dem Programm berechnen. Ich habe 25 Millionen ..... Dioden. Die Spannungen kenne ich.
E-Technikerin
Der Wert des Stromes wird in jeder Iteration für die Dioden aktualisiert.

Die verschiedenen Widerstände sind dann meine Problemmenge.
In jeder Iteration wird ein gültiger Wert für den Widerstand in die Datenmenge aufgenommen.
Wird in einer Iteration entschieden, dass keine Diode diesen Widerstand besitzt, muss der Wert gelöscht werden.
Wurde ein neuer Wert berechnet, muss dieser gespeichert werden.
So dass zum Schluss z.B. nur 4 verschiedene Widerstände in der Datenmenge vorhanden sind.
Nun muss ich, wenn ich eine Diode auswähle auch den passenden Widerstandswert finden.

Und da kann es eben schon einen Unterschied machen, ob ich für 25 Millionen Dioden den Widerstand speicher, oder nur 4 Elemente.

Listen soll ich definitiv nicht anwenden.

Bei meiner Suche ist mir std::vector noch nicht untergekommen.
Danke für den Hinweis, dass es die auch gibt. Werde mich damit beschäftigen.

Vielleicht war das Verbot der Listen ja auch nur ein Hinweis auf die Vektoren.

Sollte ich diese benutzen dürfen und fragen dazu haben, weiß ich ja nun, wohin ich mich vertrauensvoll wenden kann.

Danke,
eure Luka

otze

vector ist ein einfaches array, das im Bedarfsfall umkopiert wird sofern mehr speicher gebraucht wird als vorhanden. Also kann das Ding zumindest gut wachsen.

Eine Liste ist schonmal niemals laufzeiteffizient, weil du immer vom einen Listenelement ins nächste Hüpfen muss. Und das mögen unsere CPUs gar nicht, da sie gerne immer nur kleine Schritte nach vorne machen -> array ist immer schneller. Hinzu kommt, dass man nicht gut auf Listenelemente in der Mitte zugreifen kann.

Speichereffizient sind sie auch nicht. In der Implementation auf meinem 64 Bit System belegt die Liste für jedes Element mindestens 16Bytes zusätzlichen Speicher(ein Zeiger aufs nächste und vorherige Element in der Liste). Da du nur Widerstände speicherst, ist das ein Overhead von mindestens Faktor 3. Das lohnt sich bei dir einfach nicht.

Nun schauen wir uns das array/std::vector an: Wenn du am Anfang vorhersagen kannst, wie groß der Vektor maximal werden wird (irgendeine gute Heuristik), dann wirst du kaum jemals Kosten fürs Umkopieren haben. Ansonsten haben Vektoren auch eine gute Heuristik wie sie das wachsen sinnvoll gestalten sollten.

Zum Thema Speichereffizienz: ich denke dass es kein Problem ist, wenn dein Programm den ungenutzten Speicher nicht wieder frei gibt, bevor es beendet ist. Bei der Datenmenge ist es im Gegenteil erst mal sinnvoll, überhaupt fertig zu werden. Laufzeiteffizienz halte ich für sinnvoller. Wenn dein Array so groß ist, dass es nicht mehr in den Speicher passt, ist das viel schlimmer, als wenn das Programm entweder a) nicht fertig wird oder b) hinterher mehr Speicher als unbedingt notwendig braucht. Von daher ist da sein klarer Punkt für den Vektor, da er die bestmöglichste Speichereffizienz hat (0 Byte overhead pro Element) und weil es die Elemente in einem Prozessorfreundlichen Format hält.

Probier das erst mal aus und überlege dir erst sinnvolle Strategien fürs Vektor verkleinern, wenn es wirklich ein Problem darstellt.

Luka_one

Danke,
anscheinend wäre std::vector die richtige Wahl gewesen.

Allerdings ist es dann doch zu 'kompliziert' für die Aufgabe des Programms,
weshalb auf variablen Speicher verzichtet wird.