Performance: die schneller Rückwärts auf einem Stapel Aufruf oder Elemente in einem Array

Question

popping Ich habe mich gefragt, welche Implementierung würde eine bessere Leistung haben:

Ich brauche alle Elemente aus einem Stapel löschen mit Ausnahme der ersten 10 an der Spitze .

Diese 10 müssen dann in ihrer ursprünglichen Reihenfolge in den Stapel gelegt werden.

Ich dachte, von 2 nähert sich

die erste:

FilterRecord[] records = new FilterRecord[10]; 

     for (int i = 0; i < records.Length; i++) 
     { 
      records[i] = _InternalCollection.Pop(); 
     } 

     _InternalCollection.Clear(); 

     for (int i = records.Length - 1; i >= 0; i--) 
     { 
      _InternalCollection.Push(records[i]); 
     } 

Die zweite:

int count = _InternalCollection.Count - 10; 
       _InternalCollection.Reverse(); 


       for (int i = 0; i < count; i++) 
       { 
        _InternalCollection.Pop(); 
       } 

       _InternalCollection.Reverse(); 

Jede Hilfe oder Richtlinien oder andere impemenations wäre willkommen.

Answer 1

Ich denke, dass von dem Stapel knallen Gegenstände zu vermeiden wird Ihr Code die Leistung mehr als die Alternative zwischen den beiden verbessern Ansätze, die Sie vorschlagen. Ich würde empfehlen, auf dem Stapel einen neuen Stapels mit dem Inhalt des letzten Elements Zuweisung Linq mit etwa so:

var newStack = new Stack<FilterRecord>( 
    _InternalCollection.Take(10) 
         .Reverse()); 

_InternalCollection = newStack; 

Wenn Sie nicht der Verwendung von Generika, um Sie mit dem eingebauten Iterator das gleiche tun:

var iterator = _InternalCollection.GetEnumerator(); 
int i = 9; 
while(iterator.MoveNext() && i-- >= 0) 
{ 
    newStack.Push(iterator.Current); 
} 
_InternalCollection = newStack; 

Answer 2

Das hängt davon ab, dass Sie davon ausgehen, dass die Reverse() -Methode nicht genau das tut. Nur zwei Möglichkeiten zu wissen: 1.) Führen Sie Ihren Code und sagen Sie uns 2.) Nachschlagen der Umsetzung von Reverse().

Answer 3

Ihr erster Algorithmus hat zwei For-Schleifen, also O (2N). Ihr zweiter Algorithmus hat eine for-Schleife, aber wir müssen annehmen, dass intern Reverse() eine O (N) -Operation ist, also sein O (3N).

Ich bin nicht sicher, ob der Aufruf Clear() in Ihrem ersten Algorithmus O (N) oder O (C) ist.

Answer 4

Es ist oft schwer zu sagen auf diese Art von Dingen. Mach einfach einen wahnsinnig großen Stack, ruf beide an und Zeit sie. Dann wirst du es wissen.

Answer 5

Kommt drauf an. Es gibt zwei Dinge, die Sie tun können:

• Test durch sie es für ein paar hundert Iterationen ausgeführt wird (weniger oder mehr je nach Größe)
• Blick auf ihre Implementierungen

die Methode analysieren in dem ein Stapel (konzeptionell) implementiert wird, mit umgekehrten wäre die langsamste, da es alles des Stapels pop und dann zurück in, in umgekehrter Reihenfolge. Wenn es intern ausgewählt wird, wählt es einfach einen anderen Startindex für den Beginn des Popups aus, es könnte schneller sein.

In beiden Fällen, einfach gesagt, mit Reverse() scheint ineffizient, wie Sie diese Operation zweimal durchführen.

Answer 6

Ich würde vorschlagen, werfen Sie einen Blick auf die tatsächliche Umsetzung von Reverse() - Sie können die .Net Reflector nützlich dafür finden.

Answer 7

Wenn sich nur wenige Elemente im Stapel befinden, ist der Unterschied so gering, dass eine Optimierung nicht sinnvoll ist.

Wenn es viele Elemente in dem Stapel sind, wäre dies der schnellste sein:

FilterRecord[] records = new FilterRecord[10]; 

for (int i = 0; i < records.Length; i++) { 
    records[i] = _InternalCollection.Pop(); 
} 

_InternalCollection = new Stack<FilterRecord>(); 

for (int i = records.Length - 1; i >= 0; i--) { 
    _InternalCollection.Push(records[i]); 
} 

D.h. Werfen Sie einfach den aktuellen Stapel weg, nachdem Sie die gewünschten Artikel erhalten haben, und lassen Sie den Müllsammler sich darum kümmern. Wenn Sie die Clear-Methode verwenden, werden die Referenzen aus dem Stapel entfernt, aber die Kapazität bleibt erhalten.

Da Sie nur zehn der Elemente im Stapel berühren, unabhängig davon, wie viele davon vorhanden sind, handelt es sich um eine O (1) -Operation anstelle einer O (n) -Operation.

(Beachten Sie, dass Sie die Größe des Arrays verwenden, wenn Sie es erklären, nicht die hoechste Index.)

Answer 8

Wie wäre es, wenn Sie keinen Stapel verwenden würden? Wie wäre es mit einer LinkedList und dann mit der RemoveLast-Methode, um das zu tun, was Sie brauchen?

Einige grobe Code, braucht mehr Arbeit, aber Sie bekommen die Grundidee:

public class CustomStack<T> 
    { 
     private LinkedList<T> list; 

     public CustomStack() 
     { 
      list = new LinkedList<T>(); 
     } 

     public void Push(T item) 
     { 
      list.AddFirst(item); 
     } 

     public T Pop() 
     { 

      var result = list.First.Value; 
      list.RemoveFirst(); 
      return result; 
     } 

     public void TrimLast(int amountToLeave) 
     { 
      while (list.Count > amountToLeave) 
      { 
       list.RemoveLast(); 
      } 
     } 
    } 

Answer 9

Ich denke, dass Sie ziemlich viel Zählung auf der Double-Reverse kann langsamer sein. Ihre Laufzeit für 1) ist konstant (O (1)) in Bezug auf _InternalCollection.Length (unter der Annahme, Clear ist konstante Zeit) und O (n) in Bezug auf die Anzahl der Elemente, die Sie behalten möchten. 2) wird langsamer, linear desto größer _InternalCollection ist (O (n))

Sie könnten auch in Betracht ziehen, Ihre _InternalCollection in eine Deque (Double ended queue) zu ändern. Ein Deque unterstützt O (1) amortisierte Zeit, um Elemente von jedem Ende hinzuzufügen/zu entfernen. Natürlich (AFAIK) gibt es keine Standard-Implementierung, also müssten Sie Ihre eigene oder rollen.

Answer 10

memcpy die letzten 10 Elemente auf dem Stapel, wo Sie sie haben möchten.

Dann deklarieren Sie den Stapel zu 10 Stück lang.