Welche Möglichkeiten für C-Algorithmen gibt es, um sich einem Wert anzunähern?

Computer: Software & Programmierung C/C++
#1

Hallo zusammen

Ich stehe vor folgendem Problem: Client A schickt Client B eine Anfrage für ein oder mehrere Datenpakete. Dafür gibt es jedoch eine Zeitbegrenzung. Das heisst kommt innerhalb von z.B. 3s kein Paket zurück, wird die Anfrage verworfen und eine neue gesendet. Ich möche nun einen Algorithmus in C entwickeln, der diese Zeitbegrenzung optimal wählt. Das heisst wenn innerhalb von 3s ein Paket zurück kommt, wird diese Zeitbegrenzung verringert für das nächste Paket. Der Fall, dass diese Zeitbegrenzung zu klein gesetzt wird, sollte möglichst wenig eintreffen, da sonst der Durchsatz darunter leidet.Ich weiss dass dies keine spezifische C-Frage ist, aber ich wäre sehr dankbar über einige Ideen von euch.

#2

vielleicht ist ja da was dabei
http://de.wikipedia.org/wiki/Kategorie:open_mouth:ptimierungsa…

#3

Hallo Fragewurm,

Mit der Programmiersprache hat das zunächst einmal gar nichts zu tun :wink:

Vernünftig wird es sein mit einem Zeitfenster zu arbeiten.
Die Datenpakete werden nicht immer mit der genau gleichen Verzögerung eintreffen, sondern da gibt es eine gewisse Bandbreite. Es macht keinen Sinn bei jedem Datenpaket die Zeit neu zu berechnen.

Wenn die Datenpakete vor deinem Zeitfenster eintreffen, kannst du das Fenster nach vorne schieben, wenn sie nach dem Fenster eintreffen musst du das Fenster halt nach hinten schieben.

Also entwirf deinen Algorithmus in Pseudocode, als Flussdiagramm, als Nassi-Shneiderman, als Zustandsdiagramm oder einem anderen Werkzeug deiner Zuneigung.

Die Umsetzung in eine bestimmte Programmiersprache ist dann der nächste Schritt.

MfG Peter(TOO)

#4

Hallo Peter
Danke für deine/eure Antworten. Also du meinst man sollte die Pakete als „Blöcke“ auswerten? das heisst wenn z.b. von 10 Paketen jedes innerhalb von 500ms angekommen ist, dann kann man die 500ms verkleiner? oder was genau meinst du mit Fenster nach vorne/hinten schieben?

Lg Hefler

#5

Hallo Hefler,

Also du meinst man sollte die Pakete als „Blöcke“ auswerten?

Nein.

das heisst wenn z.b. von 10
Paketen jedes innerhalb von 500ms angekommen ist, dann kann
man die 500ms verkleiner? oder was genau meinst du mit Fenster
nach vorne/hinten schieben?

Du fängst mit den 3s anforderungsabstand an und machst ein Zeitfenster von 2.5-3.0s
Kommen die Pakete innerhalb des Fensters an, veränderst du nichts.
Kommen die Pakete vor den 2.5s an, stellst du das Fenster auf 2.2-2…7s ein und setzte die Zeit von 3s auf 2.5s.
usw.

Zeitangaben sind willkürlich gewählt, die hängen von deinem System ab.

Es gibt auch noch x andere Möglichkeiten. Aber deine Vorgaben beschreiben das System nur recht unzulänglich.

MfG Peter(TOO)

#6

OT: Entwurf
Hallo Peter,

Also entwirf deinen Algorithmus in Pseudocode, als
Flussdiagramm, als Nassi-Shneiderman, als Zustandsdiagramm
oder einem anderen Werkzeug deiner Zuneigung.

