Wie Elemente in einem Array verschieben?

StackOverflow https://stackoverflow.com/questions/148786

  •  02-07-2019
  •  | 
  •  

Frage

Ich habe ein Array von Elementen, die Zeit empfindlich sind. Nach einer Zeitspanne muss das letzte Element aus und ein neues Element fallen am Anfang setzen.

Was ist der beste Weg, dies zu tun?

War es hilfreich?

Lösung

Ich würde vorschlagen, eine Warteschlange verwenden, nur eine spezielle Instanz eines Arrays oder eine Liste. Wenn Ihr terminiertes Ereignis auftritt, Pop das letzte Element aus der Warteschlange, und dann auf den neue Element drücken.

Andere Tipps

Die wahrscheinlich einfachste Weg, dies mit einer Reihe zu tun ist, einen kreisförmigen Index zu verwenden. Anstatt immer auf der Suche Array [n], würden Sie array [CINDEX] (wobei CINDEX referrs an das Element im Array verweisen indiziert (CINDEX erhöht wird, basierend auf dem Arraysize (CINDEX% Arraysize)).

Wenn Sie sich für das älteste Element im Array fallen, würden Sie einfach das Element Referenz bei ((CINDEX + (Arraysize - 1))% Arraysize).

Alternativ können Sie einen VerketteteListe Ansatz.

Verwenden Sie einen Queue statt.

eine Warteschlange, vorzugsweise eine implementierte eine verknüpfte Liste verwendet wird.

Hier finden Sie aktuelle eine Queue mit anstelle einer einfachen Anordnung.

Eine Warteschlange funktionieren würde, wenn es eine feste Anzahl von Elementen.

Da die ‚Höhe der Zeit‘ bekannt ist, wie etwa ein SortedDictionary mit einem Datetime-Schlüssel und überschreiben Sie die Add-Methode alle Elemente mit den Tasten zu entfernen, die zu alt sind.

LinkedList hat addFirst und removeLast Mitglieder das sollte perfekt funktionieren.

EDIT: Ein Blick auf die Queue-Dokumentation, wie es scheint sie ein internes Array verwenden. Solange die Implementierung verwendet, sollte einen kreis Array-Typ-Algorithmus Leistung in Ordnung sein.

In csharp 3 Sie tun können: 

original = new[] { newItem }.Concat(
    original.Take(original.Count() - 1)).ToArray()

Aber Sie sind wahrscheinlich besser dran, eine spezielle Datenstruktur mit

Queue ist für FIFO-Arrays. Für allgemeinen Array Umgang, List (T) 's Insert(0, x) und RemoveAt(0) Methoden, um Elemente vor der Liste zu setzen oder zu entfernen, zum Beispiel.

Technisch benötigen Sie eine deque. Eine Warteschlange hat Elemente geschoben und tauchten aus nur ein Ende. A Deque ist an beiden Enden offen.

Die meisten Sprachen werden Array-Bearbeitung erlauben, nur das erste Element entfernen und ein anderes auf dem Ende zu setzen.

Alternativ können Sie jedes Element verschieben, durch Schleifen. Ersetzen nur jedes Element (ausgehend von den ältesten) mit seinem Nachbarn. Dann legen Sie das neue Element in dem letzten Elemente.

Wenn Sie wissen, dass Ihre deque nicht ab einer bestimmten Größe gehen, dann können Sie es kreisförmig machen. Sie werden zwei Zeiger müssen Sie sagen, wo die beiden Enden obwohl sind. Hinzufügen und Entfernen von Elementen, wird erhöhen / verringern Ihre Zeiger entsprechend. Sie werden einen Pufferüberlauf erkennen müssen (das heißt Ihre Zeiger ‚Kreuz‘). Und Sie haben die modulare Arithmetik verwenden, um Ihre Zeiger in einem Kreis gehen um die Array.

Oder Sie könnten jedes Element im Array Zeitstempel und sie entfernen, wenn sie zu ‚alten‘ worden. Sie können entweder tun dies, indem ein separates Array in gleicher Weise indexiert zu halten, oder durch eine Anordnung von zwei Elementanordnungen aufweist, wobei die Zeit in einem der Teilelemente gespeichert Stempel.

Wenn Sie suchen die schnellsten Art und Weise, dies zu tun, es geht um eine kreisförmige Anordnung sein: Sie halten den Überblick über Ihre aktuelle Position in der Matrix (ndx) und das Ende der so Array (Ende), wenn Sie ein Element einfügen, Sie implizit das älteste Element eliminieren.

eine kreisförmige Anordnung ist die schnellste Implementierung einer Warteschlange fester Größe, die ich kenne.

Zum Beispiel in C / C ++ es so für ints aussehen würde (beenden, wenn Sie erhalten eine 0): 

int queue[SIZE];
int ndx=0;      // start at the beginning of the array
int end=SIZE-1;
int newitem;
while(1){
  cin >> newitem;
  if(!newitem)  // quit if it's a 0
    break;
  if(ndx>end)   // need to loop around the end of the array
    ndx=0;
  queue[ndx] = newitem;
  ndx++
}

Viele Optimierung getan werden könnte, aber wenn Sie es selbst zu bauen wollen, ist dies die schnellste Route.

Wenn Sie nicht über die Leistung kümmern, verwenden Sie ein verschifft Queue-Objekt, weil es verallgemeinert werden soll.

Es kann oder auch nicht optimiert werden, und es kann nicht eine feste Größe Liste, so sicher sein, überprüfen Sie die Dokumentation auf mich vor dem Gebrauch.

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