Hallo alle, komme nicht auf einen sinnvollen Ansatz die nachfolgende Anforderung zu implementieren (STM32 oder NRF52). 1) Es steht nur ein Timer, kann auch Systick sein, zur Verfügung. 2) Es existiert eine Liste von Kommandos (Ausgabe per UART) die zu unterschiedlichen Intervallen ausgegeben werden sollen. Beide Infos stehen in einem Array, welches unterschiedlich lang sein kann. zb [1,10ms, "Mache a"] [2,30ms, "Mache b"] [3,20ms, "Mache c"] usw. Wie implementiert man sowas am besten in C. Ich brauche jetzt kein Code, sondern einen Ansatz. Eine Idee die ich habe, scheint aber nicht performant zu sein. Ich könnte das Array um einen zähler erweitern, den ich mit dem Timer inkrementiere. Nach dem inkrementieren vergleiche ich in jedem index des Arrays den Zähler mit dem Sollwert. Aber das scheint mir nicht optimal zu sein. Vielleicht hat hier jemand eine bessere Idee. Vielen Danke und Grüße, Julian
Beitrag #7238164 wurde von einem Moderator gelöscht.
Julian schrieb: > . Ich könnte das Array um einen zähler erweitern, den ich mit dem Timer > inkrementiere. Das ist der sogenannte SysTicker. > Nach dem inkrementieren vergleiche ich in jedem index des Arrays den > Zähler mit dem Sollwert. Das ist als erste Implementierung OK. Bei den meisten bleibt es auch so. Je nach Aufgabe gibt es später leichte Anpassungen. Bis hin zur Anordnung der Timer in einer Liste nach Fälligkeit. Aber das besuchst Du vermutlich nie.
Die Frage ist: Ist das Array sortiert und ist jeder Zeitpunkt nur einmal drin? Wenn ja, brauchst Du immer nur eine Stelle auszuwerten. Und wenn "mache a" eine abzählbare Anzahl an Operationen ist, geht das mit einem enum ganz gut. Wenn nicht, kann das beliebig kompliziert werden. Dann solltest Du am besten eine Sprache suchen, die Dein Problem am besten beschreibt, und einen Interpreter dafür schreiben.
:
Bearbeitet durch User
Julian schrieb: > Aber das scheint mir nicht optimal zu sein. Mir gefällt die Idee. Man kann es vielleicht sparsamer implementieren, aber so ist der Code gut durchschaubar.
A. S. schrieb: > Je nach Aufgabe gibt es später leichte Anpassungen. Bis hin zur > Anordnung der Timer in einer Liste nach Fälligkeit. Das hört sich interessant an mit der Liste. In dem Moment wo zur Laufzeit ein neues auszuführendes Kommando kommt, muss die Liste neu aufgebaut werden. Walter T. schrieb: > Die Frage ist: Ist das Array sortiert und ist jeder Zeitpunkt nur einmal > drin? Wenn ja, brauchst Du immer nur eine Stelle auszuwerten. Man kann sie ja sortieren. Stefan F. schrieb: > Mir gefällt die Idee. Man kann es vielleicht sparsamer implementieren, > aber so ist der Code gut durchschaubar. Es muss alles in eine Interrupt Routine passen und fertig werden bevor diese wieder befeuert wird, hier wären es alle 1ms
Julian schrieb: > Es muss alles in eine Interrupt Routine passen Wieso das? Solche Aktionen macht man normalerweise aus der main-loop heraus. Interrupthandler sollten nicht arbeiten, sondern lediglich Ereignisse zur Kenntnis nehmen und I/O Puffer Übertragen falls die Hardware das nicht per DMA kann.
Stefan F. schrieb: > Julian schrieb: >> Es muss alles in eine Interrupt Routine passen > > Wieso das? Solche Aktionen macht man normalerweise aus der main-loop > heraus. Interrupthandler sollten nicht arbeiten, sondern lediglich > Ereignisse zur Kenntnis nehmen und I/O Puffer Übertragen falls die > Hardware das nicht per DMA kann. So ähnlich meinte ich es ja. Die Abarbeitung muss fertig werden, bevor der Interrupthandler den status für die Abarbeitung in der main loop setzt. Eventuell lasse ich nur Intervalle >10ms zu, oder ich baue eine Liste auf, die A.S. beschrieb und arbeite diese einfach nur ab, weiß gerade nur nicht wie ich diese Liste ab besten ausbauen sollte, da diese unendlich lang, also im Ring, laufen müsste. [1,10ms, "Mache a"] [2,30ms, "Mache b"] [3,20ms, "Mache c"] ++++++++++++++++++++++++++++++++++++++++++++++++++ (1ms inkrement) 1 3;1 2;1 1;3 (auszulösende Kommandos)
Programmiere das lieber so, dass verpasste Zeitpunkte ggf. nachträglich abgearbeitet werden. Manchmal zu spät kommen ist weniger schlimm, als manchmal gar nicht kommen.
Stichwort RTOS. Stefan F. schrieb: > Manchmal zu spät kommen ist weniger schlimm, als > manchmal gar nicht kommen. Du Ferkel :)
Walter T. schrieb: > Du willst jetzt aber nicht einen Scheduler neu erfinden? Ich kann nicht für den TO sprechen, aber ICH würde es nicht wollen. Nach meinem Verständnis verteilt ein Scheduler die Arbeit zur LAUFZEIT; ich würde das -- soweit möglich -- zur Compilezeit machen, und so hatte ich die Absicht des TO auch verstanden.
Mbed-os Ticker class angucken. Es gibt einen 1 MHz Timer und der Compare Int wird immer auf das nächste anstehende Ereignis gesetzt.
Walter T. schrieb: > Du willst jetzt aber nicht einen Scheduler neu erfinden? Beitrag "Wartezeiten effektiv (Scheduler)"
Grummler schrieb: > Nach meinem Verständnis verteilt ein Scheduler die Arbeit > zur LAUFZEIT; ich würde das -- soweit möglich -- zur > Compilezeit machen, und so hatte ich die Absicht des TO > auch verstanden. Ne, leider muss es zur Laufzeit geschehen, da die Liste der Tasks erst ind er Laufzeit aufgebaut werden können
Peter D. schrieb: > Walter T. schrieb: >> Du willst jetzt aber nicht einen Scheduler neu erfinden? > > Beitrag "Wartezeiten effektiv (Scheduler)" Das geht in die richtige Richtung, danke! Fast hätte ich etwas neu erfunden :-)
Julian schrieb: > komme nicht auf einen sinnvollen Ansatz die nachfolgende Anforderung zu > implementieren... Zu allererst brauchst du eine Uhr, um zu wissen, was es grad für eine Uhrzeit ist. Die kann relativ beliebig fein ticken, aber für die meisten Fälle braucht es nur Intervalle zu 1 ms oder 10 ms. Wenn du nur Text per UART ausgeben willst, dann reichen Intervalle zu 10 ms allemal. So, die Textausgabe und die zeitliche Erinnerung daran, selbige zu senden (oder etwas anderes zu tun), sind zwei völlig verschiedene Dinge, also trenne sie auch voneinander. Und die Zeichenausgabe muß ja nun auch nicht auf die Mikrosekunde genau erfolgen, also kann man sowas auch mal ein paar Millisekunden später tun, Hauptsache ist, daß sich sowas nicht aufsummiert. Kommen wir also nun zur Uhr und dem, was sie außer dem Zählen der Uhrzeit noch tun müßte: nämlich müßte sie eine Liste von Botschaften und ihrer Zeitintervalle und ihrer nächsten Zeitpunkte führen. Also sowas etwa: struct Listenelement begin Botschaft; // 0=nix, alles andere=ne gültige Botschaft Intervall; NächsterZeitpunkt; end; Jaja, je mehr derartige Dinge da drin stehen sollen, desto länger wird auch die Bearbeitungszeit. Der Uhrtick (also die ISR des Timerticks o.ä.) müßte dann folgendes tun: for jedes Element seiner Liste do begin ist die Botschaft gültig? wenn ja then do begin ist NächsterZeitpunkt <= aktuelle Uhrzeit ? wenn ja then do begin NächsterZeitpunkt = NächsterZeitpunkt + Intervall; Werfe Botschaft in eine Ereignisliste; end end end; So etwa könnte das aussehen. Irgendwoanders in der Firmware muß dann die o.g. Ereignisliste angeschaut werden und wenn da was drinsteht, sollte es ausgeführt bzw. darauf reagiert werden. Eigentlich ist das alles keine komplizierte Sache und logisch recht geradlinig. Du hättest also schon längst selber drauf kommen können. Man muß lediglich am Anfang mit Denken anfangen und nicht am Ende mit irgendwelchen Zeichenketten, die gesendet werden sollen. Ist wie beim Autofahren: zuerst das Ziel auswählen und dann erst losfahren. W.S.
W.S. schrieb: > Eigentlich ist das alles keine komplizierte Sache und logisch recht > geradlinig. Du hättest also schon längst selber drauf kommen können. Man > muß lediglich am Anfang mit Denken anfangen Sind wir heute wieder im Arschloch Modus? Der TO hat bereits mit dem Denken angefangen und eine von mehreren Ideen genannt. Dazu wollte er unsere Meinung lesen, nicht zu der Frage ob er sein Gehirn benutzt.
W.S. schrieb: > Jaja, je mehr derartige Dinge da drin stehen sollen, desto länger wird > auch die Bearbeitungszeit. Das ist eben der Hauptunterschied zu einem Scheduler mit sortierter Liste. Da muß nur einen einzige Variable getestet werden, ob sie schon abgelaufen ist. Erst dann werden die Callbacks ausgeführt und die Zeit bis zum nächsten Ereignis geladen. Die CPU-Last des Schedulers ist also weitgehend unabhängig von der Anzahl der aktiven Einträge in der Liste. Die CPU-Last der Callbacks wird natürlich durch ihre Aufrufhäufigkeit bestimmt.
:
Bearbeitet durch User
Peter D. schrieb: > Das ist eben der Hauptunterschied zu einem Scheduler mit sortierter > Liste. Einen Tod muss man sterben. Wenn ich maximal 10 Einträge in der Liste erwarte, verschwende ich keine Zeit mit Sortieren. Bei 1000 Einträgen würde ich hingegen nicht auf die Sortierung verzichten.
Peter D. schrieb: > Das ist eben der Hauptunterschied zu einem Scheduler mit sortierter > Liste. > Da muß nur einen einzige Variable getestet werden,... Dafür ist bei der Einrichtung ein Sortieraufwand notwendig und es kommt damit eine zeitliche Beziehung zwischen verschiedenen Ereignissen ins Spiel. Ersatzeshalber kann man dann bei jedem Ereignis neu sortieren, aber das ist nicht weniger aufwendig als das, was ich vorgeschlagen habe. W.S.
Wahrscheinlich würde ich zuerst einmal zusehen, das die UART einen für mehrere Telegramme ausreichenden FIFO bekommt. Oder ist das Umkopieren/Schreiben der Telegramminhalte in einen FIFO direkt im Interrupt oder per "AsyncDelay (siehe oben W.S.)" in Relation zur typischen UART-Geschwindigkeit hier so kritisch?
Euro schrieb: > Wahrscheinlich würde ich zuerst einmal zusehen, das die UART einen für > mehrere Telegramme ausreichenden FIFO bekommt. Also, du mußt dir erstmal darüber klar werden, daß über eine Serielle die Daten nicht schneller drübergehen, als sie drüber gehen. Man würde die Übertragung und den gesamten Ablauf in der Firmware verstopfen, wenn man mehr Daten senden will, als über den seriellen Kanal tatsächlich drübergehen können. Ein Fifo im zugehörigen Treiber dient nur zur Entkopplung der aufrufenden Funktion von der dann zeitlich folgenden interruptgesteuerten Übertragung der Daten. Zeitlich umgekehrt dasselbe in der Empfangsrichtung. Also damit der µC zwischenzeitlich sich um was Anderes kümmern kann. Ähnlich verhält es sich mit Events, Botschaften oder wie man das nennen will in einer Warteschlange. Sowas wird irgendwo in der Firmware erzeugt und an ganz anderer Stelle und zu einer anderen Zeit (also NICHT zwingend sofort) zur Kenntnis genommen und irgendwie drauf reagiert (oder auch nicht, je nach sonstigen Umständen). Begreife mal, daß es sinnvoll ist, nicht alle Dinge in der Firmware in einen Topf zu werfen, sondern sie stattdessen so gut es geht voneinander zu separieren. Also Treiber für I/O schreiben, die die Datenströme puffern, ohne daß man sich außerhalb des Treibers darum kümmern müßte. Oder eben das 'Stellen' und 'Klingeln-Lassen' des Weckers davon zu trennen, was nach dem Aufstehen getan werden soll. Euro schrieb: > Oder ist das Umkopieren/Schreiben der Telegramminhalte in einen FIFO > direkt im Interrupt... Eben nicht so. Das wäre das Werfen der Dinge in einen großen Topf und umrühren. Dem Timerinterrupt ist - und SOLL! - es egal sein, ob nach 15 Millisekunden nun ein Text gesendet werden soll oder das Licht ausgemacht werden soll. Er soll nur nach 15 Millisekunden es klingeln lassen bzw. eine Botschaft an andere Firmwareteile erzeugen. W.S.
W.S. schrieb: > Dafür ist bei der Einrichtung ein Sortieraufwand notwendig Ich sehe da keinen großen Aufwand, da das Sortieren nur einmal erfolgt und nicht bei jedem Timertick nötig ist. Auch enthält das Sortieren keine komplizierten Berechnungen, nur Vergleiche und Subtraktionen.
Warum gibt es bei der Standard-Aufgabe "Scheduler" eigentlich immer eine ellenlange Diskussion? Es ist ja nicht so, als gäbe es zu diesem Thema nicht massig Lesestoff.
W.S. schrieb: > Also, du mußt dir erstmal darüber klar werden, daß über eine Serielle > die Daten nicht schneller drübergehen, als sie drüber gehen. Ach ehrlich? W.S. schrieb: > Eben nicht so. Warum nicht? Es ist eigentlich völlig wumpe, ob Du die typischen 20..50µs zum Befüllen des FIFOs im low level timer Interrupt oder in der main verballerst. Schwierig wirds in der main, wenn Du nebenher noch den Turm von Brahma umstapeln möchtest. Das dauert in der Regel bei Turmhöhe > 20 schon mal etwas. :)
Peter D. schrieb: > Ich sehe da keinen großen Aufwand, da das Sortieren nur einmal erfolgt > und nicht bei jedem Timertick nötig ist. Auch enthält das Sortieren > keine komplizierten Berechnungen, nur Vergleiche und Subtraktionen. Die Liste muss auch nicht komplett sortiert werden, es reicht, wenn immer der am nächsten fällige Task am Anfang steht. ==> Datenstruktur "priority_queue". https://en.cppreference.com/w/cpp/container/priority_queue https://de.wikipedia.org/wiki/Vorrangwarteschlange und schon wird aus dem bösen O(n log n) ein freundliches O(log n)...
Εrnst B. schrieb: > Die Liste muss auch nicht komplett sortiert werden, es reicht, wenn > immer der am nächsten fällige Task am Anfang steht. Es wird nicht die Liste sortiert, sondern die Elemente zeigen immer sortiert nach aufsteigender Zeit aufeinander. Wenn ich eine Task einfüge, gehe ich die Liste der aktiven Tasks entlang, bis eine nicht früher ablaufende Task oder das Endekennzeichen gefunden sind. An dieser Stelle wird die neue Task eingereiht. Εrnst B. schrieb: > und schon wird aus dem bösen O(n log n) ein freundliches O(log n)... Wo siehst Du dabei ein (n log n) oder (log n)?
Peter D. schrieb: > Wo siehst Du dabei ein (n log n) oder (log n)? Ok, es geht immer noch schlechter... Dein Algo wäre O(n²) "n" mal Task einfügen, und für jeden "n" Vergleiche, um die Einfügestelle zu finden. Wenn du nur einen einzelnen "Einfüge"-Vorgang betrachtest, ist dein O(n) immer noch eine ganze Kategorie schlechter als das O(log n) einer simplen Heap-basierten priority_queue.
Walter T. schrieb: > Warum gibt es bei der Standard-Aufgabe "Scheduler" eigentlich > immer eine ellenlange Diskussion? Warum gibt es hier über alles ellenlange Diskussionen? Könnte das eventuell damit zusammenhängen, dass es sich hierbei um ein Diskussionsforum handelt?
Εrnst B. schrieb: > Ok, es geht immer noch schlechter... Dein Algo wäre O(n²) > "n" mal Task einfügen, und für jeden "n" Vergleiche, um die > Einfügestelle zu finden. Nö, der erste Eintrag in eine nicht aktive Liste erfolgt sofort, d.h. selbst im Worst Case max 1+2+3... Abgesehen davon ist die Anzahl der Vergleiche nicht der Flaschenhals beim Scheduler. Jede Task, die eingefügt wurde, soll ja auch irgendwann mal laufen.
Peter D. schrieb: > Abgesehen davon ist die Anzahl der Vergleiche nicht der Flaschenhals > beim Scheduler. Jede Task, die eingefügt wurde, soll ja auch irgendwann > mal laufen. Das steht außer Frage. Trotzdem kann man eine für diesen Anwendungsfall besser geeignete Datenstruktur wählen. Nur weil eine Schraube auch mit dem Hammer in die Wand geht, darf man trotzdem besseres Werkzeug verwenden. Peter D. schrieb: > im Worst Case max 1+2+3 genau das ist es, was zu O(n²) führt...
:
Bearbeitet durch User
Grummler schrieb: > Warum gibt es hier über alles ellenlange Diskussionen? > > Könnte das eventuell damit zusammenhängen, dass es sich > hierbei um ein Diskussionsforum handelt? Ähem, nö, das ist es nicht. Dieses Forum ist zwar ein Diskussionsforum, aber die Beiträge, wo tatsächlich diskutiert - also mit sachlichen Argumenten ein gemeinsames Ziel zu erreichen versucht wird - kann man mit der Lupe suchen. Bei den meisten Beiträgen wird nur gegackert wie auf dem Hühnerhof und Argumente werden nicht zur Kenntnis genommen. Jetzt könnte man sagen (oder zumindest insgeheim meinen), dieses Forum sei ein Hühnerhof-Gacker-Forum, aber da würden sich wieder welche aufregen, weil sie Tatsachen als Beleidigungen empfinden. Fazit: wie man's macht, ist es verkehrt. Also nicht aufregen. W.S.
Euro schrieb: > W.S. schrieb: >> Also, du mußt dir erstmal darüber klar werden, daß über eine Serielle >> die Daten nicht schneller drübergehen, als sie drüber gehen. > Ach ehrlich? > > W.S. schrieb: >> Eben nicht so. > Warum nicht? Es ist eigentlich völlig wumpe, ob Du die typischen > 20..50µs zum Befüllen des FIFOs im low level timer Interrupt oder in der > main verballerst. Wieder so ein Gegacker ohne nachzudenken. Es ist eben nicht egal, ob man in einer ISR wartet, bis der Fifo zum Senden wieder ausreichend geleert ist, oder ob man so etwas tunlichst aus einer ISR heraushält. Es ist auch nicht egal, ob man Abläufe verschiedener Schichten in einer Firmware zusammenkippt oder lieber auseinanderhält. Das Warum hatte ich ja schon geschrieben, also lies es ruhig noch einmal und versuche diesmal, es zu vestehen. W.S.
Εrnst B. schrieb: > Trotzdem kann man eine für diesen Anwendungsfall besser geeignete > Datenstruktur wählen. Ich benutze den Scheduler in fast allen Projekten. Er ist eine sehr bequeme und effiziente Methode, um Wartezeiten an die Mainloop abzugeben. Man muß sich nicht mehr um jede einzelne Task kümmern, die warten soll. Man muß nur festlegen, wieviel Tasks maximal gleichzeitig warten können. Man legt also einfach etwas Reserve fest und kann dann bei der Entwicklung weitere Tasks hinzufügen. Die Idee mit der verketteten Liste ist aber nicht von mir. Ich hab ein älteres Projekt weiter pflegen müssen, da war er drin. Ich hab ihn dann nur noch etwas für kleine 8-Bitter (8051) optimiert. Ich finde die Lösung schon sehr elegant und universell.
Εrnst B. schrieb: > genau das ist es, was zu O(n²) führt... Ich weiß nicht, wo da das n² herkommen soll. Wenn z.B. 10 Tasks gerade aktiv sind und ich will eine 11. hinzufügen, dann sind dafür max 10 Vergleiche bzw. im Mittel 5 nötig.
Peter D. schrieb: > Ich weiß nicht, wo da das n² herkommen soll Ich bin mir jetzt ehrlich nicht sicher, auf welchem Level ich das Erklären anfangen soll... Ist es die "O"-Notation generell? Sieh's so: Der Binary-Heap macht es genauso wie dein Code, nur muss er beim Hinzufügen vom 11. Task nicht maximal 10 Einträge vergleichen, sondern nur log₂(10). Einfach nur weil die Einträge sinnvoller angeordnet sind. Es ist also kein "Über den Haufen werfen" von deinem Konzept, sondern eine Verfeinerung. Und nachdem es simpel zu implementieren ist (Wenn man die Idee hinter der Datenstruktur verstanden hat), gibt es eigentlich kaum einen Grund, darauf zu Verzichten, selbst wenn der eigentliche Vorteil vielleicht erst bei 100 oder 1000 Tasks deutlich sichtbar wird...
Εrnst B. schrieb: > Sieh's so: Der Binary-Heap macht es genauso wie dein Code, nur muss er > beim Hinzufügen vom 11. Task nicht maximal 10 Einträge vergleichen, > sondern nur log₂(10). > Einfach nur weil die Einträge sinnvoller angeordnet sind. > Es ist also kein "Über den Haufen werfen" von deinem Konzept, sondern > eine Verfeinerung. -> "Binäre Suche" ... Sonst dauert das hier ja noch ewig. ;)
W.S. schrieb: > Es ist eben nicht egal, ob man in einer ISR wartet, bis der Fifo zum > Senden wieder ausreichend geleert ist, oder ob man so etwas tunlichst > aus einer ISR heraushält. Wer wartet denn in einer ISR? Wenn ich das Telegramm aufgrund eines FIFO-Full nicht senden kann, wird es erst im nächsten Timer-Zyklus in den FIFO geschrieben. Im Ergebnis kein Unterschied: Wenn Dein 10-Byte-Telegramm nicht mehr in den 20-Byte-Fifo passt, ist damit die UART für den nächsten 1ms-Zyklus bei 115kBaud ausgelastet. Es bringt also auch keinen Performancegewinn, x mal innerhalb der nächsten ms in der main den FIFO zu befragen, ob denn nun endlich das Telegramm geschrieben werden kann. Naja, wenn man in der main sonst nix Besseres zu tun hat, ist es wohl auch eher eine philosophische Frage, ob dieses Overpolling eine gedankenlose Verschwendung von Ressourcen ist (oder ob man da nicht doch lieber den Turm von Brahma umstapelt).
Εrnst B. schrieb: > Peter D. schrieb: >> Ich weiß nicht, wo da das n² herkommen soll > > Ich bin mir jetzt ehrlich nicht sicher, auf welchem > Level ich das Erklären anfangen soll... Vielleicht erstmal selber nachdenken. Die Zeitkomplexität bezieht sich in der Regel auf ALGORITHMEN , das sind "Vorschriften, die mit endlich vielen Schritten zum Ergebnis" führen. Numerische Simulationen sind ein typisches Beispiel dafür: Das Programm ist fertig, wenn alle Berechnungen erledigt sind. Steuerungsanwendungen sind (als Ganzes!) aber keine Algorithmen, denn sie terminieren nicht dann und dadurch, dass ein "Ergebnis" "berechnet" wurde. Eine Steuerung muss solange aktiv sein, wie es der reale Prozess erfordert, der durch die Steuerung gesteuert wird. Infolgedessen verliert der Begriff des "Gesamtaufwandes" seinen Sinn -- man kann die Steuerung trotzdem nicht früher abschalten, auch wenn der Prozessor schon lange fertig ist mit Rechnen. Für jeden Einzelschritt gelten natürlich Zeitgrenzen; das ist ein anderes Thema, und das hat Peter ja auch so formuliert. > Und nachdem es simpel zu implementieren ist (Wenn man > die Idee hinter der Datenstruktur verstanden hat), gibt > es eigentlich kaum einen Grund, darauf zu Verzichten, > selbst wenn der eigentliche Vorteil vielleicht erst > bei 100 oder 1000 Tasks deutlich sichtbar wird... Doch, kann es geben: KISS bzw. YAGNI.
Εrnst B. schrieb: > Sieh's so: Der Binary-Heap macht es genauso wie dein Code, nur muss er > beim Hinzufügen vom 11. Task nicht maximal 10 Einträge vergleichen, > sondern nur log₂(10). Das hast Du also gemeint. Das ist hier nicht anwendbar, da eben nicht wirklich sortiert wird, sondern die aktiven Einträge nur neu verkettet werden. Man kann also nicht die Mitte auswählen, weil diese nicht bekannt ist. Εrnst B. schrieb: > Und nachdem es simpel zu implementieren ist (Wenn man die Idee hinter > der Datenstruktur verstanden hat), gibt es eigentlich kaum einen Grund, > darauf zu Verzichten, selbst wenn der eigentliche Vorteil vielleicht > erst bei 100 oder 1000 Tasks deutlich sichtbar wird... Eine binäre Suche dürfte deutlich komplexer ausfallen. Man müßte entweder wirklich umsortieren oder zusätzliche Listen der aktiven und der freien Indexe pflegen. Es müssen also schon sehr viele Tasks gleichzeitig aktiv sein, damit sich der hohe Aufwand rechnet. Die Liste hat bei meinen MC-Projekten oft nur 10-20 Einträge. In einem Projekt hat sie 30 Einträge für das automatische Senden von Monitorwerten. Man kann dann Werte im Fokus häufiger senden lassen und nur zu überwachende seltener.
:
Bearbeitet durch User
Grummler schrieb: > Vielleicht erstmal selber nachdenken. Vielleicht erstmal selber lesen. Grummler schrieb: > Die Zeitkomplexität bezieht sich in der Regel auf > ALGORITHMEN Genau darum ging es. Datenstruktur für "Irgendwas" (Hier: Tasks), Element mit niedrigster Prio (Hier: "Due"-Zeitstempel) finden, und mit geänderter Prio (Hier: Zeitstempel+Interval) wieder einreihen. Also beim Binary Heap/priority_queue eben die Algorithmen hinter den top() pop() push()-Operationen. Oder eben Elementzugriff array[0] (Ohh! schwieriger Algorithmus) und ein "make_heap" danach. Grummler schrieb: > Doch, kann es geben: KISS Wenn dein kisS-Prinzip Informatik-Erstsemester Algorithmen ausschließt, Sachen die knapp oberhalb vom Bubblesort-Urschleim liegen, muss das letzte "S" schon arg großgeschrieben sein. Und hey: Wenn dir die paar Zeilen for-Schleife zu komplex sind: in der STL gibt's fix und fertige Implementationen als Template. Die darfst du sogar anwenden wenn du die Algorithmen dahinter nicht verstehst. YAGNI kann es nicht sein, denn es ist ja schon klar, dass Tasks in der richtigen Reihenfolge ausgeführt werden sollen.
Peter D. schrieb: > Eine binäre Suche dürfte deutlich komplexer ausfallen. Man kann den Baum einfach auf ein Array mappen (hat dann aber eine fixe Maximallänge) Knoten n hat Tochterknoten 2n+1 und 2n+2, Knoten n hat Mutterknoten (n-1)/2 d.H. keine "Verpointerung" nötig, Indexberechnungen sind rein Bitshifts und Additionen. Aktuell anliegender Task ist array[0]. dem kann man nach dem Ausführen einfach seinen fällig-Zeitstempel hochstellen, und dann den Baum hochwandern lassen, bis er an einer passenden Stelle liegt. "MinHeapify(0)". Diese Funktion wird zwar üblicherweise rekursiv definiert, es ist aber eine Tail-Rekursion, der Compiler wird da eine simple Schleife draus machen.
Εrnst B. schrieb: > Man kann den Baum einfach auf ein Array mappen (hat dann aber eine fixe > Maximallänge) > Knoten n hat Tochterknoten 2n+1 und 2n+2, > Knoten n hat Mutterknoten (n-1)/2 > ... Also ich verstehe da nur Bahnhof. Hast Du mal eine Beispielimplementation, die ich nachvollziehen könnte, die also plain C und nicht C++ mit irgendwelchen super duper komplexen Templates ist? Der Quelltext mit dem Scheduler, den ich damals geerbt hatte, machte den Eindruck, daß der Programmierer sehr erfahren war und die gesamte Herangehensweise an das Projekt hat mir gut gefallen. Wenn da mit binärer Suche was zu verbessern gewesen wäre, hätte er es bestimmt gemacht. Entwickelt hatte er das Programm zum Großteil unter Unix auf ner Sun und erst später durch den Keil C51 gejagt.
Hier ist es in Farbe und bunt: https://trstringer.com/complete-binary-tree/ Was ich allerdings noch nicht verstanden habe ist, wann es einen Geschwindigkeitsvorteil gegenüber Bisektionsverfahren auf einem sortierten Array hat. Vielleicht, wenn die Daten auf einem Band ohne wahlfreien Zugriff gespeichert sind?
:
Bearbeitet durch User
Walter T. schrieb: > Hier ist es in Farbe und bunt: > > https://trstringer.com/complete-binary-tree/ Ja gut, das ist nur die Adressierungslogik. Die Frage ist aber, wie hilft mir das beim Einsortieren einer Zeit, daß immer die kürzeste als erstes ausgeführt wird? Es ist schwer, aus solchen Bildchen einen konkreten Code zu erstellen. Die binäre Suche sieht doch erheblich aufwendiger aus, als das lineare Einsortieren.
Naja, alles, was in Big-O-Größenordnungen toll ist, ist bei Zahlen in der Größenordnung von Fingern und Zehen aufwendiger als das Naheliegende.
Peter D. schrieb: > Also ich verstehe da nur Bahnhof. > Hast Du mal eine Beispielimplementation, die ich nachvollziehen könnte, > die also plain C und nicht C++ mit irgendwelchen super duper komplexen > Templates ist? Viel Magie steckt da nicht drinnen. Wichtigste Funktion ist die hier:
1 | #define LEFT(i) ((i)*2+1)
|
2 | #define RIGHT(i) ((i)*2+2)
|
3 | #define PARENT(i) ((i-1)/2)
|
4 | // An Knoten "i" die Heap-Bedingung herstellen
|
5 | // Laufzeit O(log n)
|
6 | void heapify(int i) { |
7 | // Wir suchen unter diesem und direkten Kindern den kleinsten Knoten
|
8 | int kleinster=i; |
9 | int left=LEFT(i); |
10 | int right=RIGHT(i); |
11 | if (left < taskcount && tasks[left].due < tasks[kleinster].due) |
12 | kleinster=left; |
13 | if (right < taskcount && tasks[right].due < tasks[kleinster].due) |
14 | kleinster=right; |
15 | if (kleinster == i) return; // Passt schon |
16 | // Ansonsten tauschen, kleinsten Knoten Richtung Wurzel wandern lassen.
|
17 | swap(i, kleinster); |
18 | // Tail-rekursion
|
19 | heapify(kleinster); |
20 | }
|
und die sucht einfach nur den kleinsten von drei Werten, tauscht falls nötig den Kleinsten nach unten, und macht dasselbe dann rekursiv an dem Knoten, der gerade getauscht wurde. Aus der Rekursion macht der GCC ein einfaches "JMP". Kompilierbarer Rest zum damit Spielen im Anhang, hoffentlich ausreichend kommentiert.
Walter T. schrieb: > ist bei Zahlen in > der Größenordnung von Fingern und Zehen aufwendiger als das > Naheliegende. ja, bei nur einer Handvoll Tasks lohnt weder das eine noch das andere, da packt man einfach per copy&paste sooft wie nötig sowas in den Code:
1 | void loop() { |
2 | |
3 | static uint32_t lastrun_TaskX=0; |
4 | if (millis() - lastrun_TaskX >= periode_TaskX) { |
5 | lastrun_TaskX=millis(); |
6 | taskX(); |
7 | }
|
8 | ...
|
9 | |
10 | }
|
Εrnst B. schrieb: > Aktuell anliegender Task ist array[0]. > dem kann man nach dem Ausführen einfach seinen fällig-Zeitstempel > hochstellen, und dann den Baum hochwandern lassen, bis er an einer > passenden Stelle liegt. Eben, der Baum muß neu sortiert werden. Der Binärbaum gilt ja nur für den einen Moment. Beim Einfügen oder Ausführen eines Eintrags müßte man ihn doch wieder umstellen. Das Hoch- bzw. Runterwandern könnte auf größeren MCs per DMA erfolgen. Das könnte bei großen Arrays leicht etwas bringen. Der Charme der verketteten Liste ist ja, daß ich beim Einfügen nur den Vorgänger korrigieren muß bzw. bei Ausführung nur den ersten Eintrag als frei markieren muß.
Εrnst B. schrieb: > ja, bei nur einer Handvoll Tasks lohnt weder das eine noch das andere, > da packt man einfach per copy&paste sooft wie nötig sowas in den Code: Beachten muß man aber, daß in größeren Statemaschines an vielen Stellen gewartet werden könnte, aber nur an wenigen gleichzeitig. Hat man z.B. 100 mögliche Stellen im Ablauf, wovon nur 10 aktiv warten, lohnt sich ein Scheduler durchaus.
Εrnst B. schrieb: > Kompilierbarer Rest zum damit Spielen im Anhang Danke, muß ich mir erstmal ansehen.
Peter D. schrieb: > Eben, der Baum muß neu sortiert werden. Nicht der Baum, sondern nur ein Pfad von der Wurzel Richtung Blätter wird sortiert. Also nur log₂(n), nicht n. Und der auch nicht die ganze Strecke, sobald eine passende Position erreicht ist, wird (wie bei der Suche in der verketteten Liste) abgebrochen. Peter D. schrieb: > Beim Einfügen als letztes Array-Element anhängen, den Pfad Blatt->Wurzel hochblubbern lassen. Also wieder nur ein Pfad, der angeschaut werden muss. > oder > Ausführen eines Eintrags müßte man ihn doch wieder umstellen. wieder nur ein Pfad, den der Eintrag hochlaufen muss. Peter D. schrieb: > Das Hoch- bzw. Runterwandern könnte auf größeren MCs per DMA erfolgen Da seh ich den Sinn von DMA nicht. Evtl. bei der "swap"-Operation zum memcopy-beschleunigen. Aber: Sobald die einzelnen Task-Structs so groß werden, dass man da über memcopy+DMA nachdenkt, dann kann man auch ein Array mit pointern verwenden.
Walter T. schrieb: > https://trstringer.com/complete-binary-tree/ > > Was ich allerdings noch nicht verstanden habe ist, wann es > einen Geschwindigkeitsvorteil gegenüber Bisektionsverfahren > auf einem sortierten Array hat. Beim reinen Suchen hat es keinen Vorteil -- wohl aber beim Einfügen. Um in ein sortiertes Array (unter Erhalt der Ordnung) ein Element einzufügen, muss man im Mittel n/2 Elemente verschieben -- beim Heap sind es nur log(n) Stück. Bei n=10 lohnt das noch nicht wirklich...
Εrnst B. schrieb: > Grummler schrieb: >> Vielleicht erstmal selber nachdenken. > > Vielleicht erstmal selber lesen. Habe ich. Dort stand etwas von "O(n^2)", was nicht stimmt bzw. praktisch nicht relevant ist. O(n) versus O(log(n)) ist korrekt, aber für N=10 gleitet der Streit ins Lächerliche ab... > Grummler schrieb: >> Doch, kann es geben: KISS > > Wenn dein kisS-Prinzip Informatik-Erstsemester > Algorithmen ausschließt, Sachen die knapp oberhalb > vom Bubblesort-Urschleim liegen, Ahh. Und weil das so ist, schrieb Peter: "Ich verstehe nur Bahnnof". Alles klar...
Grummler schrieb: > Habe ich. > > Dort stand etwas von "O(n^2)", was nicht stimmt bzw. > praktisch nicht relevant ist. Das O(n²) bezog sich auf die Implementation mit der Liste, die sortiert aufgebaut wird indem nacheinander n Elemente eingefügt werden, und jedes Element sucht beim Einfügen mit O(n) seinen Platz. Εrnst B. schrieb: > "n" mal Task einfügen, und für jeden "n" Vergleiche, um die > Einfügestelle zu finden. Ja, das wäre mit "zuerst unsortiert sammeln", und dann einmal mit O(n log n) sortieren auch erledigt. So hat das Peter aber nicht beschrieben. Überhaupt: Was ist so schlimm daran, neue und erprobte Algorithmen und Datenstrukturen kennenzulernen? Wenn man sie kennt, kann man entscheiden, ob und wann man sie sinnvoll einsetzen kann. Wenn man sie nicht kennt, hat man diese Möglichkeit nicht. Tut es irgendwie weh, Neues zu lernen?
Peter D. schrieb: > Eben, der Baum muß neu sortiert werden. Nee -- er ist ja gar nicht KOMPLETT sortiert. Es wird nur gerade so das absolute Minimum an Ordnung gewährleistet -- und das ist, dass die Wurzel jedes (!) Teilbaumes kleiner ist als alle anderen Elemente dieses Teilbaumes. Ein Vergleich "benachbarter" Teilbäume findet nicht statt -- ist auch nicht notwendig. > Der Binärbaum gilt ja nur für den einen Moment. Ja... naja, jein. > Beim Einfügen oder Ausführen eines Eintrags müßte man > ihn doch wieder umstellen. Immer nur einen kleinen Teil davon. Man muss immer nur einen Pfad von der Wurzel zu einem Blatt reparieren, und auch das nicht immer komplett. > Der Charme der verketteten Liste ist ja, daß ich beim > Einfügen nur den Vorgänger korrigieren muß bzw. bei > Ausführung nur den ersten Eintrag als frei markieren muß. Naja, bei 10 Elementen lohnt sich ein Heap m.E. noch nicht. Bei 100 Stück sieht das schon anders aus...
Εrnst B. schrieb: > Grummler schrieb: >> Habe ich. >> >> Dort stand etwas von "O(n^2)", was nicht stimmt bzw. >> praktisch nicht relevant ist. > > Das O(n²) bezog sich auf die Implementation mit der Liste, > die sortiert aufgebaut wird indem nacheinander n Elemente > eingefügt werden, und jedes Element sucht beim Einfügen > mit O(n) seinen Platz. Ich weiss. Genau das meinte ich mit "praktisch nicht relevant". Die Zahl der Tasks mag erst zur Laufzeit feststehen oder sich sogar von Zeit zu Zeit ändern -- aber dass permanent die komplette Liste gelöscht und neu wieder aufgebaut werden muss, halte ich doch für ziemlich exotisch. Wenn DAS ein relevantes Problem wäre, hätte Peter das sicher erwähnt... > Überhaupt: Was ist so schlimm daran, neue und erprobte > Algorithmen und Datenstrukturen kennenzulernen? Der Zeitpunkt ist entscheidend. Und die technisch bessere Lösung ist keineswegs immer die für die jeweilige Aufgabe sinnvollere Entscheidung...
Wobei der TO an keiner Stelle erwähnt hat, dass nicht eine einfache statische Planung ausreicht.
Εrnst B. schrieb: > Das O(n²) bezog sich auf die Implementation mit der Liste, die sortiert > aufgebaut wird indem nacheinander n Elemente eingefügt werden, und jedes > Element sucht beim Einfügen mit O(n) seinen Platz. Nein, ein neues Element sucht nur über die bereits eingefügten. Das 1. nimmt sich einen freien Platz (alle sind frei), das 2. vergleicht mit dem 1. usw. Also 0+1+2+3+...+(n-1).
:
Bearbeitet durch User
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.