Hallo Mikrocontroller Forum :),
ich schreibe gerade eine Bibliothek um mehrere Infrarot-Distanzsensoren
in Betrieb zu nehmen.
Der Mikrocontroller ist ein Arduino Mega 2560 (atmega2560).
Die Sensoren geben ein Analogsignal aus, der Ausgang ist allerdings
nicht linear.
Dazu unterscheiden sich alle Sensoren. Daher habe ich nun zu jedem
Sensor eine eigene Kennlinie aufgenommen, die ich jetzt in der
Bibliothek in Form von Funktionen darstellen möchte.
Die Formeln leite ich mit der Trendlinie in Excel her (Excel wurde hier
verwendet, da es schnell gehen muss ;) ).
Bei der Generierung der Trendlinie kann ich zwischen verschiedenen
Verfahren wählen (Anhang Trendlinie.png)
Die Formeln stimmen und berechnen kann der Arduino diese auch alle.
Soweit so gut, jetzt zur eigentlichen Frage.
Wieviel Laufzeit beanspruchen die einzelnen Berechnungen? Welche
Berechnung ist z.B. besonders langsam?
Ich erinnere mich aus einem Informatikmodul aus dem Studium noch diffus
an die O-Notation. Nach dieser gilt ja für die Aufwenigkeit von
Algorithmen:
1 < log n < sqrt(n) < n < n(log n)^2 < n^2 < n^a < a^n
(http://www.tilman.de/uni/ws03/alp/o-notation.php)
Kann ich das so auf die tatsächlichen Funktionen übertragen? Ist also
die Berechnung von log(x) einfacher und damit schneller als z.B. x^2 und
wäre es damit sinnvoller die Kennlinie über eine logarithmische Funktion
als über ein Polynom z.B. 2. oder 3. Ordnung anzunähern?
Im Anhang Sensoren.PNG könnt ihr eine Beispielhafte Annäherung sehen.
Ich bedanke mich jetzt schon einmal für eure Mühe diesen Text zu lesen
und für die Antworten :)
Beste Grüße,
Timo
Hallo,
die Laufzeit hängt teils stark von der Implementierung ab. Ein Polynom
vom Grad n als a0 + a1*x + ... + an*x^n einfach eingegeben benötigt
beispielsweise n^2 Rechenoperationen. Verwendet man dagegen das
Horner-Schema kommt man mit n Rechenoperationen aus. Zudem dauert auf
einem AVR eine Gleitkommaoperation deutlich länger, als eine Festkomma.
Wenn du Laufzeitbedenken hast, würde ich eine sehr einfache und flexible
Möglichkeit wählen. So wird beispielsweise bei dem Steuerungssystem
EPICS "einfach" eine Datentabelle mit den Messpunkten gespeichert und
dazwischen interpoliert.
Gruß Kai
Wenn du den AVR nicht mit langer Rechnerei quälen willst:
Der Verlauf aus deinem ersten Bild schaut so aus, als ob man den mit
einer handvoll Stützstellen und linearem Interpolieren sehr exakt
"nachzeichnen" könnte.
Hallo,
wenns schnell gehen soll halte dich von höheren Funktionen fern, die
Rechenzeit hängt auch stark von den konkreten Zahlen ab und man kann den
Worst case nicht wirklich berechnen.
Ich verwende generell ein Näherungspolynom, das ich für den
Anwendungsfall - Kennlinie, benötigter Bereich - jeweils speziell
berechnen und optimieren lasse, einschliesschlich der Fehlerverteilung
über den gewünschten Bereich (Kontrollrechnung). Sind die Fehler zu
gross, kann man es mit einem Grad mehr versuchen, andernfalls kann man
auch den Grad des Polynoms reduzieren. Kann durchaus sein, dass man dann
feststellt, dass eine lineare Interpolation zwischen Stützstellen
ausreicht, aber das muss man verifizieren.
Dadurch komme ich mit Addition, Subtraktion, Multiplikation aus,
Divisionen lassen sich fast immer vermeiden, das ist schon mal sehr
positiv für die Rechenzeit. Man rechnet also mm in inch nicht mit
Division durch 25,4, sondern mutlipliziert mit dem Kehrwert, das geht
viel schneller.
Georg
Ganz vielen Dank für eure Rückmeldungen,
ich habe die verrschiedenen Verfahren einmal implementiert und darüber
jeweils die im ersten Anhang blau dargestellte Kennlinie angenähert.
Die Kennlinie wird jeweils über die Werte 1 bis 300 berechnet. Darüber
wird die Laufzeit mit der micros()-Funktion gemessen und ausgegeben. Der
Wert der Kennlinie ist bei x = 300 als Ergebnis 8. Die jeweiligen
Näherungen schaffen das mehr oder weniger gut :P.
Die Ausgabe der Laufzeiten habe ich euch mal mit angehängt. Wie schon
erwähnt wurde, desto höher die Ordnung desto länger dauert das ganze.
Das erwähnte Horner Schema bringt da doch eine deutliche Verbesserung.
So ein Lookup Table, wie ihr es beschreibt wollte ich gerne vermeiden,
aber dass das die schnellste Variante wäre, damit habt ihr sicherlich
recht.
Es geht mir hier um die schnellste Funktion, die einen einen weiten
Bereich der Kennlinie darstellen kann.
Testweise werde ich aber auch nochmal ein interpoliertes Lookup Table
implementieren um ein Gefühl dafür zu bekommen wieviel Zeit ich hier
aufgrund von "Programmierfaulheit" verschwende :D. Es sind wie gesagt
einige Sensoren.
Eine Frage hätte ich dann nochmal zu dem was oben gesagt wurde. Dass es
keinen direkten Zusammenhang zwischen der O-Notation und beispielsweise
des Grades eines Polynoms gibt. Das verstehe ich noch nicht ganz.
Bei der von mir verlinkten Seite
(http://www.tilman.de/uni/ws03/alp/o-notation.php) steht unter dem Punkt
"Anwendung":
bei Addition: Es zählt der Summand mit dem stärkeren Wachstum (bei n²
gilt z.B. O(n²)
bei Multiplikation: Es zählt die Summe der Exponenten (n² * 3n ⇒ Θ(n³)
Timo schrieb:> Eine Frage hätte ich dann nochmal zu dem was oben gesagt wurde. Dass es> keinen direkten Zusammenhang zwischen der O-Notation und beispielsweise> des Grades eines Polynoms gibt. Das verstehe ich noch nicht ganz.
Zitat aus Wipedia:
"Landau-Symbole werden in der Mathematik und in der Informatik
verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu
beschreiben."
Sie werden u.a. auch dazu verwendet, die Laufzeit von Algorithmen in
Abhängigkeit der Anzahl der Eingabeelemente zu charakterisieren. So ist
bspw. die Laufzeit für die Sortierung von n Zahlen mit dem Heapsort-
Algorithmus in O(n · log n).
Die Laufzeit für die Berechnung einer Funktion wie exp(x), log(x) oder
x**3 + 5*x - 2 in Abhängigkeit von x erfolgt in weitgehend konstanter
(auf jeden Fall aber nach oben beschränkter) Zeit, sofern man nicht mit
Arbitrary-Precision-Arithmetik rechnet. Somit liegen diese Laufzeiten
alle on O(1).
Man könnte aber bspw. auch die Laufzeit für die Berechnung eines
Polynoms n-ten Grades in Abhängigkeit von n betrachten. Wird das Polynom
auf die ungeschickte Weise berechnet, indem jeder Summand a_k*x**k als k
Multiplikationen programmiert wird, ist die Laufzeit in O(n²). Mit dem
Horner-Schema lässt sich der Aufwand auf O(n) reduzieren.
Man muss hier aber klar unterscheiden zwischen
- der Funktion f, die als Approximation der Sensorkennlinie berechnet
werden soll und
- der Funktion g, die die Laufzeit der Berechnung der Funktion f in
Abhängigkeit von ihrem Funktionsargument, dem Grad des Polynoms (oder
was auch immer) beschreibt.
I.Allg. ist g von f verschieden, weswegen der Rechenaufwand für die
Berechnung von f(x) nicht mit einfach mit O(f(x)) abgeschätzt werden
kann.
Timo schrieb:> ich schreibe gerade eine Bibliothek um mehrere Infrarot-Distanzsensoren> in Betrieb zu nehmen.
Was sind denn das für Sensoren? Wenn das die beliebten Sharp-Sensoren
sind, würde ich mir die Mühe nicht machen. Das sind bessere Schätzeisen.
Das kann man sich auch leicht vorstellen: da wird eine Triangulation
über einen Meter und mehr mit einer Basisbreite im Bereich weniger mm
gemacht.
MfG Klaus
Die o-notation is zum Abschaetzen eines Aufwandes fuer eine grossen
Menge von Operationen bezueglich eines Algorithmusses. zB wie skaliert
die diagonalisierung einer 10'000er Matrix.
Und enthaelt keine Aussage fuer einzelne Operationen eines
kleinskaligen Problemes.
Danke nochmal für die Hinweise zur O-Notation. So setzt sich die falsche
Idee die ich hatte auf jeden Fall nicht in meinem Kopf fest.
Klaus schrieb:> Was sind denn das für Sensoren? Wenn das die beliebten Sharp-Sensoren> sind, würde ich mir die Mühe nicht machen. Das sind bessere Schätzeisen.> Das kann man sich auch leicht vorstellen: da wird eine Triangulation> über einen Meter und mehr mit einer Basisbreite im Bereich weniger mm> gemacht.>> MfG Klaus
Um genau die geht es. Man kann hier tatsächlich von Schätzeisen sprechen
was die Toleranzen bei deren Produktion angeht. Jeder Sensor weist eine
andere Kennlinie auf, auch wenn es das gleiche Modell ist.
Ich verwende Sensoren für die Bereich (4-30 cm) und (10-80 cm).
Die Kennlinien habe ich für jeden Sensor einzeln aufgenommen und nun wo
ich die Sensoren unter Verwendung dieser spezifischen Kennlinien abfrage
liefern sie auch gute Ergebnisse.
"Out of the box" geht mit diesen Sensoren jedoch gar nichts. Da ist
Schätzeisen schon wirklich die beste Umschreibung.
Das Verfahren mit Lookup Tables habe ich inzwischen auch noch
implementiert (Anhang) und die Zeit über einem Aufruf gemessen. Sehr
weit liegen Die Implementierungen zeitlich nicht auseinander.
Schöne Grüße,
Timo
Dazu musste ich feststellen, dass über Excel (oh Wunder :P) gefittete
Funktionen nicht ganz das gelbe vom Ei sind.
Das ganze mit dem Curve-Fitting-Tool in MATLAB liefert da deutlich
angenehmere und brauchbarere Ergebnisse.
Hier ist noch eine andere Funktion, die die Kennlinie der Sharp-Sensoren
ganz gut approximiert:
Beitrag "Re: Sensorkennlinie"
Ein paar Erläuterungen dazu:
Beitrag "Re: Sensorkennlinie"
Die Funktion benötigt zwar nur drei Rechenoperationen, allerdings ist
eine davon eine Division, die vermutlich recht lange dauert. Bevor du
die Koeffizienten der Funktion an deine konkreten Sensoren anpasst,
kannst du ja mal nur den Rechenzeitbedarf messen und dann entscheiden,
ob sich eine weitere Verfolgung des Ansatzes lohnt.
Da die Rechenoperationen einfach und die Wertebereiche nicht sehr groß
sind, könnte man überlegen, das Ganze mit Integer-Arithmetik zu rechnen.
Die Addition und Subtraktion könnten mit 8 Bit, die Division mit
16-Bit-Dividend, 8-Bit-Divisor und 8-Bit-Ergebnis gerechnet werden, was
eigentlich recht schnell sein sollte. Leider unterstützt der GCC keine
Division mit 8-Bit, sondern nur mit 16-Bit-Divisor.
Hi, entschuldigt die verzögerte Rückmeldung.
Den dort vorgeschlagenen Ansatz werde ich mir auf jeden Fall auch noch
einmal ansehen.
Die aktuelle Lösung funktioniert erstmal jedoch sehr gut und ich muss
gerade andere Schwerpunkte setzen :).
Werde an dieser Stelle dann aber noch einmal etwas dazu schreiben sobald
ich das angetestet habe um das Thema hier abzuschließen :).
Schöne Grüße,
Timo
Sensoren.PNG
(23 KB)
trendlinie.PNG
(44 KB)
