Algo in c++ optimieren



  • Hallo,

    Ich habe ein interessantes Algo problem fuer C++:
    Gegeben ist eine Liste von Woertern: ["ratcatdogcat", "cat", "cats", "catsdogcats", "catxdogcatsrat", "dogcatsdog", "hippopotamuses", "rat", "dog" "ratcat", "ratcatdog"]
    Finde das laengeste Wort welches in der Liste existiert und welches durch mehrere Woerter aus der Liste zusammengebaut werden kann.

    In diesem Beispiel waere die Loesung: "ratcatdogcat", weil es aus den Woertern: "rat" + "cat" + "dog" + "cat" zusammengebaut werden kann.

    hier meine Loesung (noch mit einem bug):
    http://ideone.com/KZfuRD

    habt ihr eine bessere idee das zu loesen?


  • Mod

    Ehrliche Meinung: Schlechte Idee, schlecht umgesetzt.

    Umsetzung: Globale Variablen, 'nuff said. Ein weiteres Alarmzeichen ist, dass du etwas sortierst. Und dann einen vector aktiv revers'en, weil du etwas von hinten suchst? Wie wäre es mit rückwärts laufen? Und vieles weitere mehr.

    Idee: Dein Vorgehen ist also, alle Möglichkeiten zu erzeugen und dann zu gucken, ob eines dieser vielen erzeugten Wörter in der Liste vorkommt? So viel Arbeit, um hinterher so wenig mit dem Ergebnis zu machen 👎

    Viel besser wäre es bestimmt, die Wörter selber darauf zu prüfen, ob sie überhaupt Kandidaten sind. Sich also möglichst viel Arbeit zu sparen. Ideal wäre eine Datenstruktur, die einem erlaubt festzustellen, ob es in einer Liste Wörter gibt, die mit einer bestimmten Zeichenfolge losgehen. Am besten so, dass man dann eine eingeschränkte Subliste für die nächste Abfrage als Antwort erhält. Das ist eine Frage an die studierten Informatiker hier, die kennen da bestimmt ein tolles Stichwort dafür. Wenn man solch eine Liste hat, kann man alle Wörter durchgehen und folgendes tun:

    • anfang: Gehe zum nächsten Wort
    • Ist das Wort überhaupt länger als der bisher beste Kandidat? Falls nein -> anfang
    • suchbeginn: Das aktuelle Suchwort ist leer.
    • Gibt es ein nächstes Zeichen? Falls nein -> aktuelles Wort wird bester Kandidat. Gehe zu anfang.
    • nächtes_zeichen: Füge das nächste Zeichen zum aktuellen Suchwort hinzu.
    • Gibt es in der Liste Wörter, die mit dem aktuellen Suchwort beginnen? Falls nein -> anfang
    • Gibt es in der Liste eine exakte Übereinstimmung für das aktuelle Suchwort? Falls ja: Verzweige(!) zu suchbeginn
    • Gehe zu nächstes_zeichen


  • SeppJ schrieb:

    Ideal wäre eine Datenstruktur, die einem erlaubt festzustellen, ob es in einer Liste Wörter gibt, die mit einer bestimmten Zeichenfolge losgehen. Am besten so, dass man dann eine eingeschränkte Subliste für die nächste Abfrage als Antwort erhält. Das ist eine Frage an die studierten Informatiker hier, die kennen da bestimmt ein tolles Stichwort dafür.

    wäre unwahrscheinlich, an der uni von prefix trees zu hören.



  • volkard schrieb:

    SeppJ schrieb:

    Ideal wäre eine Datenstruktur, die einem erlaubt festzustellen, ob es in einer Liste Wörter gibt, die mit einer bestimmten Zeichenfolge losgehen. Am besten so, dass man dann eine eingeschränkte Subliste für die nächste Abfrage als Antwort erhält. Das ist eine Frage an die studierten Informatiker hier, die kennen da bestimmt ein tolles Stichwort dafür.

    wäre unwahrscheinlich, an der uni von prefix trees zu hören.

    Gehört hab ichs mal, hätte die aber so erstmal nicht erkannt anhand der Erklärung. Aber durch das Stichwort "PrefixTree" fiels mir wie Schuppen von den Augen.

    Aber wenn nicht an ner Uni hören wo/wann dann? In der Ausbildung zum geprüften Fachinformatiker der Anwendungsentwicklung Assistent?



  • Hi,

    ich habe schon mal was von einem trie gehoert. ich brauch da einfach nur eine start_prefix methode implementieren?

    ich verstehe den also nicht ganz...was meinst du mit Suchwort?



  • ich hab meine loesung ein bisschen geaendert:
    1.) alle woerter in den trie hinzufuegen
    2.) alle woerter der laenge nach sortieren (maximale laenge -> minimale laenge)
    3.) jedes wort pruefen ob es auch mehreren woertern zusammengesetzt werden kann -> algo b

    algo b:
    1.) erzeuge alle prefix ersten kandidaten e.g. "ratcatdogcat"
    -> "r", "ra", "rat", "ratc", "ratca", "ratcat", "ratcatd", "ratcatdo", "ratcatdog", "ratcatdogc", "ratcatdogca"
    2.) pruefe ob irgendein prefix string im trie vorhanden ist:
    wir sehen das "rat" und "ratcat" und "ratcatdog" im trie existieren
    3.) koennen fuer diese 3 kandidaten den suffix nehmen und damit eine recursion machen:
    "catdogcat", "dogcat", "cat" ... fuer diese 3 kandidaten wird dann werden dann wieder alle prefixes erzeugt usw...

    das sortieren ist nicht recht langsam, wenn ich die liste der woerter gross ist...



  • Skym0sh0 schrieb:

    Aber durch das Stichwort "PrefixTree" fiels mir wie Schuppen von den Augen.

    Aber wenn nicht an ner Uni hören wo/wann dann? In der Ausbildung zum geprüften Fachinformatiker der Anwendungsentwicklung Assistent?

    Naja, eigentlich geisterte mit der suffix tree im Kopf rum, gelesen in Sachen lempel-ziv. Privat gelesen aus Interesse, nix mit Uni. Und schon soo lange her, daß ich so frei sein konnte, den prefix tree zu erspinnen. Den Gips überhaupt nicht, fürchte ich; der (von mir leider nicht genannte) trie riecht aber sehr lecker. Oder auch der suffix tree.



  • volkard schrieb:

    wäre unwahrscheinlich, an der uni von prefix trees zu hören.

    Richtig, hab ich noch nie gehört. Hab gegoogelt und "Trie" gefunden, das kenn ich hingegen schon und habs auch schon benutzt.


  • Mod

    algoman schrieb:

    das sortieren ist nicht recht langsam, wenn ich die liste der woerter gross ist...

    Was soll denn immer dieses Sortieren? Wenn du etwas sortierst und dein Ziel nicht ausdrücklich ist, eine sortierte Liste zu erhalten, dann machst du höchstwahrscheinlich etwas gravierend falsch.



  • @SeppJ:

    ich sortiere alle woerter der laenge nach sortieren (maximale laenge -> minimale laenge)... was ist daran falsch?


  • Mod

    algoman schrieb:

    was ist daran falsch?

    Dass es nicht nötig ist für das gewünschte Ergebnis. Deine Frage ist "was ist das längste Wort, das ein bestimmtes Kriterium erfüllt?". Wieso denkst du, dazu wäre es nötig, zuerst alle Wörter der Länge nach zu sortieren? Wenn ich dich frage, welches die größte Zahl aus "25 538 28 485 237 285 18 283 492" ist, ist es dann auch dein erster Instinkt, alle diese Zahlen zu sortieren? Wie ich schon sagt, sortieren tut man nur, wenn man etwas sortiert haben möchte.



  • @SeppJ: oh hast recht... da habe ich wohl etwas verwechselt...

    kann man den algo sonst noch schneller machen?


  • Mod

    Ich sehe keinen Grund, meine Antwort noch einmal zu wiederholen, solange du diese nicht einmal umgesetzt hast.



  • SeppJ schrieb:

    algoman schrieb:

    was ist daran falsch?

    Dass es nicht nötig ist für das gewünschte Ergebnis. Deine Frage ist "was ist das längste Wort, das ein bestimmtes Kriterium erfüllt?". Wieso denkst du, dazu wäre es nötig, zuerst alle Wörter der Länge nach zu sortieren? Wenn ich dich frage, welches die größte Zahl aus "25 538 28 485 237 285 18 283 492" ist, ist es dann auch dein erster Instinkt, alle diese Zahlen zu sortieren? Wie ich schon sagt, sortieren tut man nur, wenn man etwas sortiert haben möchte.

    Ja nein, doch, der Länge nach zu sortieren ist mein erster Instinkt. (Nicht dem Wert nach, ich brauche keine Vollsortierung, ich brauche sie nur der Länge nach als eine Vorsortierung.) Hier ist Dir die Intuition/Azubiempathie flöten gegangen.

    Wenn ich dich frage, welches die größte Zahl aus "
    25
    538
    28904
    28
    485
    4556
    237
    56782
    285
    18
    34567
    283
    492
    " ist, ist es dann auch dein erster Instinkt, alle diese Zahlen zu sortieren? Da ist irgendwas, was mich auf die drei 5-stelligen Zahlen schauen läßt *bevor* ich deren Werte genau analysiere und rechnerisch vergleiche. So als Normalo-Mensch.

    Für den C++-Rechner ist das aber halt keine Beschleunigung und tut den Code nur unnötig komplizierter machen tun. Darum tut man es beim pr0ggern nicht machen. Das ist aber antiintuitiv, gell.

    Naja, genau genommen ist die erste Verarbeitungsstufe keine Sortierung, weil es keine erste Verarbeitungsstufe gibt. Es ist eher ein

    [](x){
        if(len(x)<maxlen)
            ;
        if(len(x)>maxlen)
            maxlen=len(x)
            maxval=x;
            ;
        if(x<maxval)
            ;
        if(x>maxval)
            maxval=x;
            ;
        ;
    ...
    

    Aber bevor ich das einem BWLer auch nur andeutungsweise erkläre, lasse ich ihn die Zahlen alle sortieren oder als ultrasuperduperversion erst nur der Länge nach und dann nur die längsten des Wertes nach.

    Ohne Ultrasuperduperversion und erst dann, wenn er das per Hand 100 mal gemacht hat, erlaube ich ihm lazy evaluation und er muss die bisher kürzeren gar nicht durchsortieren, halt insofern wie die Nichtsortierung bisher fürs Endergebnis irrelevant ist. Ok, lazy *und korrekt* sind die guten BWLer theoretisch auch (never seen one of them; ich schreib ihm besser ein Excel-Makro).



  • @Volkard: sorry, wie schon gesagt sortieren ist nicht noetig, faellt dir sonst noch eine optimierung ein?



  • algoman schrieb:

    @Volkard: sorry, wie schon gesagt sortieren ist nicht noetig, faellt dir sonst noch eine optimierung ein?

    Denke mal, wir teilen und wenn der Vorderteil passt, wir den Hinterteiul teilen?

    Ich probiere gerade mal was rum, Trie und verschiedene Hashtables und jeweils ohne boost oder std. Weil ich sowas zufällig auf Arbeit brauchen könnte auf einer grünen Güllepumpe.

    *falls* ich was neues rausfinde, poste ich in diesem Forum. Meine früheren Versuche waren stets ein wenig langsamer als die std::-Imlementierungen. Also die sind schon verflixt gut. Nimm die als Kern.



  • @Volkard: ich habe hier mal meine C++ version:
    http://ideone.com/nAhwHG

    der code hat noch kein delete fuer den trie eingebaut...



  • algoman schrieb:

    @Volkard: ich habe hier mal meine C++ version:
    http://ideone.com/nAhwHG
    der code hat noch kein delete fuer den trie eingebaut...

    Mein Code sieht sehr ähnlich aus (, nur funktioniert er noch nicht 🙂 ).
    Schon faszinierend, wie einfach ein so Trie zu bauen ist.
    Wire ist denn die Laufzeit bei den 300k?



  • @Volkard: fuer 260k woerter:

    g++ -o main main.cpp -std=c++14; ./main
    1309.99 ms
    


  • die meinste zeit wird in get_prefixes verbraten...


Anmelden zum Antworten