Laden...

array als Ringpuffer

Erstellt von womi0074 vor 14 Jahren Letzter Beitrag vor 14 Jahren 15.148 Views
W
womi0074 Themenstarter:in
3 Beiträge seit 2009
vor 14 Jahren
array als Ringpuffer

Hallo,

Ich habe ein großes Problem und zwar suche ich eine Möglichkeit einen Array vom Typ integer als eine Art Wasserfaß zu benutzen.

Erklärung:

ich habe Werte welche nach und nach einen Array befüllen dieser sollte 10 Werte aufnehmen.

Wenn der Letzte geschrieben wurde und ein neuer Wert zum Speichern bereit steht,
soll der erste verloren gehen und alle anderen nach rutschen damit der Neue Wert in den letzten und somit wieder freien array geschrieben werden kann.

arr[1] = 1;
arr[2] = 2;
.
.
.
arr[10] = 10;

Wenn abschließend der 11. Wert gespeichert werden soll, dann

arr[1] = 2;
arr[2] = 3;
.
.
.
arr[10] = 11;

Ich hoffe, dass mir jemand Helfen kann, bis jetzt habe ich leider nichts finden können, ich weis aber auch nicht wie ich nach diesem array-Schieben, wie auch immer Suchen muß.

Danke.

J
237 Beiträge seit 2008
vor 14 Jahren

Du könntest eine eigene Klasse dafür schreiben. Ich wüsste nicht, dass es sowas schon gibt. Ist aber leicht selbst zu implementiern.
PS: Arrays indiziert man von 0 bis Length - 1.

Grüße, JasonDelife.

Beim Programmieren löst man die Probleme, die man nicht hätte, programmierte man nicht.

2.223 Beiträge seit 2005
vor 14 Jahren

Hallo womi0074 und Herzlich Willkommen hier im Forum,

an dieser Stellen empfehle ich kein Array sonden eine generische List<int>

und beim jedem einfügen prüfst du wie groß deine Collection ist und entfernst gegeben falls den ersten

Herzliche Grüße
BlackCoin

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo womi0074,

nimm lieber eine List(T) (System.Collections.Generic).

Dann kannst du einfach mit list.Add() was hinten einfügen. Zum "kürzen" dann einfach am Anfang löschen:


while (list.Count>5)
	list.RemoveAt(0);

Wenn du wirklich Arrays brauchst, kannst du dann auch List.ToArray() aufrufen.

Gruß,
dN!3L

1.361 Beiträge seit 2007
vor 14 Jahren

Hi womi0074,

ob du nun Array oder List<int> verwendet ist im Grunde egal. Du gibst ja eine Kapazität vor, die nicht überschritten wird. Diese ist fest. Damit bringen dir die dynamischen Reallokierungsfähigkeiten von List<> nix.

Was du suchst ist eine Queue. Implementiert als Ringpuffer mit fester Kapazität.

beste Grüße
zommi

2.891 Beiträge seit 2004
vor 14 Jahren

Damit bringen dir die dynamischen Reallokierungsfähigkeiten von List<> nix.

Darum geht es auch gar nicht. In einer List kann man an beliebiger Stelle löschen und einfügen. Im Array müsstest du selbst schieben, was aufwändig ist.

Was du suchst ist eine Queue. Implementiert als Ringpuffer mit fester Kapazität. Nur gibt es sowas standardmäßig nicht. Bzw. die Implementierung als Liste, die hinten anfügt und vorn bei Bedarf löscht, ist bedeutend einfacher.

Gruß,
dN!3L

R
3 Beiträge seit 2009
vor 14 Jahren

Wenn es nicht unbedingt ein Array sein muss, würde ich mit einer Queue arbeiten.

Queue<int> MyQueue = new Queue<int>();

mit

MyQueue.Enqueue(5);

wird 5 an die Queue angehängt.

Am besten regelst du es so:


public void addXtoQueue(int x)
  if (MyQueue.Count == 10)
  {
    MyQueue.Dequeue(); //entfernt das erste Element
  }
  MyQueue.Enqueue(x);
}

Wenn du das aber wirklich mit einem Array lösen willst, dann vllt so:


int?[] MyArray = new int?[10];

for (int i = 0; i < MyArray.Length; i++)
            {
                MyArray[i] = null;
            }

Und zum hinzufügen von neuen Werten:


public void addXtoArray(ref int?[] pArray, int x)
        {
            if (pArray[9] != null)
            {
                int?[] TmpArray = new int?[10];
                for (int i = 0; i < pArray.Length - 1; i++)
                {
                    TmpArray[i] = pArray[i + 1];
                }

                pArray = TmpArray;
                pArray[9] = x;
            }
            else
            {
                for (int i = 0; i < pArray.Length; i++)
                {
                    if (pArray[i] == null)
                    {
                        pArray[i] = x;
                        break;
                    }
                }
            }
        }

