[Thema] Suchalgorithmus

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von Schmitz, 25. September 2007 .

Schlagworte:
Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 25. September 2007
    Suchalgorithmus

    Hallo
    ich bin auf der Suche nach einem geeigneten Suchalgorithmus.
    realisieren will ich ihn mit PHP, allerdings hoffe ich, dass ich hier mehr leute erreiche
    beschreiben könnt ihr den algorithmus wie ihr wollt, wenn ich die programmiersprache nicht verstehe frag ich halt nach
    also, nun zur "aufgabenstellung":

    Vorhanden ist ein sortiertes Array
    Code:
    Array (
 0 => Array (
 'id' => 1,
 'name' => 'Blub1'
 )
 1 => Array (
 'id' => 2,
 'name' => 'Blub2'
 )
 2 => Array (
 'id' => 4,
 'name' => 'Blub3'
 )
 3 => Array (
 'id' => 8,
 'name' => 'Blub4'
 )
)
    wie man sieht ist es nach id sortiert, wobei nicht unbedingt jede ID vorhanden sein muss
    dieses array mit knapp 2,5k einträgen würd ich nun gerne nach einer bestimmten ID durchsuchen
    bisher gehe ich nach folgendem prinzip vor:

    ich setze 2 eigene zeiger am anfang und am ende fest
    dann überprüfe ich, ob die gesuchte ID vllt. an diesen stellen ist
    ist das nicht der fall, bilde ich den mittelwert, überprüfe diesen ebenfalls
    ist die gesuchte ID größer verschiebe ich den "linken" zeiger auf den mittelpunkt +1, ist die ID kleiner das ganz andersrum
    und dann gehts wieder von vorne los

    das problem ist, dass dies bei den genannten einträgen mitunter sehr lange dauert
    allerdings ist es von meinem wissen her der beste ausgleich zwischen bestcase und worstcase
    soll heißen: im idealfall ist das ding am anfang oder am ende und ich finde es direkt
    im worstcase brauche ich 1,25k durchläufe (so in etwa)
    wenn ich von vorne nach hinten durchgehen würde, bräuchte ich um den letzten eintrag zu finden doppelt so lange

    so, ich hoffe mal irgentjemand hat eine bessere idee
     
  3. 25. September 2007
    AW: Suchalgorithmus

    hmm gibt mehrere sachen wie du das machen kannst, z.b.:

    skiplisten <--- sehr schöne lösung mit randomisierung

    oder halt suchbäume (AVL-Bäume zum beispiel)

    aber ich denke eher wenn du das ganze mit php machst dass nicht die suche an sich so lange dauert sondern eher die form wie du die daten einliest. denke dass dies eher der flaschenhals ist
     
  4. 25. September 2007
    AW: Suchalgorithmus

    das ist richtig ^^ habe grade mal getestet und rausgefunden, dass das einlesen von 3,34MB wohl das Problem sein wird
    das kostet mich mal eben 6 sekunden, das suchen innerhalb des arrays nichtmal eine halbe
    ich glaube dann werde ich dafür wohl doch MySQL benutzen müssen
    naja, hat sich wohl erledigt
     
  5. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.