Hallo zusammen,
ich habe hier ein kleines Problem.
Und zwar nehme ich mit meinem AVR eine (Frequenz-)Messung vor.
Das Ergebnis soll der AVR auch direkt verarbeiten und dann einen nicht
linear vom Messwert abhängigen Wert auf einem Display ausspucken.
Ich würde also eine Lookup-Tabelle zum Einsatz bringen um die
Rechenarbeit der nicht linearen Funktion zu umschiffen.
Jetz ist aber das Problem, dass meine Einträge in der Lookup-Tabelle
(dank dem Zusammenhang: t~1/f; Periodendauer ist proportional zu
1/Frequenz) ebenfalls nicht linear verteilt sind.
Hier mal ein Ausschnitt aus der Tabelle:
1
Messwert Ausgabewert
2
18750 30
3
9375 29
4
6250 28
5
4688 27
6
3750 25
7
3125 20
8
2679 15
9
2344 12
10
2083 11
11
1875 10
12
1705 9
13
1563 9
14
1442 9
15
...
Da die Tabelle im EEPROM abgelegt werden soll ist ein durchsuchen der
16-bit Werte vom Anfang der Tabelle bis zum gesuchten Wert natürlich
nicht gerade effizent.
Ich bräuchte also irgend eine Eingebung wie ich von meinem Messwert zum
richtigen Tabelleneintrag finde. Soweit ich gelesen habe ist das genau
die Aufgabe einer Hashfunktion, doch leider stelle ich mich gerade etwas
sau doof an und finde irgendwie keine gelungene Lösung um von Messwert x
zur "Tabellenzeile" y zu kommen.
Will mir also vielleicht jemand einen kleinen Tip geben wie ich das nun
bewerkstelligen kann?
Ich steh hier grad voll auf dem Schlauch und Bücher, I-Net etc. gibt so
allgemeine Antworten, die ich zwar verstehe, aber gerade nicht umsetzen
kann...
Vielen Dank
MfG
Johannes
Johannes R. schrieb:> 16-bit Werte vom Anfang der Tabelle bis zum gesuchten Wert natürlich> nicht gerade effizent.
Behauptet wer? Das ganze ist in O(1) (Konstante Zeit, Konstanter Platz)
lösbar einen besseren Algorithmus gibt es nicht. Wenn du einen Suchbaum
im Eprom aufbaust hast du sogar in ln(256) = 8 Schritten die Lösung, bei
2 Takten "Zeit" pro Lesevorgang und vielleicht noch 8 Takten für
Vergleich, Sprung und Increment bist dun in 80 Takten fertig, ich glaube
nicht das man das schlagen kann. (bei einer Tabellengröße von 256
Einträgen)
Johannes R. schrieb:> sau doof an und finde irgendwie keine gelungene Lösung um von Messwert x> zur "Tabellenzeile" y zu kommen.
Deine "Hashfunktion" ist 1/x und du hast somit nix gewonnen...
Johannes R. schrieb:> dank dem Zusammenhang: t~1/f; Periodendauer ist proportional zu> 1/Frequenz
Du misst die Periodendauer und die willst du dann in die Frequenz
umrechnen?
Oder andersrum?
Wenn du die "1" über dem Bruchstrich durch eine viel größere Zahl
ausdrückst, bekommst du einfach ein groß skaliertes Ergebnis.
Da empfiehlt es sich, eine Zehnerpotenz zu nehmen.
Bis zu welcher Frequenz soll denn das gehen?
Andere Lösung des Problems wäre Fließkommazahlen zuverwenden. Braucht
aber viel mehr Rechenzeit und braucht einiges an Flash.
minifloat
Da du eben NICHT eine unlineare Funktion rechnen willst,
suche doch einfach binär in der Tabelle.
Die ist ja monoton steigend sortiert, da geht also schnell,
in log 2 der Einträge, bei 1000 Einträgen also 10 Vergleiche.
Ausserdem erlaubt dir deine Tabelle, EXAKT die Rundungsgrenzen
vorzugeben. Das fällt dir bei Formeln sonst schwer.
So lange also deine Tabelle nicht grösser wird als dein Speicher,
ist das effektiv.
hui das ging schnell. Danke
Also mal von hinten: Der AVR ist ein ATMega48 oder 88 mit 10MHz Takt.
Die Tabelle wird sicher nicht größer als mein Speicher (weniger als 80
Einträge), aber bei 16-Bit Werten muss ich ja immer 2 Byte lesen,
zusammenfassen, vergleichen...
bei 80 Einträgen kann die lineare Suche ne ganze Menge Arbeit für den
kleinen AVR werden, der sich sonst auchnoch um einiges kümmern soll.
Die Messfrequenz wird dabei unter 350Hz bleiben, wobei der Prozessor
dabei nicht ausgelastet sein sollte!
gute 60% brauch ich noch für andere Aufgaben.
MaWin schrieb:> Da du eben NICHT eine unlineare Funktion rechnen willst,> suche doch einfach binär in der Tabelle.> Die ist ja monoton steigend sortiert, da geht also schnell,> in log 2 der Einträge, bei 1000 Einträgen also 10 Vergleiche.
?? kannst du das mal genauer erläutern? 1000 Einträge mit 10
Vergleichen?
Joachim K. schrieb:> Du misst die Periodendauer und die willst du dann in die Frequenz> umrechnen?
Ja, so in der Richtung. Die Frequnz ist mir zwar egal, aber sie ergibt
sich ja aus der Periodendauer, die ich messe.
Läubi .. schrieb:> Wenn du einen Suchbaum> im Eprom aufbaust hast du sogar in ln(256) = 8 Schritten die Lösung
Ich weiß zwar nicht wie du auf ln(256) kommst aber die Suchbaum-Idee
ist nicht übel.
Johannes R. schrieb:> ?? kannst du das mal genauer erläutern? 1000 Einträge mit 10> Vergleichen?
Tabelle sortieren.
- auf halbem Weg vergleichen, grösser/kleiner?
- in verbleibender Hälfte ebenfalls auf halben Weg vergleichen
- usw
Aufwand log2(N) also log2(1000)=10 Vergleiche.
Auf AVRs funktioniert das exzellent, auf PCs bei Tabellen von zig MB
aufwärts hingegen ziemlich bescheiden (ein Aspekt, der in älteren
Theoriebüchern u.U. nicht zu finden ist).
256 war einfach ein Schuß ins blaue, genauso wie die 1000 eben ein
Beispiel.
Johannes R. schrieb:> bei 80 Einträgen kann die lineare Suche ne ganze Menge Arbeit für den> kleinen AVR werden, der sich sonst auchnoch um einiges kümmern soll.
Probieren geht über studieren, 80 Einträge sind in einem sortierem Baum
gerade mal 7 Vergleiche im Worst-Case.
1
Lesen vom EEPROM: 4 Takte
2
Vergleich größer/kleiner: 2 Takte
3
Sprung: 3 Takte
4
Reserve: 1 Takt
5
---------------------------------
6
10 Takte
Macht 70 clks maximal + 2 clks zu lesen des eigentlichen Wertes.. machen
wir großzügig 100 Takte draus.
Dein AVR verarbeitet 10.000.000 Befehle die Sekunde, und du musst das
ganze 350x pro Sekunde ausführen bleiben noch 9965000 Takte "für was
anderes" ;)
A. K. schrieb:> Tabelle sortieren.
kein Ding. Sortiert wird sie ja sowieso.
> - auf halbem Weg vergleichen, grösser/kleiner?> - in verbleibender Hälfte ebenfalls auf halben Weg vergleichen
Ist das dann nicht schon das Prinzip des Binärbaums?
Klingt jedenfalls sinnvoll!
Wen man dann noch den Binärbaum so entartet (ich glaube so haben wir das
damals in der Vorlesung genannt wenn er aus dem Gleichgewicht gerät),
dass häufiger auftretende Messwerte näher am Stamm sind, dann gewinnt
man da richtig Zeit.
Ich glaub so wer ichs machen.
1000 Dank!
Ich seid Klasse!!!
Danke Läubi,
Da ich noch nur in C Programmiere (Assembler eigne ich mir bei Zeiten
noch an) kenne ich diese Taktrechnerei nicht wirklich. Ist aber schön
eine Abschätzung zu haben. DANKE!!!
Bei Bedarf: ich habe irgendwo noch Variationen der bsearch()-Funktion
fertig herumliegen, die nicht nach exakt einem Wert suchen, sondern
eine z.B. nach dem übergebenen Suchwert ODER ggf. dem nächstgrößeren,
falls der gesuchte nicht da ist, eine weitere nach dem übergebenen
oder dem nächstkleineren etc..
Johannes R. schrieb:> Ist das dann nicht schon das Prinzip des Binärbaums?
Vom Ablauf her ja, nur wird hier nicht als Baum gespeichert, sondern als
normales Array. Division durch 2 (>>1) ist ja kein Aufwand.
> Wen man dann noch den Binärbaum so entartet
Kann er hier nicht, denn die Daten sind fix.
Kreative Zeitgenossen bauen sich statt dessen einen Codegenerator,
beispielsweise zur Compilezeit indem ein switch-Statement erzeugt wird.
Aus dem macht der C-Compiler dann eine binäre Suche ohne Tabelle, direkt
im erzeugten Code.
Johannes R. schrieb:> dass häufiger auftretende Messwerte näher am Stamm sind,
ne das ist Quatsch dann kannst du nicht mehr Vernünftig suchen!
Das würde nur bei einer linearen Suche etwas bringen.
Klaus Wachtler schrieb:> mfgkw
Was hindert dich daran, das Standard-bsearch() mit einer geeigneten
Vergleichsfunktion zu verwenden?
1
int compare(const void *key, const void *member)
2
{
3
const int *k = key, *m = member;
4
if (*k <= *m)
5
return -1;
6
else if (*k > *(m+1))
7
return 1;
8
else
9
return 0;
10
}
11
12
int translate(int n)
13
{
14
static int data[] = { /* ... */ }
15
int *pos;
16
17
pos = bsearch(&n, data,
18
sizeof(data)/sizeof(data[0])-1, sizeof(int),
19
compare);
20
21
return pos ? *(pos+1) : data[0];
22
}
data sollte mit dem Wert INT_MAX aus limits.h (bzw. einem zum Datentyp
passenden Maximalwert) enden, damit immer irgendein Intervall gefunden
werden kann, wenn der Key grösser als der kleinste Wert im Array ist.
Natürlich kann das auch so umgeschrieben werden, dass immer der
nächstkleinere statt dem nächstgrösseren Wert gefunden wird.
Andreas
Danke für die Codes. Ich werde sie aber so nicht verwenden.
Ich entwickle lieber selbst was. Ersten mach ich dann meine Fehler
selbst und 2. lern ich dann mehr. Trotzdem Danke, inspirieren lass ich
mich aber davon, auch wenn ich ehrlichgesagt eine Funktion (*compar)()
so noch nie gesehen habe (ein Pointer auf ne funktion, wild.) und auch
sonst mit einigen Typen (zB. size_t) und variablen (z.B. nmemb) nicht
viel anfangen kann...
ein Pointer auf ne funktion, wild.
Aber irgendwie stell ich mich auch grad wirklich an...
ich habe 40 * 4byte (80*4 passen nicht ins 256kb-eeprom, also reichen
auch 40)
die 4byte-Blocks bestehen je aus 2 byte Messwert und 2byte Rückgabewert.
Da ich bei jeweils den nächst höheren UND nächst tieferen Wert haben
möchte, denke ich ist eine Aufsteigend sortierte Liste die besste Wahl,
da ich dort die beiden Werte immer schön bei einander habe.
Nur 40 Einträge durchsuchen, beginnend beim 20. klingt so einfach...
Ich bekomms gerade nicht hin.
1
//counter ist der Messwert
2
...
3
address=0x50;// Startadresse des 20. Tabelen-Eintrags
4
5
for(i=0x28;i>=4;i>>=1){
6
tab_val=eeprom_read_word(address);
7
if(tab_val<counter)
8
address+=i;
9
elseif(tab_val>counter)
10
address-=i;
11
else
12
//TREFFER, Happy
13
}
Das wär jetzt mein Ansatz gewesen, ist viel kürzer, scheitert aber an:
- in der 4. "for-Runde" wird ein ungültiger Tabelleneintrag ( z.B.
Eintrag 2,5 ) ausgelesen.
- Eintrag 1 kann nie ausgelesen werden, selbst wenn counter immer
kleiner als tab_val ist.
( counter immer kleiner tab_val => Auslese-adressen: 0x50 -> 0x28 ->
0x14 -> 0xA0 (nicht gültig) -> 0x05 (nicht gültig) -> 0x02 ...)
Ich glaube ich sollte wirklich nochml ne Nacht drüber schalfen!
Danke trotzdem allen die helfen wollten!
Johannes R. schrieb:> Danke für die Codes. Ich werde sie aber so nicht verwenden.> Ich entwickle lieber selbst was.
Dein Ehrgeiz in Ehren, aber insbesondere am Anfang (und da stehst du
nach meinem Eindruck derzeit noch) ist es keine Schande, auch mal
relativ einfache Dinge fertig zu übernehmen, mit dem Verstehen des
fremden Codes ist man da oft schon genug beschäftigt. Nur "blind"
übernehmen solltest du den Code nicht, sondern immer versuchen, ihn auch
selbst zu verstehen.
Selbst später ist es dann oft (viel) gesparte Zeit, wenn man Code von
anderen übernehmen kann ;-)
> auch wenn ich ehrlichgesagt eine Funktion (*compar)()> so noch nie gesehen habe (ein Pointer auf ne funktion, wild.)
Wenn du einen einfachen Funktionspointer in C schon wild findest, was
ist dann, wenn du irgendwann mal an eine Programmiersprache gelangst,
bei der Funktionen ganz normale Objekte sind (wie z.B. auch eine Zahl),
die Variablen zugewiesen und über geeignete Operatoren (dynamisch)
verändert werden können, es anonyme Funktionen (also ohne Namen) gibt
etc.? ;-)
> und auch> sonst mit einigen Typen (zB. size_t)
Du solltest dich erstmal ausgiebig mit einem C-Einsteigerbuch
beschäftigen, auch wegen der Sache mit den Funktionspointern. Das sind
nun wirklich keine "abgefahrenen" Konstruktionen, sondern ganz normales
Feld, Wald und Wiesen-Alltags-Handwerkszeug.
Danach ist dann die binäre Suche auch kein Problem mehr (wenn sie nicht
sowieso schon als Beispiel oder Übung im Buch drankommt ;-).
> und variablen (z.B. nmemb) nicht> viel anfangen kann...
Was die Parameter genau bedeuten steht in der Dokumentation von
bsearch(), die must du schon zuende lesen und nicht nach dem Prototyp
aufhören. "nmemb" speziell ist eine (gängige) Kurzform für "number of
members", also die Anzahl der Elemente.
> Das wär jetzt mein Ansatz gewesen, ist viel kürzer, scheitert aber an:
Bei der Schleife zum Durchlaufen des Arrays solltest du dich erstmal an
den Arrayindex halten, anstatt ohne Not direkt mit den Adressen
"rumzuhampeln". Vor allem als Anfänger vereinfacht das das Verständnis
ungemein, wenn man nicht auch noch immer im Kopf alles mit 4
multiplizieren/dividieren muss. Die Berechnung der konkreten Adressen
kann man dann durch geeignete Gestaltung getrost dem Compiler/Linker
überlassen.
Ausserdem solltest du nicht pauschal Hex verwenden, wir denken nunmal
dezimal, da ist es immer einfacher wenn die Konstanten im Code auch
dezimal sind. Natürlich nur weil das hier im wesentlichen Zähler sind,
bei von der Sache her binären Dingen (Flagwerte, Adressen etc.) kann es
durchaus angebracht sein, Hex zu arbeiten.
> - in der 4. "for-Runde" wird ein ungültiger Tabelleneintrag ( z.B.> Eintrag 2,5 ) ausgelesen.
Dein Zähler ist eine Ganzzahl (zumindest nehme ich das an, da die
Deklaration von i nirgendwo bei dir steht). Dieser kann keine
Nachkommastellen haben, sondern diese werden bei der Berechnung
abgeschnitten. Wenn mathematisch exakt also 2,5 rauskäme, steht
anschliessend 2 in deiner Variablen.
> - Eintrag 1 kann nie ausgelesen werden, selbst wenn counter immer> kleiner als tab_val ist.
Das stimmt zwar für deinen Code, das liegt aber nicht an der Berechnung.
1/2 ist bei Ganzzahlrechnung 0!
Eine gängige Methode, binäre Suche in einem sortierten Array zu
implementieren, ist per Intervallschachtelung. Aussehen kann das z.B.
so:
Der Code kann sicher noch optimiert werden, aber insbesondere am Anfang
sollte die Verständlichkeit erstmal einen höheren Stellenwert haben.
Ausserdem hat der Code noch Probleme, wenn der nachzuschlagende Counter
kleiner als der kleinste oder grösser als der grösste Wert in der
Tabelle ist. Warum das so ist, und das dann zu beheben, überlasse ich
dir als (Verständnis-)Übung ;-)
Andreas
Andreas Ferber schrieb:> Was hindert dich daran, das Standard-bsearch() mit einer geeigneten> Vergleichsfunktion zu verwenden?
Das wird dir irgendeinen Wert <=key liefern, aber nicht unbedingt den
kleinsten davon.
bsearch bricht sofort ab, wenn die Vergleichsfunktion 0 liefert.
hatte mal ne vorlesung über datenstrukturen, nent funktionspointer
wildes Programmieren und liefert so was ab. (oder es ist mit absicht so
geschrieben, weil er schon massiv optimieren wollte)
du vermischt den addressen und strukturpositionen in deiner for
schleife. entweder
40 und >=1 oder 160 und >=4
wobei ich da jetzt auch nicht sagen kann, ob das immer funktionieren
wird.
ich vermute mit 32 / 64 ja an sonsten nein.
anderer Forschlag:
so wie ich das jetzt verstanden habe, willst du messergebnisse in
gruppen zusammenfassen für eine statistische auswertung.
Die Gruppen sind durch den tab_val[x] und tab_val[x+1] begrenzt.
wenn die gruppen sich durch eine Funktion definieren lassen könnten,
müsstest due den tab_val nicht mitschleifen, und köntest dann auch
direkt addessieren. Wenn es eine entsprechende Funktion calcTblPos gibt,
die das in brauchbarer zeit liefert.
1
uint16_tmesswertTbl[40];
2
uint16_tmesswert=getMesswert();
3
4
uint8_tpos=calcTablPos(messwert);
5
6
messwertTbl[pos]++;
weiter, da sich deine Grenzen warscheinlich nicht dynamisch ändern,
könntest du diese auch in einer lookuptbl im Code hinterlegen ( nicht im
RAM) und ähnlich deiner jetzigen suche die position ermitteln.
sicher nicht viel anderes als das was du machen wolltest, nur immer nur
duch 2 teilen, funktioniert nur für 2 hoch n speicherpositionen, bei
allem anderen geht das irgendwo mal schief. siehe 2,5te
speicherposition.
A. K. schrieb:> Johannes R. schrieb:>>> Ist das dann nicht schon das Prinzip des Binärbaums?>> Vom Ablauf her ja, nur wird hier nicht als Baum gespeichert, sondern als> normales Array. Division durch 2 (>>1) ist ja kein Aufwand.>>> Wen man dann noch den Binärbaum so entartet>> Kann er hier nicht, denn die Daten sind fix.
Kommt drauf an wie man die Struktur im Speicher interpretiert...
Nimmt man einen simplen, nicht irgendwie balancierten Baum bzw. dessen
Algorithmen und füttert ihn mit sortierten Daten, ertartet dieser immer
(d.h. wird zur Liste).
Läubi .. schrieb:> Johannes R. schrieb:>> dass häufiger auftretende Messwerte näher am Stamm sind,> ne das ist Quatsch dann kannst du nicht mehr Vernünftig suchen!> Das würde nur bei einer linearen Suche etwas bringen.
Mir fällt zwar im Moment der Name dafür nicht ein, dafür aber
http://www.itl.nist.gov/div897/sqg/dads/HTML/interpolationSearch.html
(O(log log n) statt O(log n)) falls die Daten gleichverteilt sind.
Klaus Wachtler schrieb:> Das wird dir irgendeinen Wert <=key liefern, aber nicht unbedingt den> kleinsten davon.>> bsearch bricht sofort ab, wenn die Vergleichsfunktion 0 liefert.
Genau das soll sie auch. Schau dir meine Compare-Funktion nochmal genau
an, die liefert 0 exakt dann zurück, wenn der Key in das von zwei
aufeinanderfolgenden Arraywerten gebildete Intervall fällt (wobei die
untere Grenze ausgeschlossen, die obere eingeschlossen ist). Es kann
keine weiteren Werte geben, die dazwischenliegen würden, da das Array
sonst nicht sortiert wäre. Die untere Intervallgrenze ist dabei in
meinem Fall das, was bsearch() als zu vergleichenden "Member" an die
Comparefunktion übergibt.
Das bsearch-Ergebnis ist also nicht irgendein Wert, sondern der
grösste, der kleiner als der Key ist. Der nächste Wert in der Folge
ist dann der kleinste, der grösser oder gleich dem Key ist. Immer dran
denken, dass die Folge sortiert ist.
Andreas
Arc Net schrieb:> Nimmt man einen simplen, nicht irgendwie balancierten Baum bzw. dessen> Algorithmen und füttert ihn mit sortierten Daten, ertartet dieser immer> (d.h. wird zur Liste).
Ich bezog mich auf die Darstellung fester Daten als sortiertem Array und
der binären Suche per sukzessiver Intervall-Halbierung. Bei dieser
Methode habe ich einige Schwierigkeiten, die Möglichkeit einer Entartung
zu erkennen.
Wenn die Daten nicht fest sind, sondern nacheinander eintrudeln, dann
ist diese Methode der Speicherung natürlich weniger praktikabel. Aber
darum geht es hier m.W. nicht.
Noch eine ganz andere Idee:
Evtl. ist es auch so, daß sich die Werte von einer Berechnung zur
nächsten eher wenig ändern.
Dann kann es einfach und effektiv sein, doch linear zu suchen.
Beim ersten Mal ab Anfang oder Mitte der Tabelle (ok, ist doof)
und ab dann die letzte Position in einer static-Variablen zu merken
und immer ab da suchen.
Klaus Wachtler schrieb:> Evtl. ist es auch so, daß sich die Werte von einer Berechnung zur> nächsten eher wenig ändern.
Er hatte oben geschrieben, dass diese Tabelle die Berechnung einer
Funktion erleichtern soll. Das klingt nicht danach, als ob sich die
Werte ändern.