Dein Rat ist hier sicher richtig und allgemein anerkannt. Ich frage mich nur mittlerweile, ob für C-Experten unter Pseudocode nicht u.a. auch compilierbaren C-Code subsumieren sollte (ohne linkbarkeit oder konkrete Verarbeitung). Der Syntax ist eindeutig, Compiler oder Lint finden Schreibfehler und grobe Schnitzer, eine erste I/O ist mit printf und co schnell realisiert.

Allgemein gilt es als Smell, direkt „loszuprogrammieren“, und mir ist klar, dass ein unerfahrener Programmierer damit überfordert wäre und sich schnell verrennt.

Für einen erfahrenen Programmierer hingegen wäre ein Analogon eine Sekretärin, die einen Brief erst in Notepad grob skizzieren soll, bevor sie ihn mit Word „setzt“.

Auch fällt es uns Entwicklern hier manchmal wesentlich einfacher, echten abstrakten C-Code nachzuvollziehen als graphische Diagramme über mehrere Seiten.

Wie ordnest Du Deine Gedanken hauptsächlich vor der Implementierung, wenn nicht gerade mit Papier und Bleistift (was ich als eine wichtige Stufe davor ansehe)? Pseudoce, UML, State Flows, compilierbarer Code …?

Gruß
achim

#7

Hallo Achim,

Wie ordnest Du Deine Gedanken hauptsächlich vor der
Implementierung, wenn nicht gerade mit Papier und Bleistift
(was ich als eine wichtige Stufe davor ansehe)? Pseudoce, UML,
State Flows, compilierbarer Code …?

Das ist sehr unterschiedlich bei mir.

Ich bin, seit bald 40 Jahren, hauptsächlich im Bereich Micro-Controller unterwegs.

Ausgangspunkt: Erstmalige Inbetriebnahme der Hardware.

Da ich die Hardware auch selbst entwickle ist vieles an Software schon im Kopf vorhanden und da programmiere ich direkt drauf los. Fängt dann mit einer Mischung aus Low-Level-Funktionen und Testprogrammen an.
Es weiss dann noch Keiner ob die Hardware auch wirklich so tut wie sie soll. Meist sind da auch neue, unbekannte Peripheriebausteine dabei, welche wiederum ihre eigenen Handbücher haben.

Dann kommt’s drauf an, was als Automat ausgeführt wird zeichne ich dann als State Flow, wenn’s komplizierter ist. Wobei ich auch gerne Übertragungsprotokolle als Automat implementiere.
Automaten lassen sich recht gut direkt in Interrupts packen, da die Laufzeiten pro Aufruf meist recht kurz sind und mit dem letzten Interrupt dann meist ein grosser Teil der Dekodierung schon erledigt ist.

Für den Rest kommt es drauf an, je nach Lust und Laune, bzw. so wie man das Problem gerade im Kopf angeht, dass ist dann meist Pseudocode oder eine Flow Chart.

Vor so 30 Jahren habe ich längere Zeit mit den X-Tools gearbeitet, das war eine Nassi-Shneiderman-Editor, welcher direkt Code erzeugen konnte. Das Teil hatte aber auch so seine Tücken. z.B. erzeugte es Code mit vielen goto.

MfG Peter(TOO)

1 Like
#8

Hallo Peter,

vielen Dank für Deine Erfahrung, kommt mir sehr bekannt vor :wink:. Auch embedded, die ersten 15 Jahre eher HW und Treiber, seit ein paar Jahren eine über 20 Jahre gewachsene Steuerungs-Applikation von fast 1 Mio Zeilen.

