Algo in c++ optimieren



  • @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...



  • Ich trau keiner Messung ohne -O3.

    Ja, get_prefixes ist da ein wenig unglücklich. Deine Implementiertung mit den std::strings dürfte ordentlich kosten. Und überhaupt, wozu get_prefixes? Man könnte einfach alle möglichen prefixes generieren und zu jedem dann den Trie fragen, ob dieses prerfix terminal ist. Also zu "ratman" ganz stumpf "r", "ra", "rat", "ratm", "ratma" testen. Und dann ist der Trie nur noch eine unordered_set. Sind am Ende zwar mehr Operationen, aber vielleicht sind die billiger.

    Wobei die erst richtig billiger werden, wenn nicht pro Versuch ein std::string erzeugt werden muss. new/delete sind schon recht teure Operationen. Die strings wirste zum Bleistift so los, wenn Du magst:

    class ForeignString{
    	//Besitzlose String-Views in fremden Speicher.
    	//Eigentlich für geparste XML-Elemente in file mappings
    	//und ähnlichen Schmodder; brachte mit mal Einlesezeit
    	//von 15s statt der Konkurrenz 10min. Das Zweckentfremden
    	//für String-Literale ist irgendwie naheliegend.
    
    	//Für diese Aufgabe völlig unnötig, nullterminierte Strings
    	//gingen auch prima. Mal einfach so reingemacht, um zukünftige
    	//Konzepte zu üben.
    	char const* _begin;
    	char const* _end;
    public:
    	ForeignString(char const* begin,char const* end)
    	:_begin(begin)
    	,_end(end){
    	}
    	char const* begin() const{
    		return _begin;
    	}
    	char const* end() const{
    		return _end;
    	}
    	friend ostream& operator<<(ostream& out,ForeignString fs){
    		return out.write(fs.begin(),fs.end()-fs.begin());
    	}
    	//Demnächst in Ihrem Compiler!!!
    	//http://en.cppreference.com/w/cpp/experimental/basic_string_view
    };
    
    //string literal
    #define SL(str) ForeignString((str),(str)+sizeof(str)-1)
    
    ForeignString wordsArray[]={
    	SL("ratcatdogcat"),
    	SL("cat"),
    	SL("cats"),
    	SL("catsdogcats"),
    	SL("catxdogcatsrat"),
    	SL("dogcatsdog"),
    	SL("hippopotamuses"),
    	SL("rat"),
    	SL("dog"),
    	SL("ratcat"),
    	SL("ratcatdog"),
    }
    

    Später beim Laden der 260k Wörter von Platte, am schnellsten die Datei per mmap anschauen und nur ForeignStrings anlegen, die in den gemapten Speicher zeigen. Dann brauchste auch diese 260k new-Aufrufe nicht. Falls das erstmal zu kompliziert ist, einfach 260k std::strings in einen std::vector einlesen und dann zu jedem std::string einen ForeignString in den Trie schubsen.

    Nuja, die Schnittstelle des Tries ändert sich ein wenig, aber der Code fast gar nicht.

    class trie
    {
    ...
    	void insert(char const* begin,char const* end){
    ...
    		for(char const* pos=begin;pos!=end;++pos){
    ...
    	template<typename T>
    	void insert(T const& t){
    		insert(t.begin(),t.end());
    	}
    

    Oder sogar

    //void insert(char const* begin,char const* end){
    	//template<typename iter>
    	void insert(iter begin,iter end){
    

    und man kann die von Datei gelesenen std::strings direkt reinwerfen. Und trotzdem woanders mit ForeignStrings arbeiten.

    bool is_compound_word(string candidate, int &count) {
    		bool found = false;
    		auto prefixes = t.get_prefixes(candidate);
    		for (auto prefix: prefixes) {
    

    [/code]
    würde zu

    bool is_compound_word(string candidate, int &count) {
    		bool found = false;
    		auto prefixes = t.get_prefixes(candidate);
    		for (auto candpos: candidate) {//oder so ähnlich
    			prefix=ForeingString(candidate.begin(),candpos);//char const*
    			postfix=ForegnString(candpos,candidate.end());//eigentlich
    

    Darum gehts mir bei den ForeingStrings. Ich kann sie unglaublich preiswert weiter zerlegen.

    Jo, dann hätte ich zum Trie noch kleine Ideen:

    class trie
    {
    private:
    	//node *root;
    	node root;
    	...
    		//node *tmp = root;
    		node *tmp = &root;
    

    Und was mich an meinem sofort störte war

    node *next[ALPHABET_SIZE];
    	bool is_terminal;
    

    nebst der Tatsache, daß in einem Wörterbuch unglaublich viele Wörter terminal sind und alle terminalen im Trie noch 26 Zeiger Platz fressen.
    Das hab ich geändert zu

    node *next_node[ALPHABET_SIZE];
    	bool next_is_terminal[ALPHABET_SIZE];
    

    , genial oder? Nee, wenn Du anläßlich dieser Änderung nicht vor Begeisterung um den Tisch tanzt, kann ich das nachvollziehen. Die Änderung würde ich lieber noch mit der Stoppuhr bestätigen lassen. Mir ging es halt drum, bei sehr großem Wörterbuch, daß nicht so viele Zugriffe ins langsame RAM passieren, und mehr Treffer im schnellen Cache kommen.
    Aber da war doch noch so ein uralter Trick, der sich jetzt gerade mal anbietet. Die Node-Adressen sind auf Deinem Rechner doch eh alle durch 4 teilbar, also haben die beiden letzten Bits immer auf 0, da kannste doch mal das letzte Bit selber benutzen.

    static_assert(align_of(*this)>1);
    	node *next_node_bitor_next_is_terminal[ALPHABET_SIZE];
    ...
    		//if(next_is_terminal)
    		//if(reinterpret_cast<int_ptr>(next_node_bitor_next_is_terminal)&1)
    

    Und um an next_node ranzukommen &~1 machen.

    Und dann den Trie vermutlich gut einlagern und hier gar nicht benutzen. Weil nämlich es um die Speicherzugriffe nur noch geht, nachdem wir std::string in Rente geschickt haben. Und da gibt es schnellere Strukturen als den Trie. Hasttables (unordered maps).

    Zwei Beschleunigungen drängen sich mir auf.

    - a) Den hash gleich beim Erzeugen der prefixes mitberechnen, statt nachher.
    Also statt

    for (auto candpos: candidate) {//oder so ähnlich
    			prefix=ForeingString(candidate.begin(),candpos);//char const*
    			//Hashwertberechnung herausgelöst, keine 
    			//eigene funktion mehr und auch nicht in 
    			//has aufgerufen
    			uint32_t prefix_hash=17;
    			for(auto ch:prefix)
    				prefix_hash=prefix_hash*31+static_cast<unsigned_char)(ch);
    			if(hashtable.has(prefix,preifix_hash)
    

    würde zu

    uint32_t prefix_hash=17;
    		for (auto candpos: candidate) {//oder so ähnlich
    			prefix=ForeingString(candidate.begin(),candpos);//char const*
    			prefix_hash=prefix_hash*31+static_cast<unsigned_char>(*candpos));
    			if(hashtable.has(prefix,preifix_hash)
    

    Das mit dem =17 und *31 ist geraten, müßte im Internet nach besseren Vorschlägen für string hashfunktionen suchen.

    - b) (Hab jetzt vergessen, was ich sagen wollte. Na, dann sag ich was anderes, um die Lücke zu füllen.) Also ich denke gerne immer gleich an ne cuckoo hashtable. Die hat nur während des Einlesens der Strings möglicherweise Stress. Aber beim späteren Abfragen, garantiert höchstens zwei RAM-Zugriffe pro has(). Naja, ich rechne mal damit, daß zehnmal so viele has()- als insert()-Aufrufe passieren. Ups, bei Dir heißt has() find(). Zehnmal ist nicht viel, ne normale mit doppeltem hashing hat durchschnittlich zwei Zugriffe, die std::unordered_set steht meinen Messungen nach einer mit doppeltem hashing nicht nach. Welche da am schnellsten ist, kann ich ohne Messung nicht abschätzen. Mist, std::unordered_set scheint nicht so einfach anzubieten, daß man den hashwert extern berechnet. Sowas ist immer doof an Standard-Containern. Sie reichen nur für den Berufsalltag aus. Aber will man im Hobby mal ein wenig außergewöhnliche Performance haben, geht ihnen schnell die Puste aus.



  • @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.



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

    was meinst du?



  • 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?



  • 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



  • 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.





  • antidisestablishmentarianisms?



  • 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


Anmelden zum Antworten