Frage

Ich brauche eine Datenstruktur, die eine Liste von Elementen des gleichen Typs hält. Benötigte Funktionen sind

  • Hinzufügen
  • GetEnumerator
  • (möglicherweise) Klar

Ein indiziertes Zugang, Sortieren, Suchen, Entfernen von Elementen nicht erforderlich . Was ist die beste Sammlung Klasse für sie? Leistung, Speichernutzung, Verhalten des Garbage Collector: Folgende Aspekte sollten in Betracht gezogen werden.

Meine aktuellen Kandidaten sind List<T> und LinkedList<T>

War es hilfreich?

Lösung

Kurze Antwort
Standard zur Verwendung von List<T> in fast alle Fällen.

Etwas länger beantworten
LinkedList<T> ist nur noch besser sein, wenn Sie eine Menge tun, das Hinzufügen und Werte im Vergleich zu entfernen, um diese Werte Aufzählen über und die Größe der Liste ist groß. Dies sollte nur ein Faktor bei der Wahl sein, wenn nachfolgende Sie mit List<T> finden Profilierung ist ein Problem.

Lange Antwort

Annahme, haben Sie die Verwendung eines oder das andere als ein Problem für die Leistung identifiziert.

Es Sie tun eine Menge von zufälligem Zugriff dann List<T> fast immer erheblich schneller sein, egal was. Wenn Sie eine Menge aufzählen und selten einsetzen (oder fast immer in der Nähe einfügen / am Ende) wird die List<T> fast immer schneller. Wenn Sie ständig das Einfügen / Entfernen in zufälligen Orten aber während Iteration über die Liste so sind bereits an oder nahe dem entsprechenden Knoten und mindestens mehrere tausend Elemente haben möchten Sie vielleicht LinkedList<T> versuchen

Ausarbeiten, welche Werte / Nutzung zu einer besseren Leistung übersetzen sind sehr stark abhängig von Ihrem Einsatz. Microbenchmarks kann sehr irreführend sein hier, da sie unter den Teppich Aspekte der verknüpften Listen Verhalten wie die Knoten in Pinsel in etwa anstatt schön benachbart im Speicher verteilt werden, wenn sie in Ihren Tests auf einmal bekommen zugeordnet passieren. Ebenso vorge Erstellen den List<T> mit der richtigen Größe kann einen großen Unterschied machen.

In Bezug auf Informatik Stil Argumentation und O-Notation (die wirklich braucht große Ns in diesem Fall sinnvoll sein)

  • Betrieb
    • Kosten List<T>
    • Kosten LinkedList<T>
  • Einsatz am Ende
    • O (1) (fortgeführte Anschaffungskosten, Zuteilung auf doppelte Größe je nach Bedarf)
    • O (1) Zuordnung jedes Mal
  • Einsatz beim Start
    • O (N) (obwohl getan, so schnell Speicher bewegen so etwas komplexes Laufzeitverhalten)
    • O (1)
  • Einsatz in Position x (und entfernen Sie auch)
    • O (N-x) (siehe Kommentar zum Einsatz am Ende)
    • O (1)
  • vorwärts Aufzählung
    • O (N) (obwohl Cache-Misses minimiert)
    • O (N) (obwohl stark abhängig von Cache-Lokalität)
  • Reverse Aufzählung
    • O (N)
    • O (N) (die LinkedList<T> Umsetzung doppelt gebunden ist)
  • random access
    • O (1)
    • O (N)

Der Speicherverbrauch ist komplex, da Liste höchstens Count haben kann - 1 überschüssige Zellen an jedem beliebigen Punkt aber LinkedList<T> eine LinkedListNode<T> für jede Zelle verbrauchen, die weiteren 3 Referenzen ist (4/8 Bytes ein pop) zuzüglich den üblichen Objekt-Overhead. Im normalen Sprachgebrauch ist die Liste wahrscheinlich diese zu gewinnen, aber wieder nur etwas, das Sie zu kümmern, wenn Sie den Speicherverbrauch zu finden, ist tatsächlich ein Problem.

Andere Tipps

Wenn Sie nicht mit einer massiven Struktur handeln oder Sie planen, über diese Sache eine Billion mal auf Iterieren, spielt es keine Rolle. Wählen Sie einfach ein und Programmieren beginnen . Wenn Ihre App später zu einem Schleichen verlangsamen, herauszufinden, warum dann und ändern, falls erforderlich.

(Im Ernst, es tut. Nicht. Rolle. Im Geringsten. Jede Minute, die Sie auf diese Frage auf der Suche nach der Antwort verbringen eine Minute näher man mit funktionierenden Code habe sein können).

