WPC... geht weiter! -> wpc12
-
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.
-
na, dann zeige ich meine auch mal.
#include "wpc12.h" #include <vector> #include <algorithm> using namespace std; const char* getName() {return "volkard";} const char* getMail() {return "volkard@normannia.de";} vector<size_t> wpc12(vector<bool>& state1,vector<bool>& state2){ //setup RVO, es wird auf jeden fall result1 zurückgegeben. leider //rechne ich damit, daß der compiler die funktion nicht sehen wird //und RVO nicht machen kann. naja, kosten mit denen alle zu leben haben. //Jester wird wissen, daß er keinen inlinen darf, wenn er einen outlined. vector<size_t> result1; //result2 speichert die schlechtere lösung vector<size_t> result2; //ich berechne beide lösungen in einem durchlauf, indem ich die beiden //schleifen kombiniere. //größe merken size_t const size=state1.size(); //speicher reservieren. ich reserviere vorsichtshalber hier viel, denn //umkopieren braucht viel zeit. aber speicher, der reserviert und nicht //angerührt wird, ist kostenlos. result1.reserve(size); result2.reserve(size); //iterator sicherlich schneller als op[] vector<bool>::const_iterator i1=state1.begin(); vector<bool>::const_iterator i2=state2.begin(); //der schalter, der nicht mehr untersucht werden darf size_t const ende=size-1; //ich brauche gar nicht auf den eingangs-arrays zu arbeiten. //ich muss nur immer 3 bits sehen, die stopfe ich in einen int. unsigned int mask1=*i1++^*i2++; mask1=(mask1<<1)|(*i1++^*i2++); //ich habe darauf verzichtet, genau zu untersuchen, ob ich die kleinen drei //oder die grossen drei bist nehmen soll. die grossen drei klingen lecker, weil //dann das abzufragende bit das vorzeichenbit ist und eh nach der letzen //operation in einem flag steht. andererseits scheint das reinshiften auf position //29 teuer genug, daß ich nicht entscheiden kann. und ich hatte keine lust, zu messen. size_t schalter=0; for(;;){ //die schleife ist ganz leicht geunrolled, um auszunutzen, daß die //schalterstellungen der beiden lösungen sich bei schalter n*3+2 stets //gleichen und bei anderen schaltern unterscheiden //ist auch fein im forum nachzulesen, vielleicht sollte ich mich gerade mal //hauen, weil ich es verraten habe. //das spart, mask2 mitführen zu müssen und ein paar vergleiche. //n*3+0 if(mask1&4){ mask1^=7; result1.push_back(schalter); } else{ result2.push_back(schalter); } ++schalter; if(schalter==ende) break; mask1=(mask1<<1)|(*i1++^*i2++); //n*3+1 if(mask1&4){ mask1^=7; result1.push_back(schalter); } else{ result2.push_back(schalter); } ++schalter; if(schalter==ende) break; mask1=(mask1<<1)|(*i1++^*i2++); //n*3+2 if(mask1&4){ mask1^=7; result1.push_back(schalter); result2.push_back(schalter); } ++schalter; if(schalter==ende) break; mask1=(mask1<<1)|(*i1++^*i2++); } //die andere maske berechnen unsigned int mask2=mask1^((size%3)+1); //soll der letzte schalter noch gedrückt werden? if(mask1==3){ result1.push_back(schalter); mask1=0; } if(mask2==3){ result2.push_back(schalter); mask2=0; } //auswertung, welche meiner ergebnis-arrays zurückgegeben werden sollen if(mask1){ if(mask2){ //beide waren kacke throw Unsolvable(); } else{ //nur r2 war gut, ich tausche mit r1 result1.swap(result2); } } else{ if(mask2){ //nur r1 war gut } else{ //beide waren gut //ich nehme den kürzeren if(result1.size()<=result2.size()){ //r1 war kürzer } else{ //r2 war kürzer, ich tausche mit r1 result1.swap(result2); } } } return result1; }
-
[quote="Ponto"]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 ms
[/qoute]
ich hab mal ne menge mehr messpunkte genommen.http://www.volkard.de/wpc12.png
meine kurve ist recht stabil, TomasRiker ist ja nach eingangsvertoren mal drüber mal drunter. na, da hat Jester was zu tun, bestimmt werden sich noch andere lösungen in diesen bereich mischen, und so echt deutlich ist nicht zu erkennen, wer schneller ist.
dieses messprog:
#include <iostream> #include "wpc12.h" using namespace std; typedef unsigned long long u64; inline u64 rdtsc(){ u64 r; asm volatile( "rdtsc" :"=A" (r) ); return r; } vector<size_t> wpc12Ponto(vector<bool> & a,vector<bool> & b); vector<size_t> wpc12TomasRiker(vector<bool> & a,vector<bool> & b); vector<size_t> wpc12Volkard(vector<bool> & a,vector<bool> & b); size_t gr; u64 measure(vector<size_t> (*f)(vector<bool> & a,vector<bool> & b),size_t size){ u64 mintime=u64(-1); size_t initleft=10000/size+3; size_t left=initleft; while(--left){ srand(size); vector<bool> s1(size); vector<bool> s2(size); for(size_t i=0;i!=size;++i){ s1.push_back(rand()%2); s2.push_back(rand()%2); } u64 time=-rdtsc(); try{ gr=f(s1,s2).size(); }catch(Unsolvable){ } time+=rdtsc(); if(time<mintime){ mintime=time; left=initleft; } } return mintime; } int main(){ cout<<"Size\tPonto\tTomasRiker\tVolkard\n"; for(size_t size=3;size<1000000;size+=size/100+1){ cerr<<size<<'\r'; cout<<size<<'\t'; cout<<measure(&wpc12Ponto,size)<<'\t'; cout<<measure(&wpc12TomasRiker,size)<<'\t'; cout<<measure(&wpc12Volkard,size)<<'\t'; cout<<endl; } }für messungen bis 100.000.000 taugt das prog allerdings nix auf meinem lahmen rechner.
