Wörterbuch mit C++ selbst erstellen



  • Danke für deine Antwort.

    Das Ganze, wie du es beschreibst, hat im Prinzip schon funktioniert, ich habe es einfach z.T. ein bisschen anders gelöst.

    Es wird aber eben für den 2. Schritt wichtig, dass ich diesen Baum erstellen und exportieren kann.

    Denn: Habe ich 12 Buchstaben zur verfügung und soll ein Wort mit 8 Zeichen daraus bilden --> gibt das (12!)/(4!) = ca. 20 Mio. Kombinationsmöglichkeiten.
    Diese alle zu speichern und danach jedes Wort zu überprüfen dauert ne Zeit.

    Die Wortkombinationen werden übrigens mit Backtracking gebildet.
    So kann ich dann mit diesem Baum-Wörterbuch (aus dem 2. Schritt) direkt erkennen, dass es keine Wörter gibt, die z.B. mit "XP...." beginnen gibt und somit viele Möglichkeiten ausschliessen.

    Wie gesagt, wie sinnvoll das ganze ist, da lässt sich streiten darüber, es geht nur darum, eine Übung zu machen....

    Das einzige, was ich wirklich wissen möchte ist:
    Wie kann ich ein gebildetes Array, einen gefüllten Baum, oder eine sonstige komplexe Datenstruktur exportieren, um sie in einem anderen Programm verfügbar zu haben, ohne sie jedes mal neu bilden zu müssen?

    Edit: Das war jetzt die Antwort auf deinen Vorposter, da war ich schon am schreiben.
    Die Datenstruktur erstell ich mir zur Not selbst, sollte kein allzu grosses Problem sein.
    Ich möchte wirklich nur wissen, ob es möglich ist, so eine fertige Struktur zu exportieren und falls ja, wie.



  • Wohl garnicht. Außer du legst deine komplette Datenstruktur darauf aus indem sie nur Speicher aus einem eigenen Pool bezieht, keine Zeiger sondern Offsets in diesen Pool verwendet und nur primitive Datentypen speichert. Kurz: Es ist das nicht wert.

    So wäre es mit std::unordered_set wohl am Besten gelöst:

    std::unordered_set<std::string> wordlist;
    fuellen(worldlist);
    
    std::ofstream out("woerterliste.txt");
    for(std::string& s : wordlist)
        out << s << '\n';
    
    ....
    
    std::unordered_set<std::string> wordlist2;
    std::ifstream in("woerterliste.txt");
    std::string cur;
    while(in >> cur)
        wordlist2.insert(cur);
    


  • Hab mal nen kleinen Test geschrieben:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <unordered_set>
    #include <chrono>
    #include <random>
    using namespace std;
    
    unsigned const N_WORDS = 20000000;
    unsigned const WORD_LEN = 8;
    
    vector<string> makeRandomWords()
    {
    	mt19937 gen(time(nullptr));
    	uniform_int_distribution<char> dis('a', 'z');
    
    	vector<string> result;
    	for(unsigned i = 0; i < N_WORDS; ++i)
    	{
    		string curWord;
    		for(unsigned j = 0; j < WORD_LEN; ++j)
    			curWord.push_back(dis(gen));
    		result.push_back(move(curWord));
    	}
    
    	return result;
    }
    
    int main()
    {
    	auto words = makeRandomWords();
    
    	unordered_set<string> wordlist;
    	wordlist.reserve(words.size());
    
    	{
    		unordered_set<string> wordlistNoReserve;
    
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			wordlistNoReserve.emplace(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Inserting " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word) (without reserve)\n";
    	}
    
    	{
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			wordlist.emplace(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Inserting " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word) (with reserve)\n";
    	}
    
    	{
    		size_t antiOptimize = 0;
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			antiOptimize += wordlist.count(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Looking up " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word)" << antiOptimize << "\n";
    	}
    }
    

    Das Ergebnis ist bei mir:

    Inserting 20000000 words took 8092ms (Avarage 404ns per word) (without reserve)
    Inserting 20000000 words took 4769ms (Avarage 238ns per word) (with reserve)
    Looking up 20000000 words took 3351ms (Avarage 167ns per word)

    Bist du dir sicher dass 167 Nanosekunden Prüfzeit ovb ein Wort gültig ist zu langsam sind?



  • Woohoa Computer sind shcon geil schnell 😃 🕶



  • gut, dann habe ich das ganze wohl überschätzt. 🙄

    aber liege ich mit meiner Annahme richtig, dass die zweite Variante (mit dem Buchstabenbaum) schneller wäre, zumal sogar bereits beim bilden der Kombinationen grosse Mengen ausgeschlossen werden könnten?

    Danke für eure Hilfe und Anregungen.



  • Schneller als was? Schneller als eine Hashtable (std::unordered_set) ? Vermutlich nicht, die Hashtable macht wortweise etwas Arithmetik/Bitschubserei auf den String und weiß dann im Regelfall direkt ob der String im Set ist.

    Schneller als ein Binärbaum? Möglicherweise. Du hast sehr wenige Schritte beim Lookup dafür hat dein Buchstabenbaum den Nachteil viel Speicher zu verschwenden wenn viele Zweige ungenutzt sind (zb. "test" allein verbraucht etwa 4 * 26 * sizeof(void*) Bytes = 832 Byte bei 64bit), das ist Gift für den Cache. Wenn da viele Cachemisses auftreten kann das schnell langsamer werden. Wenn der Baum hingegen prall gefüllt ist dann ist das wohl schneller als ein Binärbaum.



  • stimmt, das hatte ich nicht bedacht 🙄
    auch wenn die Zeiger nirgends hinzeigen brauchen sie ja Platz...
    Danke für die Mühe.



  • Habe es mal probiert, mir ist beim erstellen erstmal halb der Rechner eingefroren (wohl weil ordentlich geswappt werden musste, 8GB, SSD) und dann war es etwa 3x langsamer als die std::unordered_map.

    Aber immer noch besser als die std::map (Binärbaum, genauer gesagt R/B-Tree), da war der Lookup 13x langsamer.


  • Mod

    Wie viele Datensätze? Selbst mit allen Beugungen wirst du im Deutschen nicht auf > 100,000 Wörter kommen, außer du zählst die hundertausenden von Fachwörtern hinzu, die hier wohl nicht gefragt sind.



  • Naja, bei diesem Spiel können auch glaube ich Eigennamen dazukommen. Aber laut Wikipedia zählt die Standardsprache ~70000 Worte, während sich diese zahl auf bis zu 500000 erhöhen kann, je nach Fachrichtung und Tiefe.

    Quelle


Anmelden zum Antworten