WPC... geht weiter! -> wpc12
-
Jester schrieb:
Kannst Du bei 1000002 Lichtern durch Messung rausfinden ob ne Excpetion fliegt?
Und bei 100000002?Da kann gar keine Exception geworfen werden
Es sei denn der Algorithmus ist fehlerhaft.
Selbst wenn Exceptions viel Zeit brauchen sollten, so ist es letztendlich doch egal, weil jeder der Teilnehmer in diesem Fall eine Exception werfen muss, also gleiche Bedingungen für alle.
-
Stimmt.
Da kann nix fliegen. Aber ich wollte ja nix verraten.
Wie auch immer, ich denke nicht, daß es meßbar ist wenn eine fliegt.MfG Jester
-
Nein, bei eingeschalteten Compileroptimierungen kann ich es nicht messen, habe mich da geirrt. Ohne Optimierungen schon, aber da ist der ganze Algorithmus sowieso deutlich langsamer, dass es schon wieder egal wäre
-
Ich hab mal die verschiedenen Versionen des Algorithmus mit verschiedenen Compilern und auf verschiedenen Rechnern getestet. Dabei ist das nicht besonders überraschende Ergebnis herausgekommen, dass je nach Compiler, Compileroptionen und Rechnerarchitektur eine andere Version die schnellste ist. Etwas überrascht hat mit dagegen, dass jede Version des Algorithmus, die bei einer Konstellation die schnellste ist, bei einer anderen Konstellation die langsamste ist.
Deshalb frage ich mal, welcher Compiler in welcher Version wird verwendet und welche Compileroptionen werden genutzt?
Zum Beispiel ist es auf einem Celeron wesentlich, ob man g++ -march=pentium3 -O3 oder nur g++ -O3 benutzt.
-
ich hatte eigentlich daran gedacht nur -O3 zu benutzen. Wäre das okay?
-
Jester schrieb:
ich hatte eigentlich daran gedacht nur -O3 zu benutzen. Wäre das okay?
Das zu deiner Maschine zugehörige -march= wäre besser. Zumindest meiner Meinung nach. Du sparst dann auch Zeit beim Testen, da die Programme schneller laufen.
-
Was genau gehört zu nem Celeron? Pentium II?
Wegen mir auch das.btw.: Ponto, hast Du meine Mail bekommen?
-
Jester schrieb:
Was genau gehört zu nem Celeron? Pentium II?
Wegen mir auch das.ich schau für sowas auf sowas wie http://gentoo-wiki.com/Safe_Cflags
ich schätze, pentium2 ist genau die richtige march.
-
Jester schrieb:
Was genau gehört zu nem Celeron? Pentium II?
Wegen mir auch das.btw.: Ponto, hast Du meine Mail bekommen?
Zu einem Celeron gehört soweit ich weiss -march=pentium3 Aber auch -march=pentium2 macht keinen Unterschied, zumindest nicht auf meinem Celeron 600.
Die Mail hab ich bekommen und eine korrigierte Version wird bald zugeschickt.
-
Okay, gut.
werden dann -march=pentium2 verwenden, das scheint zu meinem Celeron zu passen. Ist auch ein alter Celeron, kein neuer. Als ich denk gekauft hab gab's glaub noch garkeinen P3.
-
Jester schrieb:
Okay, gut.
werden dann -march=pentium2 verwenden, das scheint zu meinem Celeron zu passen. Ist auch ein alter Celeron, kein neuer. Als ich denk gekauft hab gab's glaub noch garkeinen P3.
Bleibt mir nur noch zu sagen, dass die 3.4 Reihe der GCC schlecht optimiert und jede andere Reihe besser ist.
-
Ich werden den gcc verwenden, der bei meinem Dev-Cpp dabei ist. Hab keine Lust dafür jetzt noch was anderes zu installieren. Wenn es was 3.4.x-mäßiges ist, dann habt ihr halt Pech gehabt.
Aber es haben ja alle die gleiche Chance.
-
Wann kann man Ergebnisse erwarten?
-
-
Ergebnisse des speed-tests wird's voraussichtlich morgen abend geben.
MfG Jester
-
lol
eViLiSSiMo schrieb:
Zuletzt bearbeitet von eViLiSSiMo am 19:16:42 12.03.2005, insgesamt 5-mal bearbeitet
-
Falls jemand selbst vergleichen möchte. Hier ist meine eingesandte Routine:
-
Heh, die schlägt meine letzte, zu hoch optimierte Version noch um fast 10ms bei Lichterketten der Länge 1 Mio.. Selbst wenn meine Variante korrekt gearbeitet hätte, wäre ich hier ziemlich aus dem Rennen gewesen
-
Mein Code (braucht bei mir, Athlon XP 3000+, 240 ms für 10 Millionen Lichter, während der von Ponto 460 ms braucht ;)):
vector<size_t> wpc12(vector<bool>& state1, vector<bool>& state2) { const size_t size = state1.size(); const size_t modulo = (size - 2) % 3; char* p_buttons = new char[size]; memset(p_buttons, 0, size * sizeof(p_buttons[0])); // Wir probieren es mit der Variante, den ersten Knopf nicht zu drücken. size_t button = 0; vector<bool>::const_iterator s1 = state1.begin(); vector<bool>::const_iterator s2 = state2.begin(); char* b = p_buttons; int diff = *s1 != *s2; s1++; s2++; int nextDiff = *s1 != *s2; // Lösungsvektor vorbereiten vector<size_t> result; result.reserve(size); while(button < size - 1) { button++; s1++; s2++; b++; if(diff) { // Der nächste Knopf muss gedrückt werden, da der Zustand // der aktuellen Glühbirne nicht stimmt. diff = !nextDiff; nextDiff = *s1 == *s2; *b = 1; result.push_back(button); } else { // Der nächste Knopf muss nicht gedrückt werden. diff = nextDiff; nextDiff = *s1 != *s2; } } // Hat der Ansatz zum Erfolg geführt? if(!diff) { if(modulo) return result; else { // Es gibt auf jeden Fall zwei Lösungen, wovon wir eine haben. // Nun müssen wir die Kürzere von beiden finden. // Dazu zählen wir die Anzahl der gedrückten Knöpfe für diese Lösung. // Knöpfe mit einem Index 3*n+2 sind in beiden Lösungen gleich und // werden darum gesondert behandelt. size_t numImportantButtons = 0; const size_t numUnimportantButtons = size / 3; b = p_buttons; size_t i = 0; while(i < size - 2) { if(*(b++)) numImportantButtons++; if(*(b++)) numImportantButtons++; b++; i += 3; } // die übrigen beiden Knöpfe zählen if(*(b++)) numImportantButtons++; if(*b) numImportantButtons++; const size_t maxImportantButtons = size - numUnimportantButtons; if(numImportantButtons * 2 <= maxImportantButtons) { // Die gefundene Lösung ist die Kürzere. delete[] p_buttons; return result; } else { // Die andere Lösung ist die Kürzere. result.clear(); b = p_buttons; size_t i = 0; while(i < size - 2) { // zwei Knöpfe vertauschen, einen übernehmen if(!*(b++)) result.push_back(i); i++; if(!*(b++)) result.push_back(i); i++; if(*(b++)) result.push_back(i); i++; } // übrige Knöpfe verarbeiten if(!*(b++)) result.push_back(i); i++; if(!*b) result.push_back(i); delete[] p_buttons; return result; } } } else { if(modulo) { // Der Ansatz hat nicht zum Erfolg geführt. // Es muss also die andere Lösung sein. result.clear(); b = p_buttons; size_t i = 0; while(i < size - 2) { // zwei Knöpfe vertauschen, einen übernehmen if(!*(b++)) result.push_back(i); i++; if(!*(b++)) result.push_back(i); i++; if(*(b++)) result.push_back(i); i++; } // Ist noch ein Knopf übrig? if(modulo == 2 && !*b) result.push_back(i); delete[] p_buttons; return result; } else { delete[] p_buttons; throw Unsolvable(); } } }
-
TomasRiker schrieb:
Mein Code (braucht bei mir, Athlon XP 3000+, 240 ms für 10 Millionen Lichter, während der von Ponto 460 ms braucht ;)):
...Bei mir ist die Differenz etwas weniger:
20000000 Lampen und es gibt keine Exception:
Ponto: 742 ms
TomasRiker: 660 ms
20000000 Lampen und es gibt eine Exception:
Ponto: 411 ms
TomasRiker: 517 msIch hatte am Anfang eine ähnliche Version wie du, habe mich dann aber gegen den Overhead entschieden und Laufzeit geopfert um bis zum Schluss skalieren zu können. Dein Code legt immer zwei Arrays der Länge size * (1 + sizeof(size_t)) an (p_Buttons und result.reserve()), selbst wenn das Ergebnis eine Exception ist oder nur aus wenigen Lampen besteht. Wenn Jester ans Ende seines Speichers kommt, kann hier schneller Schicht im Schacht sein.