Schnellste Möglichkeit, über einen Stapel in C#

Question

zu iterieren Ich finde, dass die Verwendung von GetEnumerator() und Casting IEnumerator.Current ist teuer. Irgendwelche besseren Vorschläge?

Ich bin offen für die Verwendung einer anderen Datenstruktur, wenn es ähnliche Funktionen mit besserer Leistung bietet.

Nach Gedanken:
Wäre ein allgemeiner Stapel eine bessere Idee sein, so dass die Besetzung nicht notwendig ist?

Answer 1

Sie Benchmarks gemacht haben, oder sie sind nur Bauchgefühl?

Wenn Sie der Meinung sind, dass der Großteil der Verarbeitungszeit für das Durchlaufen von Stapeln benötigt wird, sollten Sie einen Benchmark erstellen und sicherstellen, dass dies der Fall ist. Wenn ja, haben Sie ein paar Möglichkeiten.

1. den Code Redesign, so dass der Looping
2. Finden Sie ein schnelleres Schleifenkonstrukt ist nicht erforderlich. (Ich würde Generika empfehlen, auch wenn es nicht so wichtig wäre. Auch hier Benchmarks).

EDIT:

Beispiele für Looping, die nicht notwendig sein könnte, wenn Sie versuchen, Lookups in einer Liste zu tun oder zwei Listen oder ähnlichen entsprechen. Wenn das Looping sehr lange dauert, sehen Sie, ob es Sinn macht, die Listen in Binärbäume oder Hash-Maps zu setzen. Es könnte eine anfängliche Kosten für die Erstellung von ihnen geben, aber wenn der Code neu gestaltet wird, könnten Sie das zurück bekommen, indem Sie später O (1) Lookups durchführen.

Answer 2

Ja, die Verwendung eines generischen Stacks erspart den Cast.

Answer 3

Wenn Sie die Funktionalität eines Stapels (wie bei einer Liste oder einem anderen Sammlertyp) benötigen, dann verwenden Sie einen generischen Stapel. Dies wird die Dinge ein wenig beschleunigen, da der Compiler das Casting zur Laufzeit überspringt (weil es zur Kompilierungszeit gar nicht erkannt wird).

Stack<MyClass> stacky = new Stack<MyClass>(); 

foreach (MyClass item in stacky) 
{ 
    // this is as fast as you're going to get. 
} 

Answer 4

Aufzählen übernimmt eine generische IEnumerable<T> oder IEnumerator<T> nicht nicht eine Besetzung nicht erstellen, wenn die Iteration Variable vom Typ T ist, also ja mit der Gattungs in den meisten Fällen schneller sein wird, aber Generika haben einige sehr subtile Probleme, besonders wenn sie mit Werttypen verwendet werden.

Rico Mariani (Microsoft Performance Architekt) hat einige Beiträge, die Unterschiede detailliert und die Untermauerung

• Six Questions about Generics and Performance
• Performance Quiz #7 -- Generics Improvements and Costs
• Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Answer 5

Eine Alternative zum Erstellen eines Enumerators besteht darin, die ToArray-Methode zu verwenden und anschließend über das Array zu iterieren. Der Stapel-Iterator verursacht einen leichten Overhead, um zu prüfen, ob der Stapel geändert wurde, während die Iteration über das Array schnell erfolgen würde. Allerdings ist natürlich der Aufwand für die Erstellung des Arrays an erster Stelle. Wie Matten sagen, sollten Sie die Alternativen benchmarken.

Answer 6

Stack<T> (mit foreach) würde in der Tat die Besetzung speichern, aber tatsächlich Boxen isn't all that bad im großen Schema der Dinge. Wenn Sie Leistungsprobleme haben, bezweifle ich, dass dies der Bereich ist, in dem Sie viel Wert hinzufügen können.Verwenden Sie einen Profiler und konzentrieren Sie sich auf echte Probleme - sonst ist dies zu früh.

Beachten Sie, dass schneller sein kann (vermeidet den Overhead eines Enumerators), wenn Sie die Daten nur einmal lesen möchten (z. B. wenn Sie den Stack gerne verwenden); YMMV.

Stack<T> stack = null; 
    while (stack.Count > 0) 
    { 
     T value = stack.Pop(); 
     // process value 
    } 

Answer 7

In Bezug auf die Geschwindigkeit gibt es mehrere Variablen, abhängig vom Kontext. Beispielsweise können Sie in einer automatisch speicherverwalteten Codebasis wie C# Zuweisungsspitzen erhalten, die die Framerate in etwa einem Spiel beeinflussen können. Eine schöne Optimierung Sie für diese anstelle eines foreach machen kann, ist ein Enumerator mit einer while-Schleife:

var enumerator = stack.GetEnumerator(); 

while(enumerator.MoveNext()) { 
    // do stuff with enumerator value using enumerator.Current 
    enumerator.Current = blah 
} 

Soweit CPU-Benchmarks, ist dies wahrscheinlich nicht schneller als ein foreach, aber foreach kann unbeabsichtigte Zuteilung Spikes, die letztendlich die Leistung Ihrer Anwendung "verlangsamen" können.