Somit kannst du immer wieder werte dazupacken und wenn alle voll sind, wird der erste gelöscht und ein neuer ans Ende gepackt 😃

J
237 Beiträge seit 2008
vor 14 Jahren

Man könnte es sogar als Extension-Method implementieren. Dann ist es wirklich einfach zu benutzen.

Grüße, JasonDelife.

Beim Programmieren löst man die Probleme, die man nicht hätte, programmierte man nicht.

2.891 Beiträge seit 2004
vor 14 Jahren

Wenn es nicht unbedingt ein Array sein muss, würde ich mit einer Queue arbeiten.

... auf die man aber nicht Indexiert zugreifen kann. Mit einer Liste geht dass. Und die Implementierung als Ringpuffer ist auch schnell erledigt:

public class Wasserfass<T> : List<T>
{
	public void Add(T value,int maxCount)
	{
		while (this.Count>=maxCount)
			this.RemoveAt(0);
		this.Add(value);
	}
}

Und wie bereits erwähnt, wenn es unbedingt ein Array sein soll, gibt es ToArray(), da muss man auch nichts selbst coden.
Warum so kompliziert, wenn's auch einfach geht?

Gruß,
dN!3L

1.361 Beiträge seit 2007
vor 14 Jahren

Mhh,

Damit bringen dir die dynamischen Reallokierungsfähigkeiten von List<> nix.

Darum geht es auch gar nicht. In einer List kann man an beliebiger Stelle löschen und einfügen. Im Array müsstest du selbst schieben, was aufwändig ist.

Was du suchst ist eine Queue. Implementiert als Ringpuffer mit fester Kapazität.

Nur gibt es sowas standardmäßig nicht. Bzw. die Implementierung als Liste, die hinten anfügt und vorn bei Bedarf löscht, ist bedeutend einfacher.

Nunja, über die Einfachheit lässt sich freilich streiten. Zumal eine passende Implementierung überall im Internet zu finden ist.
Meine Sicht der Dinge ist:
Wenn man eine Datenstruktur mit gewissen Eigenschaften benötigt, sollte man keine andere "missbrauchen", wenn diese nicht dafür geeignet ist, nur weil der Code damit 3 Zeilen lang ist. Und schon garnicht, wenn dadurch die Performance Größenordnungen drunter leidet.

Ich seh hier die Verwendung von List<T>.removeAt(0) ebenfalls als Schlemiel an.

Eine m.E. besser Variante wäre beispielsweise folgende minimalistische Implementierung:


class FixedSizeArrayQueue<T>
{
	private readonly int capacity;
	private int pointer;	// index of first element;
	private int length;
	private T[] array;
	
	public int Length { get{ return length; } }
	public int Capacity { get{ return capacity; } }

	public T this[int i]
	{
		get
		{
			if(i>=length)
				throw new IndexOutOfRangeException();
			return array[(pointer + i) % capacity];
		}
	}
	
	public void add(T t) // aka enqueue
	{
		array[(pointer + length) % capacity] = t;
		if(length<capacity) // there is enough place
			length++;
		else // the first element was overwritten
			pointer = (pointer+1) % capacity;
	}
	
	public T remove() // aka dequeue
	{
		if(isEmpty())
			throw new IndexOutOfRangeException(); // or another
		
		T result = array[pointer];
		pointer = (pointer+1) % capacity;
		length--;
		return result;
	}
	
	public bool isEmpty()
	{
		return (length==0);
	}
		
	public FixedSizeArrayQueue(int cap)
	{
		capacity = cap;
		array = new T[cap];
		length = 0;
		pointer = 0;
	}
}

Aber vielleicht gibts ja auch ein schon besseres Snippet hier im Forum (mit IList-Interface und synchronisiert oder so)

beste Grüße
zommi

C
114 Beiträge seit 2008
vor 14 Jahren

Annsonsten nimm ein normales Array und merke dir einfach immer den letzten Punkt, an dem du geschrieben hast in einer Variablen. Wenn du dann z.B. ein Array der Länge 10 hast wäre beim 10. einfügen noch fass[9] der richtige Befehl. Danach springst du wieder zur 0 und überschreibst somit automatisch das erste Element.

//Edit: Mir scheint Zommi hat was vergleichbares schon verfasst.

„Heute back ich, morgen brau ich,
übermorgen cast ich die Königin nach int;
ach, wie gut dass niemand weiß,
dass ich Rumpelstilzchen heiß!“

"Bei Stylefragen sollteste nen Mac-User oder ne Frau fragen."

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zommi,

wie du schon sagtest, kann man drüber streiten.

Wenn man eine Datenstruktur mit gewissen Eigenschaften benötigt, sollte man keine andere "missbrauchen", wenn diese nicht dafür geeignet ist, nur weil der Code damit 3 Zeilen lang ist. Und schon garnicht, wenn dadurch die Performance Größenordnungen drunter leidet.

