Wie wird List <T> intern abgebildet?

Wird es intern als Array behandelt oder wird es von der CLR als völlig anderer Typ behandelt?Wie wird List <T> intern abgebildet?

Ich versuche, ganzzahlige Werte in die Liste zu implementieren.

List<int> lst = new List<int>(); 
lst.Add(3); 
lst.Add(4);

vs.

Ich erstelle ein Array von ganzen Zahlen

int[] arr = new int[2]; 
arr[0] = 3; 
arr[1] = 4;

bessere Zeitspanne Ergebnisse Array zurückgibt. Warum bevorzugen Leute die Liste <>.

Quelle

2012-08-04 Sunny R Gupta

Sie könnten versuchen [ILSpy] (http://ilspy.net) und schauen Sie selbst. Der Grund für eine dynamisch anwachsende/schrumpfbare Liste besteht darin, dass sie keine feste Größe wie 'Array' ist. –

List<> ist eine Implementierung einer Datenstruktur, die sich um die bedarfsgerechte Zuweisung von Speicher kümmert; es erlaubt Einfügen und Löschen bei jedem Index usw. Daher ist es viel bequemer als ein einfaches Array.

Unter der Haube verwendet die aktuelle List<> Implementierung ein Array für die Speicherung, und der Aufwand bei array-ähnlichen Operationen ist minimal. Der zusätzliche Komfort ist normalerweise den kleinen (wenn überhaupt relevanten) Leistungsunterschied wert. Das Hinzufügen von Elementen ist in der Regel schneller, da die Liste Speicherbereiche zuweist und keine neue Zuweisung erfordert und bei jedem Hinzufügen kopiert wird (im Vergleich zum reinen Array, bei dem die Length immer an die Größe im Speicher gebunden ist).

Quelle

2012-08-04 09:50:00 Lucero

Also, was Sie sagen, ist, obwohl vernachlässigbar, 'List <>' wird eine langsamere Reaktion, in Bezug auf _Speed_, als eine 'Array' bieten? –

Natürlich. Liste ist eine Abstraktion über Array, und Abstraktionen kosten zusätzliche CPU-Zyklen. Wie auch immer, ich stimme Lucero zu, unter normalen Bedingungen ist List mehr als schnell genug. – Steven

Die "Antwortzeit" ist normalerweise irrelevant, die Anfrage wird nach einer (schnellen und billigen) Schrankenüberprüfung an das zugrunde liegende Array weitergeleitet. Dies ist wahrscheinlich sogar durch die Laufzeit bedingt, so dass es nicht einmal einen zusätzlichen Anruf benötigt. – Lucero

Eine normale Direktzugriffsliste hat normalerweise ein internes Array. Die .NET List<T> Implementierung führt dies aus. Andere Implementierungen wie LinkedList<T> verwenden Ketten von Elementen mit Referenzen anstelle von Arrays. Exotischere Listen können Bäume intern zur Bestellung verwenden.

Das interne Array in List<T> ist mit einer kurzen Länge (4 glaube ich) initialisiert, und wenn Sie versuchen, außerhalb der maximalen Grenzen des Arrays hinzuzufügen, wird es erweitert. Da dies zeitraubend sein kann (das Array muss kopiert werden), ist das Array doppelt so groß, d. H. Wenn Sie das fünfte Element hinzufügen, wird das interne Array auf die Länge 8 und so weiter skaliert.

Quelle

2012-08-04 09:54:02

Ich erinnere mich zu lesen, dass 'List <>' Datenstruktur für _Speed_ optimiert ist, während 'Array' DS für _Memory_ optimiert ist. Sie scheinen der Tatsache zu widersprechen, dass 'List <>' für _Speed_ optimiert ist. (Wenn wir sagen, dass es neu skaliert und neu zugewiesen wird, wenn man sich außerhalb der Grenzen bewegt) –

Ich stimme dieser Unterscheidung nicht zu. Eine Liste HAT ein Array intern, so unterscheidet sich im Wesentlichen nicht von einem Array Speicher-weise. Sie zahlen mit der Liste eine kleine Leistungseinbuße, und für diese Kosten erhalten Sie eine dynamische/veränderbare Sammlung. Der größte Unterschied zwischen Liste und Array besteht also darin, dass Sie Dinge immer zu einer Liste hinzufügen können. –

@bugbuster, wenn Sie ein Element zu einem Array hinzufügen möchten (so dass 'Length 'größer wird, dh * ein vorhandenes Element nicht * ändert *), müssen Sie das Array ebenfalls neu zuweisen. Die Liste wächst in größeren Blöcken und verfolgt die Anzahl der verwendeten Elemente des Arrays, wodurch sie für sequentielle Adds schneller ist. – Lucero

Wie wird List <T> intern abgebildet?

Antwort

Verwandte Themen