Die Herausforderungen beider Bereiche sind m.E. sehr verschieden.
Auf der HAL-Seite ist ein tiefes Verständnis der HW, der Programmierumgebung (Compiler, Linker, Einbindung in IDE) und hunderte von Pattern verschiedenster Aufgaben (serielle Treiber, race conditions, RTOS -Architektur, IO-Behandlung, …). Also in der Regel komplizierte Realisierung von Modulen überschaubarer Komplexität (ein Printf z.B. ist auf wenigen Seiten fast vollständig beschreibbar, es gibt kaum „nichtlinearität“, es gibt nur einen sehr begrenzten „Kontext“, wengleich die Implementierung sehr aufwendig ist. Ein noch krasserers Beispiel wäre z.B. sin().

Auf der anderen Seite, bei einer Applikation mit Tausenden von I/O, Zuständen oder Ablaufwegen und der Vernetzung über den globalen Kontext (der realen HW und der Welt dahinter) ist ein tiefes Verständnis der Programmiersprache meist eher zweitrangig, das Fachvokabular sind die Funktionen oder Variablen (Token) und die Produktivität/Verlässlichkeit hängt m.E. eher davon ab, wie gut die Fachsprache (Architektur und Token des Sourcecodes) der Problembeschreibung gerecht wird.

Die Grundlegende Annahme „aller“ Manager und nicht-Softwerker ist dagegen, dass die Problembeschreibung nicht im Sourcecode erfolgen kann oder darf. Am Beispiel sin() ist das für jeden offensichtlich und wird dann auf komplexe, nichtlineare Applikationen extrapoliert.

Meine jüngste Erfahrung ist nun, dass Problembeschreibung bei komplexen autarken Steuerungs-Applikationen mit hoher Nichtlinearität kaum effektiver oder verständlicher erfolgen kann als in einer Programmiersprache, effektive Token und Architektur mal vorausgesetzt. Das also entsprechende Repräsentationen in UML, Word oder sonstwo einzelne Teilaspekte stark vereinfacht veranschaulichen können, für die tiefere umfassende Betrachtung aber meist von relativ geringem Wert sind und praktisch immer parallel und manuell erstellt und gepflegt sein müssen, meist noch getrennt nach Zielgruppe (Manager, Kunde, Prüfer, Kollegen, Zulasser).

Meines Erachtens entspricht (high-level) Quellcode dem Schaltplan einer HW. Niemand käme hier auf die Idee, die dort gezeichneten Verbindungen, Designatoren und Werte nochmal getrennt in Word oder sonstie zu beschreiben.

Bis auf einige Beiträge von Les Hatton finde ich wenig theoretische Überlegungen zur Entwicklung der „Fachsprache“ einer Applikation, zumindest im Vergleich zu den zahlreichen „Snake-Oil“ Versprechungen der UML & Co Anbieter.

Hast Du Dich mal intensiver mit der Architektur großer Projekt beschäftigt oder kennst dazu hilfreiche Literatur?

Gruß
achim

#9

Hallo Achim,

vielen Dank für Deine Erfahrung, kommt mir sehr bekannt vor
:wink:. Auch embedded, die ersten 15 Jahre eher HW und Treiber,
seit ein paar Jahren eine über 20 Jahre gewachsene
Steuerungs-Applikation von fast 1 Mio Zeilen.

Mein grösstes Teil hat nur um die 100’000 Code-Zeilen, auch über Jahre gewachsen, auf PC und 2 Controller verteilt, dafür jede Zeile selber geschrieben :wink:

Die Grundlegende Annahme „aller“ Manager und nicht-Softwerker
ist dagegen, dass die Problembeschreibung nicht im Sourcecode
erfolgen kann oder darf. Am Beispiel sin() ist das für jeden
offensichtlich und wird dann auf komplexe, nichtlineare
Applikationen extrapoliert.

Bei mir steht auch immer einiges im Code!
Ist einfach praktischer, wenn man etwas ädern muss und sich dazu nicht erst durch 10 Ordner suchen muss.

Meine jüngste Erfahrung ist nun, dass Problembeschreibung bei
komplexen autarken Steuerungs-Applikationen mit hoher
Nichtlinearität kaum effektiver oder verständlicher erfolgen
kann als in einer Programmiersprache, effektive Token und
Architektur mal vorausgesetzt.

Die Namensgebung ist ein wichtiger Aspekt. Ich habe auch oft Projekte übernommen, welche nicht wirklich funktioniert haben.
Es gibt nichts unübersichtlicheres als eine globale Variable temp, welche dann Resultate durch das halbe Programm verteilt :frowning:
Ich musste da oft erst mal einiges umbenennen um die Übersicht zu bekommen, war ja alles immer ohne Dokumentation.

Als ich 1976 angefangen habe, gab es noch die engen Limiten der Sprachen.
BASIC lies nur einen Buchstaben und optional eine Ziffer für Variablen zu, Funktionsnamen gab es gar nicht, nur Zeilennummern.
Assembler waren noch auf 5 oder 8 Zeichen für Bezeichner beschränkt.
Da musste man kryptische Bezeichner verwenden :frowning:

Das also entsprechende
Repräsentationen in UML, Word oder sonstwo einzelne
Teilaspekte stark vereinfacht veranschaulichen können, für die
tiefere umfassende Betrachtung aber meist von relativ geringem
Wert sind und praktisch immer parallel und manuell erstellt
und gepflegt sein müssen, meist noch getrennt nach Zielgruppe
(Manager, Kunde, Prüfer, Kollegen, Zulasser).

Das werden immer unterschiedliche Dokumentationen, für die unterschiedlichen Zielgruppen bleiben. Das ergibt sich schon daraus, dass diese Gruppen unterschiedliche Ausbildungen haben.
Wobei die Manager meistens am wenigsten verstehen und einfach bunte Bildchen mögen :wink:

Meines Erachtens entspricht (high-level) Quellcode dem
Schaltplan einer HW. Niemand käme hier auf die Idee, die dort
gezeichneten Verbindungen, Designatoren und Werte nochmal
getrennt in Word oder sonstie zu beschreiben.

Also ich habe für Kunden viele Funktionsbeschreibungen der Hardware gemacht. Es ist für Servicetechniker nicht immer gleich klar, was man da als Entwickler für Tricks in die Hardware eingebaut hat, bzw. wie jetzt welche Schaltzustände sich gegenseitig beeinflussen.

Hast Du Dich mal intensiver mit der Architektur großer Projekt
beschäftigt oder kennst dazu hilfreiche Literatur?

Leider nein.
Ich bin ja eigentlich mehr Autodidakt. Meine Ausbildung habe ich als Elektroniker genossen und 1976 wurde ich einfach ins Wasser gestossen und musste so schwimmen lernen. Meine erste Aufgabe war Testprogramme auf einem KIM-1 für eine Prozessorplatine und den Adapter zu erstellen. Assemblieren musste ich alles von Hand und dann als Hex eintippen…
Als nächstes habe ich mir dann auf einem Wang 2200 in BASIC einen Crossassembler geschrieben.
Irgendwie war man damals dann schon ein Softwarespezialist :wink:

MfG Peter(TOO)

1 Like
#10

Hi,

mit der Programmiersprache C/C++ hat es wirklich nichts zu tun. Nur beachte bitte, dass du auch immer eine algorithmische Verzögerung hast bei solchen Herausforderungen. Wenn du dich „endlos“ mit den Anlegen von Statistiken beschäftigst, dann wird das einen Einfluss haben, den du selbst beeinflusst. Da du ja sonst keinen Einfluss hast auf die Netzwerklatenz (evtl. noch auf die Serialisierungsverzögerung) ist es nicht lösbares Problem.
Du musst hier eine Festlegung treffen. Und zwar musst du dich entscheiden welches Verhalten eine „Bevorrangung“ erhalten soll.

a. Das Finden einer optimalen Schranke oder
b. Das Vermeiden des Unterschreitens einer Schranke

Ich tendiere zu (b.). Deine optimale Latenz ist immer genau die Antwortzeit die du vom Partner bekommst. Es gibt ja auch keinen triftigen Grund warum das Netzwerk schneller werden sollte. Es sei denn du hast Einflussmöglichkeiten!