Array, das schnell werden kann geändert

StackOverflow https://stackoverflow.com/questions/413618

Frage

Ich bin auf der Suche nach einer Art von Array-Daten-Typ, der leicht Elemente haben kann hinzugefügt, ohne Leistungseinbußen.

    .
  • System Array - Redim Preserve Kopien gesamter RAM von alten zu neuen, so langsam wie Menge an vorhandenen Elementen
    • .
  • System.Collections Arraylist - gut genug
    • .
  • System.Collections IList - gut genug
War es hilfreich?

Lösung

Nur wenige Datenstrukturen zusammenfassen:

System.Collections.ArrayList : nicht typisierten Datenstrukturen sind veraltet. Use-Liste (t) statt.

System.Collections.Generic.List (t) : Dies stellt eine veränderbare Array. Diese Datenstruktur verwendet eine interne Anordnung hinter den Kulissen. Hinzufügen von Elementen zu Liste ist O (1), solange die zugrunde liegende Array wurde nicht gefüllt, sonst seine O (n + 1), um das interne Array, um die Größe und kopieren Sie die Elemente über. 

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

Elemente hinzuzufügen, ist nur dann effizient, wenn sie auf die Rückseite der Liste hinzufügen. Einfügen in der Mitte zwingt das Array alle Elemente zu verschieben, nach vorn, die ein O (n) Betrieb ist. Löschen von Elementen ist auch O (n), da die Anordnung rückwärts Elemente verschieben muss.

System.Collections.Generic.LinkedList (t) : Wenn Sie brauchen nicht zufällig oder indizierten Zugriff auf Elemente in der Liste, zum Beispiel planen Sie nur Artikel hinzufügen und iterieren von ersten In dem letzten, dann ist ein LinkedList dein Freund. Inserts und Löschungen sind O (1), lookup O (n).

ist

Andere Tipps

Sie sollten die generische Liste mit <> ( System.Collections.Generic. Liste ) für diese. Er arbeitet in konstant fortgeführten Anschaffungszeit .

Er teilt auch die folgenden Funktionen mit Arrays.

  • Schneller Direktzugriff (Sie jedes Element in der Liste in O zugreifen kann (1))
  • Es ist schnell zu Schleife über
  • Langsam Objekte in der Start- oder Mitte einzusetzen und zu entfernen (da es eine Kopie des gesamten listbelieve zu tun)

Wenn Sie eine schnelle Einfügungen und Löschungen in den Anfang oder das Ende benötigen, verwenden entweder verknüpfte Liste oder Warteschlangen

Kann die LinkedList Struktur für Sie arbeiten? Es ist nicht (in einigen Fällen) so intuitiv wie eine gerade Reihe, ist aber sehr schnell.

  • addlast bis zum Ende
    • anhängen
  • AddBefore / AddAfter in Liste einfügen
  • addFirst zum Anfang
    • anhängen

Es ist nicht so schnell für den Direktzugriff jedoch, wie Sie über die Struktur zu durchlaufen müssen, um Ihre Artikel zugreifen ... aber es hat .ToList () und .ToArray () Methoden, um eine Kopie der Struktur in der Liste zu packen in einer Prise so für den Lesezugriff / Array-Form, könnten Sie das tun. Die Leistungssteigerung der Einsätze kann die Leistung Verringerung der Notwendigkeit für den Direktzugriff aufwiegen oder auch nicht. Es hängt ganz von Ihrer Situation ab.

Es gibt auch diese Referenz, die Ihnen helfen zu entscheiden, welches der richtige Weg zu gehen:

Wenn eine verknüpfte Liste verwenden, um über ein Array / Array-Liste?

Was „gut genug“ für Sie? Was genau tun Sie mit dieser Datenstruktur zu tun?

No Arraystruktur (d.h. O (n) Zugriff) erlaubt das Einfügen in der Mitte ohne O (n) Laufzeit; Einsetzen am Ende ist O (n) im schlechtesten Fall ein O (1) zum Ändern der Größe selbst Arrays wie Array amortisieren.

Vielleicht Hash-Tabellen (fortgeführte Anschaffungs O (1) Zugang und Einfügen überall, aber O (n) im schlechtesten Fall für die Insertion) oder Bäume (O (log (n)) für den Zugang und das Einsetzen überall garantiert) besser geeignet sind.

Wenn die Geschwindigkeit Ihr Problem ist, ich sehe nicht, wie die gewählte Antwort ist besser als ein rohes Array verwenden, obwohl es selbst ändert die Größe, verwendet es den exakt gleichen Mechanismus würden Sie verwenden, um ein Array, um die Größe (und sollen nur nehmen eine Berührung mehr), wenn Sie immer bis zum Ende hinzufügen, in diesem Fall sollte ein bisschen smarter Dinge tun, weil es ein Stück zu einem Zeitpunkt nur ein Element statt zuordnet.

Wenn Sie oft in der Nähe von Anfang / Mitte der Sammlung und nicht Index in die Mitte / Ende sehr oft, mögen Sie wahrscheinlich eine verknüpfte Liste. Das wird die schnellste Einsatzzeit hat und große Iterationszeit haben wird, saugt es nur bei Indizierung (wie auf dem 3. Elemente vom Ende suchen, oder das 72er-Elemente).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top