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
Angehängte Dateien:
-
Sensoren.PNG
23 KB -
trendlinie.PNG
44 KB
Aeh... kann man alles im Simulator ausprobieren, und ergibt ein brauchbares Gefuehl fuer spater.
Timo schrieb: > 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? Nein. Das eine hat mit dem anderen absolut nichts zu tun.
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
Angehängte Dateien:
-
Laufzeiten.PNG
14 KB
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.
:
Bearbeitet durch Moderator
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.
Angehängte Dateien:
-
Lookup_Table.PNG
1,6 KB
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
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.