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
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.
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.
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.
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.
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_queuehttps://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...
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.
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?
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.
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
voidheapify(inti){
7
// Wir suchen unter diesem und direkten Kindern den kleinsten Knoten
// 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:
Ε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.
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...
Ε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).
