Wieviel Speicherplatz für Stack<int> ?

biter

Hallo zusammen, mal wieder, ich brauche eine "Auflistungs-Datenstruktur" so wie .NET Stack<int>, deren Speicherplatz minimal ist, also keine Vorab-Kapazität. Muss nur eintragen und durchlaufen können. Wieviel Speicherplatz braucht Stack<int> für 20 Einträge ? Ist es empfehlenswert, eine Liste selber zu stricken ? Ich arbeite mit .NET WinForms C# VS 2008 und VS 2019. Leider finde ich nur wenig Information über den Speicherverbrauch von Auflistungsklassen, wie List<T>, Dictionary<TKey, TValue> usw.

Mechanics

Kurze Antwort: ein int braucht 4 Byte. Die Liste wird evtl. doppelt so viel Speicher allokiert haben, wie aktuell Einträge enthalten sind - bis zu 40 * 4 = 160 Byte. Und etwas Overhead für Verwaltungsinformationen, z.B. die Länge.

biter

Was ist wenn ich folgendes mache ?

public class ListenKnoten
{
int Eintrag;
ListenKnoten kn;
}

Und daraus eine Liste mache, mit Methoden zum Einfügen und Durchlaufen ? Brauche ich da weniger Speicherplatz ? Nein ! die Zeiger brauchen auch noch vier Byte, Sorry ....

Mechanics

Objekte brauchen bei 64 Bit Systemen mindestens 24 Byte. Und verlinkte Listen sind auch aus anderen Gründen keine gute Idee.

biter

Wird bei Stack<T>, ein dynamisches, Array verwendet ( Ein Array das vergrössert werden kann ) ? Was ist wenn ich einen binären Suchbaum verwenden will ? Den muss ich wohl mit Knoten-Objekten selber bauen. Bei meiner Anwendung möchte ich sehr viele Stacks verwenden, aber das dürfte wohl kein Problem sein. Folgende Datenstruktur:

MeinStruct[] MeineDaten = new MeinStruct[1000000];
struct MeinStruct
{
int[] arr;
Stack<int> st;
}

spricht da etwas dagegen ?

hustbaer

@biter sagte in Wieviel Speicherplatz für Stack<int> ?:

Wird bei Stack<T>, ein dynamisches, Array verwendet ( Ein Array das vergrössert werden kann ) ?

In der Doku steht

The capacity of a Stack<T> is the number of elements the Stack<T> can hold. As elements are added to a Stack<T>, the capacity is automatically increased as required by reallocating the internal array. The capacity can be decreased by calling TrimExcess.

Ist also vermutlich mit einem Array implementiert. Das Interface würde allerdings auch andere Implementierungen zulassen. z.B. mit einer verketteten Liste.

Was ist wenn ich einen binären Suchbaum verwenden will ?

Wenn es wichtig ist dass es ein binärer Suchbaum ist, vielleicht sogar wichtig welche genaue Art von binärem Suchbaun, dann wirst du es selbst implementieren müssen. Bzw. suchen ob es fertige Libraries gibt die genau die gewünschte Art von Suchbaum implementieren. Wenn du nur inetwa die Eingenschaften eines binären Suchbaums brauchst, dann kannst du SortedList oder SortedDictionary verwenden.

Bei meiner Anwendung möchte ich sehr viele Stacks verwenden, aber das dürfte wohl kein Problem sein.

Wenn du wirklich speichersparend arbeiten willst, dann ist das in "managed" Sprachen immer etwas fummelig. Das kompakteste was du in C# bekommen kannst ist ein Array aus structs. List<MyStruct> ist vermutlich auch OK, gibt ja TrimExcess.

Folgende Datenstruktur: (...) spricht da etwas dagegen ?

Schwer zu sagen ohne zu wissen was du damit anstellen willst.

int[] arr;

Aarrr!

biter

Danke Euch !!!