Meine Sicht der Dinge: Ich finde nicht, dass die Liste dafür ungeeignet ist. Man kann indexiert auf Elemente zugreifen. Wenn die Kapazität überschritten wird, soll das erste Element gelöscht werden und das neue hinten angefügt werden.
Und warum sollte die Performance drunter Leiden? Die leidet höchstens, wenn die Liste dynamisch vergrößert wird. Kann man durch initiale Angabe vermeiden.
Und jeder Code, den man nicht warten muss (= den es nicht gibt), ist guter Code.

Beste Grüße,
dN!3L

1.361 Beiträge seit 2007
vor 14 Jahren

Und warum sollte die Performance drunter Leiden?

Nach dem Löschen des ersten Elements müssen alle Arrayelement vorverschoben werden. Jedes muss angefasst werden. Das kostet leider.

Zitat von List<T>.RemoveAt: Diese Methode ist eine O(n)-Operation, wobei n für (Count - index) steht.

Wenn man hingegen ringförmig überschreibt und sich immer die Position merkt und verschiebt, ist das O(1).

beste Grüße
zommi

2.223 Beiträge seit 2005
vor 14 Jahren

Hallo ...

ich kann dN!3L nur zustimmen,
wenn man mit diesen paar Zeilen, ein Problem so einfach mit einer List<T> lösen kann, dann sollte man es auch tun.

getreu dem Motto - Keep it simple, stupid (KISS)
http://www.clean-code-developer.de/wiki/CcdRoterGrad

Herzliche Grüße
BalckCoin

1.361 Beiträge seit 2007
vor 14 Jahren

Wenn man immer nur dem KISS-Prinzip folgt, bräuchte man den StringBuilder und ähnliches nicht.
Einfacher als Strings mit "+" zu verketten gehts nicht, trotzdem rät man davon ab, wenn man es mehr als einmal tun will.

Im Übrigen ist der obige Code ja auch nicht wirklich wasserdicht. (Und das bei nem Wasserfass 😉). List<T> implementiert bereits Add, und die ist nicht virtual, abstract, oder override. Also kanns schwupps passieren, dass man doch die Basis-Methode aufruft und niemand das "Überlaufen" kontrolliert.

Wenn man nun als Ausweg den Typ von IList erben lässt, dann muss man am Ende auch wieder zig Methoden implementieren und ob man die nun einfach weiterdelegiert oder mit 5 Zeilen Code füllt (und damit ne effiziente Implementierung erhält) kann man sich nun aussuchen.

beste Grüße
zommi

5.742 Beiträge seit 2007
vor 14 Jahren

Hallo zusammen,

ich kann dN!3L nur zustimmen [...] getreu dem Motto - Keep it simple, stupid (KISS)

ich stimme zommi zu: Hier sollte eine eigene Klasse verwendet werden (z.B. die vorgestellte FixedSizeQueue).
Getreu nach dem Motto Principle of least astonishment.
Wenn ich mit einer Liste arbeite, erwarte ich nicht, dass ich nach dem Einfügen eines Elementes ein anderes entfernen muss.
Erst recht erwarte ich nicht, dass ich durch ein simples Einfügen eines Elements die Anwendung in einen ungültigen Zustand (= mehr als 10 Elemente in der Liste) bringen kann.
Außerdem geht aus einer List<> nicht klar hervor, dass die Elemente in einer gewissen Reihenfolge abgearbeitet werden sollen.

Wie die konkrete Implementierung aussieht, spielt IMHO eine untergeordnete Rolle; wichtig ist das Interface.

//EDIT: Oha - da stand tatsächlich "Fetreu" statt "Getreu"...

2.223 Beiträge seit 2005
vor 14 Jahren

Hallo @ll,

das, das ganze in einer Klasse realisiert wird sollte sich ja von selbst verstehen,

ich meinte nur das die Datenbasis die Intern verwendet wird ne generische List sein könnte.

Aber das ist ja das schöne am Programmieren, es gibt meistens mehr als einen Weg es zu Realisieren

Herzliche Grüße
BlackCoin

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo blackcoin,

ich meinte nur das die Datenbasis die Intern verwendet wird ne generische List sein könnte.

dagegen spricht ja auch nichts. Es spricht nur was dagegen Remove/RemoteAt zu verwenden.

Bei 10 Elementen mag das noch keinen Unterschied machen, aber gerade wenn man die Queue als eigene Klasse implementiert, wird man sie potentiell auch in anderen Situation benutzen. Und wenn man da dann 10000 oder mehr Elemente hat, kann einem das leicht auf die Füße fallen. Natürlich auch nicht bei einem Remove, aber bei 10000 Elementen kann es leicht passieren, dass man 10000 Removes macht. Und dann kommt man in Bereiche, wo es spürbar wird.

