3. Algo in c++ optimieren

Algo in c++ optimieren

  • ?

    @Volkard: mit -O3 sind es 550ms

    ich werde mal ein unordered_map verwenden anstatt des tries...
    kann ich die prefixes zu "ratman" -> "r", "ra", "rat", "ratm", "ratma" beim lesen des files erzeugen? dann brauch ich ne art multimap?

    das file ist lexikographisch sortiert.

    0
  • ?

    @Volkard: ich hab nun den algo auf ca. 900ms runter optimiert und mit -O3 kompiliert:
    http://ideone.com/WLZMOI

    was meinst du?

    0
  • V

    algoman schrieb:

    @Volkard: ich hab nun den algo auf ca. 900ms runter optimiert und mit -O3 kompiliert:
    http://ideone.com/WLZMOI

    was meinst du?

    Bin gerade zum ersten mal fehlerfrei geworden.
    Zeig mal die Eingabedatei (irgendein pastebin vielleicht), dann können wir leicht Zeiten und vor allem das gefundene Wort vergleichen. Welches Wort kam raus?

    0
  • _

    Hallo zusammen,
    da ihr euch jetzt hier battelt wer die schnellere Implementierung hat, mal ein paar Interessensfragen:

    (a) Müsstet ihr euren Code nicht ohne Optimierungen laufen lassen, um zu schauen wer den "besseren" Code schreibt? Der Optimierer kann ja u.U. einiges beschönigen.

    (b) Um eure Laufzeiten zu vergleichen müsste der Code ja auf der gleichen Hardware laufen. Gibt es nicht zufällig eine andere Messgröße/Metrik die man mit den bekannten Tools bestimmen kann? (Anzahl der atomare Instruktionen und diese irgendwie gewichtet) - um eine Hardware unabhängig Aussage treffen zu können ob Code A oder Code B.

    (c) Ändert doch die Umlaute zu ae, oe und ue, wie sz zu ss. Dann sollten eure Implementierungen doch wieder gehen!?

    Grüße

    0
  • V

    jb schrieb:

    Hallo zusammen,
    da ihr euch jetzt hier battelt wer die schnellere Implementierung hat, mal ein paar Interessensfragen:

    (a) Müsstet ihr euren Code nicht ohne Optimierungen laufen lassen, um zu schauen wer den "besseren" Code schreibt? Der Optimierer kann ja u.U. einiges beschönigen.

    Nein. Nie ohne -O3.
    Sonst wird man zu so lustigen Sachen gezwungen, wie Makros statt Funktionen zu verwenden oder Copy&Paste statt den selben Code in eine die selbe Bedeutung tragende Funktion auszulagern.
    Außerdem dann dauernd die Tricks wie "for(BlaIt i=bla.begin(),e=bla.end();i!=e;++i)" statt "for(BlaIt i=bla.begin();i!=bla.end();++i)" und am schlimmsten "i>>=1" statt "i/=2". Nee, die trivialen Optimierengen sollten alle weg sein, für uns irrelevant, daß es nur noch drauf ankommt, den am bessendsten passenden Container auszuwählen und so.

    jb schrieb:

    (b) Um eure Laufzeiten zu vergleichen müsste der Code ja auf der gleichen Hardware laufen. Gibt es nicht zufällig eine andere Messgröße/Metrik die man mit den bekannten Tools bestimmen kann? (Anzahl der atomare Instruktionen und diese irgendwie gewichtet) - um eine Hardware unabhängig Aussage treffen zu können ob Code A oder Code B.

    Knuths MMIX. 🙂
    Aber ist schon ok so.

    jb schrieb:

    (c) Ändert doch die Umlaute zu ae, oe und ue, wie sz zu ss. Dann sollten eure Implementierungen doch wieder gehen!?

    Benutze gerade einen fremden Lappy mit USB-Stick als Hauptpartition und Foto-Karte als Auslagerungsdatei. Beim Buchstaben 'm' einer großen wordlist ist der Rechner isn threashing gekommen und quasi stehengeblieben. Da muss man sich halt dann auf die Problemgröße einigen.

    0
  • ?

    @volkard: hier das file:
    https://gist.githubusercontent.com/Arnold1/0d1db8d917ed1c782ba1/raw/9d0034b5883e17ec505a8711473618e9ab65ca9d/words.txt

    ich hab meinen algo noch etwas optimiert:
    http://ideone.com/WLZMOI

    0
  • V

    antidisestablishmentarianisms?

    0
  • V

    Meine Zeiten:
    std::string und std:set 0.340
    std::string und std:unordered_set 0.206
    std::string und Trie 0.129
    ForeignString und std:set 0.258
    ForeignString und std:unordered_set 0.163
    ForeignString und Trie 0.118 (0.101 wenn ich bool und Zeiger zusammenpresse) (0.271 mit fanout von 256 satt 26)

    Deine Zeit:
    0.171

    0
  • ?

    @Volkard: sieht gut aus. richtiges wort!

    welche einheiten sind das?

    0
  • V

    algoman schrieb:

    welche einheiten sind das?

    Sekunden.

    0
Anmelden zum Antworten