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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.