4. Array schnell durchsuchen

Array schnell durchsuchen

  • ?

    Hallo,

    gibt es einen schnellen Durchsuchungsalgorithmus für ein struct Array?

    struct _list {

    unsigned int *ID;
    //...
    };

    struct _list Liste[] {
    //arguments
    };

    Das struct Array ist sortiert nach einer ID (sieht struct _list). Diese ID besitzt z.B. folgende Zahlen (binär-baum):

    ...
ID1: 1          //  (1.1)
ID2: 1111       //  (1.1.1.1)
ID3: 1112       //  (1.1.1.2)
ID4: 11121      //  (1.1.1.2.1)
ID5: 1115       //  (1.1.1.5)
ID6: 1.2        //  (1.2)
ID7: 1.3        //  (1.3)
...

    Oder ist es sinnvoller das Array als BinärBaum darzustellen? Wie würde das funktionieren?

    LG
    Hans

    0
  • ?

    hmm du hast einen pointer auf einen integer in deiner struct. heißt das, dass du bei der id pro level einen integer hast? oder is das nur eine zahl für alle ebenen? wie kann man außerdem in einem binären baum eine id mit 5 oder 3 bekommen?

    0
  • ?

    ooo schrieb:

    hmm du hast einen pointer auf einen integer in deiner struct. heißt das, dass du bei der id pro level einen integer hast? oder is das nur eine zahl für alle ebenen? wie kann man außerdem in einem binären baum eine id mit 5 oder 3 bekommen?

    pro Eintrag in der struct, gibt es eine ID. Mit dem "Binärbaum" meinte ich lediglich die Ähnlichkeit. Aber es können alle Zahlen [0-9] vorkommen.

    Hab mir schon überlegt, ob ich zu Beginn das erste und letzte Element des Arrays mit der zu suchenden ID vergleiche .... aber das bringt mich auch nicht weiter, da die IDs ja unterschiedlich verteilt sind (z.B. gibt es unter 1.1 viele Elemente, unter 1.2 kein einziges element).

    Hans

    0
  • L

    In C99 gibt es die Funktion bsearch, die macht eine binäre Suche auf einem sortierten Array. Dieser übergibst Du einen Funktionszeiger auf eine Vergleichsfunktion, die -1, 0 oder 1 zurückgibt. Beispiel:

    int comp(void const* a, void const* b)
{
    struct _list const* left = (struct _list const*)a;
    struct _list const* right = (struct _list const*)b;
    return *left->ID < *right->ID ? -1 : (*left->ID > *right->ID ? 1 : 0);
}

unsigned int id = 1111;
struct _list schluessel = { &id };

struct _list* eintrag = bsearch(&schluessel, Liste, <Anzahl in Liste>, sizeof(struct _list), &comp);
if (eintrag != NULL) {
  /* gefunden */
}
    0
  • ?

    Hi Bruder !
    Halbierungssuche. Array nach Werten sortiert.

    0
  • ?

    Big Brother schrieb:

    Hi Bruder !
    Halbierungssuche. Array nach Werten sortiert.

    bringt das auch was, wenn die daten in einem array anscheinend nicht gleichmäßig verteilt sind - viele 11111 und wenig elemente von 1.2 vorhanden sind?

    0
  • ?

    ja

    0
  • ?

    Halbierungssuche

    das funktioniert doch so, dass man das letzte element und das erste element mit dem vorhandenen / zu suchenden element vergleicht und schaut in welcher hälft, der hintereren oder der vorderern des Arrays liegt.

    Wenn man allerdings z.B. 11121 suchen soll und die letzte zahl ist 13 und die erste ist 11 - muss man zuvor nochmals auf die gleiche anzahl an stellen aufstocken 13000 und 11000

    -> und wenn gleich nach 11121 13 kommt sucht man ziemlich lange...

    bsearch

    wie performantiert ist denn diese methode? Wieviel Overhead kommt hier dazu? Und wie schnell arbeitet bsearch?

    mfg
    array_sorter

    0
  • ?

    array_sorter schrieb:

    wie performantiert ist denn diese methode? Wieviel Overhead kommt hier dazu? Und wie schnell arbeitet bsearch?

    logarithmisch, wie die meisten solcher funktionen. d.h. es wird nur unmerklich langsamer, wenn die arrays riesengross werden. der 'echte' binary search ist rekursiv, aber ich glaube die c-funktion macht's ohne rekursion.
    🙂

    0
  • ?

    array_sorter schrieb:

    das funktioniert doch so, dass man das letzte element und das erste element mit dem vorhandenen / zu suchenden element vergleicht und schaut in welcher hälft, der hintereren oder der vorderern des Arrays liegt.

    ja.

    array_sorter schrieb:

    Wenn man allerdings z.B. 11121 suchen soll und die letzte zahl ist 13 und die erste ist 11 - muss man zuvor nochmals auf die gleiche anzahl an stellen aufstocken 13000 und 11000

    wenn die zahlen als strings gespeichert sind dann brauchst du nichts aufzustocken.

    array_sorter schrieb:

    -> und wenn gleich nach 11121 13 kommt sucht man ziemlich lange...

    was verstehst du unter lange, 😮 wie groß sind deine arrays ?

    0
Anmelden zum Antworten