Wenn jemand zu dem Punkt, wo sie Notwendigkeit , um den Unterschied zu kennen, LinkedList schneller als Liste und könnten verwendet werden, wenn Sie nicht zufällig benötigen, Vorwärts-Lesen und Anhänge Funktionalität.

Wenn Sie nicht mit Hunderttausenden oder Millionen von Einträgen zu tun haben, und Sie haben Ihr Programm profiliert, um zu sehen, dass es ein großes Problem ist, werden Sie wahrscheinlich den Unterschied zwischen den beiden nicht bemerkt.

Anders als das:

  

LinkedList<T> stellt separate Knoten vom Typ LinkedListNode<T>, so das Einsetzen und Entfernen sind O (1) Operationen.

hier .

würde ich List<T> weil alle Ihre Daten sequentiell gespeichert werden, wenn sie Werttypen sind und immer noch gut mit Referenztypen (intern, List<T> verwaltet ein Array, dass es um einen Faktor von zwei bei jedem Lauf aus wächst Raum).

LinkedList<T> verwendet viel mehr Sinn machen, wenn die Dinge nicht IO gebunden. Die Menschen werden oft zitieren seine scheinbare „O (1)“ der Natur. Doch diese Rabatte, die tatsächlichen Kosten, die immer die Knoten mit erhöhten Chancen auf Seitenfehler kommen.

Wenn Sie zusammenhängende Speicherbereiche mit einem Array oder List<T> und vermeiden das Potenzial eines Seitenfehlers bekommen können, sind Sie viel besser dran mit modernem Prozessor und Hauptspeicher-Caching-Linien.

Wenn Sie wissen, wie viele Elemente im Voraus Sie haben ein Array verwenden. Wenn Sie eine gute Vorstellung davon, wie viele Elemente haben, verwenden Sie einen List<T> (und in dem Konstruktor übergibt die wahrscheinliche Obergrenze, um möglicherweise eine Umverteilung zu vermeiden).

Das einzige Mal, dass ich einen LinkedList<T> verwenden würde, wenn man von einem Wert ständig in einer Listenelemente stoßen müssen. Zum Beispiel, wenn Sie eine least recently Cache-Algorithmus verwendet und müssen etwas hinzufügen nach vorne und etwas vom Ende nehmen.

Für kleine Gegenstände, wird es wirklich keinen Unterschied machen. Der Generations Garbage Collector wird verstreuten Haufen Elemente zusammen im Laufe der Zeit so kompakt, dass die verknüpfte Liste wird nicht allzu schlecht bekommen.

Ich würde ein List<T> holen und mit ihm laufen, wenn Sie Probleme bemerkt (via Profilierung)

Wenn indiziert Zugriff nicht erforderlich ist, sind Sie wahrscheinlich besser dran mit einem LinkedList<T>. Es gibt nicht viel Unterschied, aber der LinkedList kann für den Appends schneller sein.

Ihre Anforderungen an die Schnittstelle gegeben, sollten Sie ICollection<T> überall in Ihrem Code statt mit Bezug auf eine bestimmte konkrete Klasse werden.

Der Grund dafür ist, dass, wenn Sie List verwenden, dann können Sie eine Menge Code schreiben, l[0] das erste Element erhalten verwendet. Auf der anderen Seite, wenn Sie verwenden LinkedList dann könnten Sie Anrufe verteilt im gesamten Code AddLast. Um die Wahl zu bewahren zu wechseln, müssen Sie verhindern, dass unbeabsichtigt abhängig zu werden auf Funktionen, die Sie nicht wirklich brauchen. Sie benötigen eine Schnittstelle zu verwenden, die beiden Behälter unterstützen.

So schreiben Sie eine Klasse wie folgt aus: 

public static class Collections
{
    public static ICollection<T> Make<T>()
    {
        return new List<T>();
    }
}

Dann, wenn Sie eine Sammlung benötigen, dies zu tun: 

ICollection<int> c = Collections.Make<int>();

Isolieren Sie Ihre Wahl des Behälters aus dem Rest des Programms. Nun, wenn Sie Ihre Meinung profilieren und ändern, man muss nur die Make<T> Methode bearbeiten.

Ein LinkedList wird mehr Speicher-Overhead führen (für die Knoten), aber es ist besser, wenn Sie viele Elemente in der Mitte einfügen. Eine verknüpfte Liste wird mehr Speicherzuordnungen verlangen, als LinkedListNode eine Klasse und wird dynamisch zugewiesen. Wenn Sie nicht Elemente einfügen (nur anhängen), würde ich eine Liste verwenden. Es sollte eine Liste so schnell oder schneller zum Anhängen, obwohl es gelegentlich vergrößern müssen.

Wenn Ihr Array groß genug sein wird, an der Materie, müssen Sie Ihre eigene Rolle ... sonst nur eine Liste verwenden.

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