Hallo,
ich suche nach einem Algorithmus für folgendes Problem: Ich muss eine
Liste von Sequenznummern führen, die von einer Gegenstelle kommen. Die
Sequenznummern werden im Prinzip immer nur inkrementiert, es kann aber
sein, dass dazwischen einzelne fehlen und erst später ankommen und für
die Zukunft sollte es abgedeckt sein, dass die Sequenznummern von
verschiedenen Gegenstellen kommen, sodass deutlich mehr Unordnung
herrscht.
Ich muss jederzeit relativ einfach das längste durchgehende Interval von
empfangenen Sequenznummern von 0 weg angeben können. Die Nummern liegen
derzeit im Bereich 0 - 2^31, für spätere Applikationen brauchen wir aber
sicher den Bereich 0 - 2^50, also sollte der Algorithmus auch für 64 Bit
Sequenznummern funktionieren.
Meine Idee wäre ein binärer Baums, in dem Intervalle einsortiert sind.
Man kann in log2(n) das Intervall [0; topval] finden und ausgeben, wenn
man eine neue Sequenznummer hat sucht die insert-Fkt das passende
Intervall und ergänzt die Nummer, falls diese Nummer eine Lücke zwischen
zwei Intervallen schließt werden die beiden verbunden und der Baum
entsprechend angepasst.
Meine Frage: Gibts so eine Datenstruktur schon? Die Aufgabenstellung ist
ja denke ich nicht so ungewöhnlich, ich darf aber keine Sequenznummern
verschmeißen und das ganze soll dann in einen Embedded-Prozessor
implementiert werden, muss also schnell und speicheffizient laufen.
Danke und lg
Matthias
Tip, vergiss es.
Speichere dir eine Liste, z.B. 64 Einträge mit Sequenznummern sowie
Folgelisten (semi-statisch alloziert) mit 8bit Differenzen, Null ist ein
Terminator. Semi-Statisch im Sinne, daß du dir z.B. bei 32bit einen
32byte
block allozierst , 4byte für den next Pointer wobei 5bits als Flag
genutzt werden können, sowie 28 Einträge. Diese Nummern sind nur
Beispiele.
In der Head-Liste der Sequenznummern kannst du dir noch zwei Zähler
machen,
min, max damit du dich Arbeit erleichtest wegen zusammenführen und
Intervalle.
"Vergiss es" klingt irgendwie so hoffnungslos ... g.
Ich fürchte ich hab das nicht ganz verstanden, wieso 28 Einträge, ich
muss ja immer nur Anfang und Ende einer Sequenz wissen. Eine simple
Implementierung wäre ja auch eine einfach verkettete Liste mit head
Intervall [0 : topval], und daran anschließend weitere Einträge mit
nachfolgenden Intervallen. Mit einer neuen Zahl wird da einfach drüber
gegangen und die Zahl an das erste passende Intervall angehängt. Dann
prüft man das nächste, wenn die Zahl dort an den Anfang dranpasst werden
die beiden Intervalle verbunden. Wenn man jetzt noch die Komplexität des
Suchens von O(n) runterbringen könnte, wäre das Problem imho gelöst.
Bzgl der CPU handelt es sich um eine NIOS-Softcore CPU, derzeit noch
etwas beschränkt aber wenn wir es brauchen basteln wir halt noch einen
DDR2 dran und das Ding hat bei 200 MHz Takt auch nicht viel andere
Aufgaben, also das kann schon einiges, es ist halt kein Desktop-PC mit
Gigabyte RAM sondern eher 64-128 MByte.
lg
Matthias
Matthias schrieb:> ich suche nach einem Algorithmus für folgendes Problem: Ich muss eine> Liste von Sequenznummern führen
Wie lang wird denn die Liste sein?
MfG Klaus
Matthias schrieb
> Ich fürchte ich hab das nicht ganz verstanden, wieso 28 Einträge, ich> muss ja immer nur Anfang und Ende einer Sequenz wissen. Eine simple> Implementierung wäre ja auch eine einfach verkettete Liste mit head> Intervall [0 : topval], und daran anschließend weitere Einträge mit> nachfolgenden Intervallen. Mit einer neuen Zahl wird da einfach drüber> gegangen und die Zahl an das erste passende Intervall angehängt. Dann> prüft man das nächste, wenn die Zahl dort an den Anfang dranpasst werden> die beiden Intervalle verbunden. Wenn man jetzt noch die Komplexität des> Suchens von O(n) runterbringen könnte, wäre das Problem imho gelöst.
Klingt doch schon mal nicht schlecht.
Erinnert mich an eine 1-Dimensionale Boolsche Operation auf Strecken,
die ich mal gebraucht habe.
Die Frage ist: Wie zersplittert die Nummern sind, bzw. wieviele Bereiche
du erwartest. Damit dir ein Binärer Baum im Laufe der Zeit nicht zu
einer Liste degeneriert, musst du beim Zusammenführen von Abschnitten
den Baum neu balanzieren. Und das kann aufwändig sein. O(n) ist für
kleine n nicht immer automatisch die schlechteste Wahl. Denn wenn die in
der O-Notation unberücksichtigten Konstanten O( a * ln2(n) + b ) nur
ungünstig genug sind, kannst du das mit einem O(n) für kleine n
schlagen bzw. zumindest Paroli bieten. Ganz abgesehen davon, dass
O(ln2(n)) auch nur dann gilt, wenn der Baum balanziert ist.
Vergiss es meinte ich mit binary tree usw. Der Speicheraufwand (Pointer)
ist einfach zu groß.
28 Einträge deshalb, war nur eine Hausnummer, weil z.B. 32 byte Speicher
alloziert werden, da hat man dann bei 32bit einen Pointer für den
nächsten Speicher inkl 5 Flags sowie 28 Diff Werte. Ev. könntest du dir
auch ein
Byte für die Anzahl der belegten Variablen reservieren, um dann das
Array
direkt anzusprechen, bringt einen kleinen Geschwindigkeitsvorteil.
Wenn du dann für 28 Werte 32bit brauchst ist das effizienter als wenn du
eine linked list nimmst mit 12 bytes die dann jeweils alloziert werden
für
je einen Eintrag. Bei 20 Einträgen wären es dann schon über 240 byte.
Auch die 32 bytes sollten in einem Pool alloziert werden als 4k/8k oder
sonstwas um den Speicherverbrauch niedrig zu halten und dann mittels
linked list in einer freien Speicherliste gehalten werden.
Wie zersplittert die Sequenzen in der Zukunft sein werden kann ich noch
schwer abschätzen, es kommen dann eben mehrere Gegenstellen zum Einsatz
die im schlimmsten Fall selber regelmäßige Sprünge in den Sequenzen
haben. Im bestehenden System ist es ziemlich einfach, da kommen Sprünge
nur vor wenn Werte bei der Übertragung verloren gehen, das sollte
relativ selten passieren, zb alle 30s bei voller Auslastung und der
fehlende Wert wird binnen einiger 100 ms wieder neu geschickt -->
meistens wird die Liste nur einen Eintrag haben, mehr als 3 oder 4 kann
eigentlich nur bei Defekten vorkommen.
Ich werd das wohl mal so implementieren und noch weiter begrübeln, das
Hauptanliegen meiner Frage war ja, dass ich nicht das Rad neu erfinde,
wenn es hier schon eine Standardlösung gibt.
Danke und lg
Matthias
Das will bei mir etwas nicht so recht zusammen passen:
Matthias schrieb:> Meine Idee wäre ein binärer Baums ...Matthias schrieb:> meistens wird die Liste nur einen Eintrag haben, mehr als 3 oder 4 kann> eigentlich nur bei Defekten vorkommen.
MfG Klaus
Ich bin inzwischen eh bei der Liste. Der Baum würde wohl zu viel fürs
Rebalancieren kosten. Aber in Wahrheit weiß ich das noch nicht, ich
werde mit dem System Messungen machen, mit realistischen und Worst-Case
Daten, dann weiß ich mehr.
lg
Matthias
