Algo in c++ optimieren

volkard

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?

volkard

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?

__jb__

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

volkard

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.

@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

volkard

antidisestablishmentarianisms?

volkard

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

@Volkard: sieht gut aus. richtiges wort!

welche einheiten sind das?

volkard

algoman schrieb:

welche einheiten sind das?

Sekunden.