www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hashfunktion oder Trick für Lookup-Tabellen gesucht


Autor: Johannes R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
Messwert  Ausgabewert
18750     30
9375      29
6250      28
4688      27
3750      25
3125      20
2679      15
2344      12
2083      11
1875      10
1705      9
1563      9
1442      9
...
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

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Joachim K. (minifloat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Joachim K. (minifloat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OT: Wie schnell ist denn der EEPROM beim auslesen? bzw. Wie schnell 
lässt du deinen AVR(welchen?) rennen?

Autor: Johannes R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.
Lesen vom EEPROM:    4 Takte
Vergleich größer/kleiner: 2 Takte
Sprung:                   3 Takte
Reserve:                  1 Takt
---------------------------------
                         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" ;)

Autor: Johannes R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!!!

Autor: Johannes R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!!!

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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..

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
mfgkw

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:

> mfgkw

In der stillen Hoffnung, dass der Compiler die unsinnge Endrekursion 
selber auflöst...

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da bin ich relativ zuversichtlich.
Ansonsten bleibt es als Hausaufgabe für den aufmerksamen Leser...

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> mfgkw

Was hindert dich daran, das Standard-bsearch() mit einer geeigneten 
Vergleichsfunktion zu verwenden?
int compare(const void *key, const void *member)
{
        const int *k = key, *m = member;
        if (*k <= *m)
                return -1;
        else if (*k > *(m+1))
                return 1;
        else
                return 0;
}

int translate(int n)
{
        static int data[] = { /* ... */ }
        int *pos;

        pos = bsearch(&n, data,
                      sizeof(data)/sizeof(data[0])-1, sizeof(int),
                      compare);

        return pos ? *(pos+1) : data[0];
}

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

Autor: Johannes R. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.
//counter ist der Messwert
...
address = 0x50;  // Startadresse des 20. Tabelen-Eintrags

for ( i = 0x28; i >= 4; i >>= 1 ) {
  tab_val = eeprom_read_word( address );
  if ( tab_val < counter )
    address += i;
  else if ( tab_val > counter )
    address -= i;
  else
    //TREFFER, Happy
}

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!

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
#include <stdint.h>
#include <stdbool.h>
#include <avr/eeprom.h>

struct data_rec {
        uint16_t counter;
        uint16_t result;
};

#define TABLE_SIZE 40

struct data_rec lookup_table[TABLE_SIZE] EEMEM = {
        { 1442, 9 },
        { 1563, 9 },
        /* ... */
};

uint16_t lookup(uint16_t counter)
{
        uint8_t lower = 0, upper = TABLE_SIZE-1;

        while (lower <= upper) {
                uint8_t middle;
                uint16_t value;

                middle = (lower+upper)/2;
                value = eeprom_read_word(&lookup_table[middle].counter);

                if (value < counter)
                        // search "right" half
                        lower = middle+1;
                else if (value > counter)
                        // search "left" half
                        upper = middle-1;
                else
                        // value found
                        return eeprom_read_word(&lookup_table[middle].result);
        }

        // default if no entry found
        return 0;
}

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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: abcdefg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: abcdefg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.
uint16_t messwertTbl[40];
uint16_t messwert = getMesswert();

uint8_t pos = calcTablPos(messwert);

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.

static const uint16_t LOOK_UP[41] = {1,2,3,4,5,6,7, ...};

int8_t calcTblPos( uint16_t messwert )
{
   uint8_t ret;

   a = 0;
   b = 40;

   if ( messwert < LOOK_UP[ a ] )
   {
      return -1; 
   }

   if (messwert > LOOK_UP[ b ])
   {
      return -2;
   }

   do 
   {
      c = (a + b) / 2;
      if ( messwert >= LOOK_UP[c])
         a = c;
      else
         b = c;
   } while ( (a+1) <= b );
   return ret;
}

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.

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/inter...
(O(log log n) statt O(log n)) falls die Daten gleichverteilt sind.

Autor: Andreas Ferber (aferber)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da habe ich in der Tat die Vergleichsfunktion nicht genau genug 
angesehen.
So geht es natürlich auch.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.