Warum sind Stack <T> und Queue <T> mit einem Array implementiert?

Question

lese ich von den Albahari Brüder in aller Kürze C# 4.0 und ich kam in diesem:

Stacks sind intern mit einem Array implementiert, die je nach Bedarf Größe verändert hat, wie mit Queue und List. (S. 288, Absatz 4)

Ich kann nicht helfen, aber wundere mich warum. LinkedList bietet O (1) Kopf- und Fußzeileneinfügungen und -löschungen (die für einen Stapel oder eine Warteschlange gut funktionieren sollten). Ein resizierbares Array hat O (1) amortisiert einfügen (wenn ich mich recht erinnere), aber O (n) schlimmsten Fall (ich bin nicht sicher über löschen). Und es benötigt wahrscheinlich mehr Platz als die verknüpfte Liste (für große Stapel/Warteschlangen).

Gibt es mehr als das? Was ist der Nachteil einer doppelt verknüpften Listenimplementierung?

Answer 1

aber O (N) worst case

Die amortisieren worst case noch O (1). Lange und kurze Einfügezeiten mitteln sich aus - das ist der springende Punkt bei der amortisierten Analyse (und beim Löschen gleich).

Ein Array verwendet auch weniger Speicherplatz als eine verkettete Liste (die schließlich einen zusätzlichen Zeiger für jedes Element speichern muss).

Darüber hinaus ist der Overhead nur viel weniger als bei einer verknüpften Liste. Alles in allem ist eine Array-basierte Implementierung für fast alle Anwendungsfälle (viel) effizienter, auch wenn der Zugriff manchmal etwas länger dauert (tatsächlich kann eine Warteschlange durch Aufnahme etwas effizienter implementiert werden) Vorteil der Seiten, die selbst in einer verknüpften Liste verwaltet werden - siehe C++ 'std::deque Implementierung.

Answer 2

Hier ist eine grobe guestimation der Speicherressourcen für einen Stapel von 100 System.Int32 s verwendet:

Ein Array Implementierung würde folgendes erfordern:

type designator       4 bytes 
object lock        4 
pointer to the array      4 (or 8) 
array type designator     4 
array lock        4 
int array        400 
stack head index       4 
             --- 
Total         424 bytes (in 2 managed heap objects) 

Eine verkettete Liste Implementierung folgendes erfordern würde:

type designator       4 bytes 
object lock        4 
pointer to the last node     4 (or 8) 
node type designator   4 * 100 = 400 
node lock     4 * 100 = 400 
int value     4 * 100 = 400 
pointer to next node 4 (or 8) * 100 = 400 (or 800) 
            ----- 
Total        1,612 bytes (in 101 managed heap objects) 

Die Hauptnachteil der Array-Implementierung wäre das Kopieren des Arrays, wenn es e sein muss x erweitert. Wenn Sie alle anderen Faktoren ignorieren, wäre dies eine O (n) -Operation, wobei n die Anzahl der Elemente im Stack ist. Dies scheint eine ziemlich schlechte Sache zu sein, abgesehen von zwei Faktoren: Es passiert fast nie, da die Expansion in jedem Inkrement verdoppelt wird, und der Array-Kopiervorgang ist hoch optimiert und ist erstaunlich schnell. Somit wird die Erweiterung in der Praxis leicht durch andere Stapeloperationen überlagert.

Ähnlich für die Warteschlange.

Answer 3

Dies liegt daran, dass .NET auf modernen Prozessoren ausgeführt wurde. Die sind viel, viel schneller als der Speicherbus. Der Prozessor läuft bei etwa 2 Gigahertz. Der Arbeitsspeicher in Ihrer Maschine wird typischerweise mit ein paar hundert Megahertz getaktet. Das Lesen eines Bytes aus dem RAM dauert weit über hundert Taktzyklen.

Was die CPU-Caches auf modernen Prozessoren sehr wichtig macht, wird eine große Menge an Chip-Immobilien verbrannt, um die Caches so groß wie möglich zu machen. Typisch sind heute 64 KByte für den L1-Cache, der schnellste Speicher und physisch sehr nahe am Prozessorkern, 256 KByte für den L2-Cache, langsamer und weiter weg vom Kern, rund 8 MByte für den L3-Cache, langsamer und am weitesten entfernt weg, von allen Kernen auf dem Chip geteilt.

Um die Caches effektiv zu machen, ist es sehr wichtig, sequentiell auf den Speicher zuzugreifen. Das Lesen des ersten Bytes kann sehr teuer sein, wenn ein L3- oder RAM-Speicherzugriff erforderlich ist, die nächsten 63 Bytes sind sehr billig. Die Größe der "Cache-Zeile", die Einheit der Datenübertragung für den Speicherbus.

Dies macht ein Array mit Abstand die effektivste Datenstruktur, seine Elemente werden sequenziell im Speicher gespeichert. Und eine verkettete Liste ist bei weitem die schlechtest mögliche Datenstruktur, ihre Elemente sind natürlich durch den Speicher verstreut, was möglicherweise den sehr teuren Cache-Fehltreffer für jedes Element zur Folge hat.

Dementsprechend werden alle .NET-Sammlungen außer LinkedList <> als Arrays intern implementiert. Beachten Sie, dass ein Stack <> bereits natürlich als Array implementiert ist, da Sie nur ein Element vom Ende des Arrays verschieben können. Eine O (1) -Operation. Die Größe des Arrays wird amortisiert O (logN).