4. Look-Up-Table, floor-Funktion

Look-Up-Table, floor-Funktion

  • G

    Ich habe eine Look-Up-Table z.B.:

    const unsigned int tabelle[12] = {8192, 4836, 2555, 1297, 651, 325, 163, 81, 41, 20, 10, 5};

    nun möchte ich für eine eingegebene Variable (x) wissen zu welchem Listen-Index der Wert gehört.

    Wichtig die Funktion soll mir den Index liefern bei dem die Zahl kleiner oder gleich der eingegebenen ist.

    In SQL gibt es hierfür die Funktion "floor". Siehe:
    http://www.sql-und-xml.de/server-daten/sql-befehle/floor.html

    Hier einige Beispiele damit ihr versteht was ich meint:

    floor(1000) -> 4 = [651]
floor(8200) -> 1 = [8192]
floor(8192) -> 1 = [8192]
floor(8191) -> 2 = [4836]

    Kann mir jemand helfen wie ich eine solche Funktion in ANSI C schreiben kann?

    0
  • H

    das kannst du selbst. geh halt durch das array und guck wie weit dein x vom jeweiligen wert entfernt liegt - der index des wertes mit kleinster distanz ist das ergebnis.
    wenn die tabelle gross wird brauchste hashing.

    0
  • M

    Da das Array sortiert ist, kann man eine binäre Suche benutzen.

    0
  • G

    Danke für eure Antworten.

    Ich habe mitlerweile rausgefunden das in der math.h die floor funktion abgebildet ist:

    double floor(double);

    nun würde ich gerne einmal den Quelltext der Funktion sehen. Ich weiß des ist ne ziemliche Anfängerfrage aber wo findet man den Quelltext zu den Standardfunktionen?

    Ich würde die Funktion gerne für mich selbst Umschreiben in:

    int floor_int(int);

    Hintergrund: Das ganze ist für einen Mikrokontroller und der hat bekanntlich wenig Speicher und Rechenpower daher keine Standardfunktionen und Fließkommazahlen.

    @MFK eine binäre Suche findet doch nur wenn das Ergebnis exakt mit dem Suchwert übereinstimmt?

    :schland:

    0
  • ?

    Die floor() Funktion aus ANSI C macht aber nicht was du denskt, von daher bringt dir der Quellcode nix 😉

    Da es für einen (kleinen nehme ich an) µC ist, mach eine einfache lineare Suche. Die kostet wenig Speicher und dürfte bei so wenigen Elementen auch schneller sein als eine binäre Suche.

    0

  • floor() hilft dir nicht. floor rundet eine Fließkommazahl ab. Du kannst double floor( double ) nicht in int floor( int ) "umschreiben". Du könntest sie höchstens neu schreiben. Jetzt aber egal, denn floor() hilft dir nicht.

    Wenn die Werte deines Lookup-Tables weiterhin von links nach rechts absteigend sortiert sein wird, kannst du

    #include <iostream>

using namespace std;

int get_lowest_index( unsigned int value )
{
    const unsigned int tabelle[12] = {8192, 4836, 2555, 1297, 651, 325, 163, 81, 41, 20, 10, 5};

    for( int i = 0; i < 12; ++i ) {

        if( tabelle[ i ] <= value )
            return i;
    }
}

int main( )
{
    cout << get_lowest_index( 160 ) << endl;
}

    verwenden.

    Greetz, Swordfish

    0
  • B

    Swordfish schrieb:

    #include <iostream>

using namespace std;

int get_lowest_index( unsigned int value )
{
    const unsigned int tabelle[12] = {8192, 4836, 2555, 1297, 651, 325, 163, 81, 41, 20, 10, 5};
	
    for( int i = 0; i < 12; ++i ) {
	
        if( tabelle[ i ] <= value )
            return i;
    }
}

int main( )
{
    cout << get_lowest_index( 160 ) << endl;
}

    verwenden.

    Greetz, Swordfish

    Ich denke eher:

    #include <stdio.h>

int get_lowest_index(unsigned int value)
{
    const unsigned int tabelle[12] = {8192, 4836, 2555, 1297, 651, 325, 163, 81, 41, 20, 10, 5};
    int i;
    for(i = 0; i < 12; ++i) {

        if(tabelle[i] <= value)
            return i;
    }
}

int main( )
{
    printf("%d", get_lowest_index(160));
}

    Wir sind doch hier im Ansi-C Forum, oder?
    Hab's mal C89 'valid' geschrieben (hoffe ich zumindest, falls mir ein Fehler unterlaufen sein sollte, sorry!), falls sein Compiler auch C99 unterstützt, kann er ja das int i = 0 wieder in die for-schleife tun.

    0
Anmelden zum Antworten