WPC... geht weiter! -> wpc12
-
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.
-
Joah, das wird wohl ein knappes Rennen. Habe eure Algorithmen auch mal auf meinem Rechner kurz getestet bis hoch zu 10 Mio. (allerdings nur grob, also nur 100 Durchläufe und davon den Durchschnitt, bei der Knappheit ist das natürlich sehr ungenau). Danach lagen volkard und TomasRiker gleichauf bei ca. 210ms, ponto mit 250ms dahinter (im Falle, dass Exceptions geworfen werden, war er aber gleichauf), und mein eigener in der letzten korrekt funktionierenden Version mit 500ms weit abgeschlagen
Natürlich ist mein Rechner auch ziemlich konträr zu Jesters Testrechner, bin mal auf die Resultate dort gespannt...
-
kwaart schrieb:
Natürlich ist mein Rechner auch ziemlich konträr zu Jesters Testrechner, bin mal auf die Resultate dort gespannt...
ich auch. bei ramtakt 75MHz und prozessortakt 475MHz scheint jeder ramzugriff wirklich wirklich teuer und ponto gewinnt noch.
-
Bei mir sieht's ziemlich ähnlich aus.
volkard und ThomasRiker wechseln sich immer mal ab, ponto ist meist etwas langsamer als beide. kwaart ist ein gutes Stück langsamer, edx fliegt noch lange vorher raus, er zieht nämlich Kopien von der Eingabe. Das ist schnell zu teuer.
Im Moment schaue ich mal wer in 20 Sekunden die größte Lichterkette knackt. Wenn mir das Ergebnis danach zu knapp ist (das wird es vermutlich bei volkard und ThomasRiker), dann werde ich bei denen wohl mal den Schnitt über 100 große Lichterketten nehmen oder so. Irgendwie muß ich mich ja entscheiden.
Btw.: volkard: mit was machst Du diese tollen Grafiken?
-
Jo Ponto ist grad bei ner 120Mio-Kette rausgeflogen.
-
Ich hab hier auch mal Läufe gemacht in 1.000.002 Schritten bis 100.000.000. Alles auf einem P4 mit 2.4GHz und 256RAM, keinen Swap. Der Compiler ist g++ (GCC) 4.0.0 20050220 und compiliert wurde mit g++ -O3 -march=pentium4.
Es werden zwei Arten von Lösungen verglichen. Einerseits ist State1 und State2 identisch, so dass die Lösung leer sein muss. Andererseits erreicht man State2 nur durch umstellen aller Schalter.
Es zeigt sich, dass TomasRikers und Volkards Algorithmen schnell die Puste ausgeht. Komischerweise ist auf meiner Maschine meiner auch schneller. Vielleicht hätte ich eher auf den Celeron optimieren sollen.
Hier die Ergebnisse: http://www.pontohonk.de/wpc/lauf.html
-
@Ponto:
Das muss ja ewig gedauert haben, diese Tabelle zu generieren.
Allerdings darfst Du nicht vergessen, dass das nur ganz spezielle und seltene Fälle sind@Jester:
Wenn man es sich leicht machen will, nimmt man einfach die Kürze des Codes als Bewertungskriterium. Vor allem kann man dann 100%ig objektiv sein und kann definitiv sagen, wer der Gewinner ist.
