element schnell in einem array finden



  • hallo,

    ich bin gerade dabei einen disassembler zu programmieren, jetzt bin ich vor dem problem das ich irgendwann einen riesen liste von funktions entry-points habe, welche ich jedes mal bei einen "call opcode" neu durchsuchen muss ob ich dort schon war.
    deshalb meinen frage ist iterativ suchen gleich schnell wie
    -jedes mal die liste beim einfügen mit quicksort zu sortieren
    und dann mit binärer suche zu durchlaufen wenn ich wissen will ob ein element schon eingetragen wurde ?

    gibt es mit normalen ansi-c bessere möglichkeiten ?

    danke



  • Afaik ist quicksort die schnellste Sortierungsart. Nen besseren Weg als sortieren und dann binär suchen wirst du nicht finden..



  • iterativ suchen hat im worst-case O(n), ein kluges quicksort + binäres suchen hat O(n*log(n))

    also wenn du es sonst nicht sortiert haben musst, ist es schwachsinn zuerst zu sortieren!



  • ich denke das beste wäre du legst für jedes byte zu dissassemblierenden code ein egenes byte an (also einen zweiten speicherbereich so groß wie der zu disassemblierende code). in diesem byte kannst du dann speichern, ob der code an der stelle ein mnemonic, datenconstante oder wer weiß was ist.

    schneller gehts nicht mehr 😃



  • Kommt sowieso drauf an, ob die suche mehrfach auf den selben Array angewendet werden muss oder nicht. Bei dem Schema:

    - neues Element eifügen
    - Element suchen
    - neues Element einfügen
    - Element suchen
    ....

    hilft nur sequentielles durchsuchen. Da ist sortierung jeglicher art vorher nur zeitverschwendung.

    Bei

    - neues Element einfügen
    - Element suchen
    - Element suchen
    ...

    ist natürlich ein vorsortierter Array schon vorteilhaft. Quicksort ist aber AFAIK nicht besonders gut dafür geeignet ein einzelnes Objekt in einen sonst komplett sortierten Array einzusortieren, da er bei einem schon gut sortierten Array keine gute performance aufweist. Hier wäre vielleicht ein anderer Ansatz interessant.

    Wie wärs den mit nem schönen Binären Baum?



  • Hi,

    wenn es Dir um Geschwindigkeit geht, dann würde ich mich mal über A-V-L-Bäume schlau machen. Im Grunde ein Binärer Baum, der aber beim Einfügen und Löschen eines Knotens immer dafür sorgt, dass er ausbalanciert ist. Somit hast Du immer die geringste Höhe im Baum und hast Laufzeit O(log n). Selbst im worst-case.

    Ist zwar etwas komplizierter, als ein simples Array, aber die Vorteile sind nicht zu verachten.
    Hier ein Link, wo das erklärt wird, mit einem Programm, wo man ein wenig mit spielen kann. 🙂
    http://www.informatiktreff.de/materialien/sek_ii/algorithmen/avl/avlbaum.htm


Log in to reply