Sicher sollte man Implementierungen einfach halten, aber mal sollte sich deshalb noch lange keinen quadratischen Aufwand einhandeln.

Was in der Summe nichts anderes bedeutet, als dass ich mich zommi und winSharp93 anschließe. 😃

herbivore

W
womi0074 Themenstarter:in
3 Beiträge seit 2009
vor 14 Jahren

Hallo,

und Danke für die schnellen und Zahlreichen Antworten.
Ich werde das gleich einmal versuchen.

2.891 Beiträge seit 2004
vor 14 Jahren

Hallo zusammen,

Wie die konkrete Implementierung aussieht, spielt IMHO eine untergeordnete Rolle; wichtig ist das Interface. Full ACK.
(Ich bin im Übrigen auch voll dafür, unbedingt eine neue Klasse anzulegen.) Aber man kann ja erstmal "einfach" anfagen und wenn ich dann mal wirklich 10k Elemente benutze und es wirklich zu Performanzschwierigkeiten kommt, dann kann man den Code optimieren und einen Ringpuffer mit Zeiger auf Anfang und Ende implementieren.

Sicher sollte man Implementierungen einfach halten, aber mal sollte sich deshalb noch lange keinen quadratischen Aufwand einhandeln.

Man beachte aber, dass das O-Kalkül nichts über die reale Laufzeit aussagen kann (Konstanten werden ja bekanntlich gestrichen). A mit O(x²) könnte bis 1 Mrd. Elemente immer noch 1k mal schneller sein, als B mit O(1)...

Beste Grüße,
dN!3L

P.S.: Interessant, wie die Prinzipien von CCD gegeneinander ausgespielt werden (können).

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo dN!3L,

und es wirklich zu Performanzschwierigkeiten kommt, dann kann man den Code optimieren und einen Ringpuffer mit Zeiger auf Anfang und Ende implementieren.

ja, das ist normalerweise auch meine Rede. Nur hat diese Rede eine Ausnahme: Unterschiedliche Aufwandsklassen. Wenn schon von vorneherein feststeht, dass es eine Implementierungsmöglichkeit mit einer niedrigeren Aufwandsklasse gibt, dann sollte man diese in der Regel auch tatsächlich wählen.

Man beachte aber, dass das O-Kalkül nichts über die reale Laufzeit aussagen kann (Konstanten werden ja bekanntlich gestrichen). A mit O(x²) könnte bis 1 Mrd. Elemente immer noch 1k mal schneller sein, als B mit O(1)...

Theoretisch richtig, praktisch normalerweise irrelevant, insbesondere für den Fall, über den wir reden. Da ist ein solcher konstanter Faktor völlig undenkbar.

herbivore

1.564 Beiträge seit 2007
vor 14 Jahren

@all:
Ich schließe mich zommi und herbivore an. Bei einem echten Ringbuffer finde ich einen Array irgendwie auch sinnvoller. Hat schon den Vorteil, dass ich ziemlich deutlich (über eine Exception) mitbekomme wenn in der Implementierung was falsch ist.

@womi0074
Ich habe sowas letztens erst für einen DbReader benötigt. Wenn du willst kann ich die Files mal hochladen. Du müsstest halt das DB-Zeug rausschmeißen und durch deine eigentliche Anforderung ersetzen, aber den Core kannst du verwenden.

Grüße
Flo

Blog: Things about Software Architecture, .NET development and SQL Server
Twitter
Google+

Je mehr ich weiß, desto mehr weiß ich was ich noch nicht weiß.

W
womi0074 Themenstarter:in
3 Beiträge seit 2009
vor 14 Jahren

Hallo Flo,

Die Files als Beispiel würden mich schon Interessieren.

Gruß
womi0074

1.564 Beiträge seit 2007
vor 14 Jahren

Hab' die Files angehängt. Ich habe das Ding gebaut weil ich das Interface der DbReader Klasse ziemlich mau finde, aber die Möglichkeit benötige sehr große Datenmengen aus einer Datenbank zu streamen.

Kurze Erläuterung:
ResultTable ist die Haupt-Klasse - die auch den Ringbuffer implementiert.
ResultColumn sind die Spalten des zurückgelieferten Datenbank-Ergebnisses.
ResultRow sind die gestreamten Zeilen des Ergebnisses.

Wenn du irgendwo einen SQL Server mit einer AdventureWorks zur Verfügung hast kannst du das Snippet aus der "HowToUse.txt" einfach kopieren und die aktuelle Funktionalität testen.

Disclaimer
Ist jetzt nicht besonders toll kommentiert. Das wollte ich noch machen 😁

Grüße
Flo

Blog: Things about Software Architecture, .NET development and SQL Server
Twitter
Google+

Je mehr ich weiß, desto mehr weiß ich was ich noch nicht weiß.