wpc112
-
Für die dieswöchige Ausgabe gilt es für mich erst einmal einen Algorithmus zu finden, und volkard baut bereits die ASM-Optimierungen dafür.
Gilt es das hier zu optimieren?:
int wpc112(int *start, int *end, int n) { const int NOTHING = 0; // == Kein Start und kein Ende an dieser Position der X-Achse const int START = 1; // == Zumindest ein Start an dieser Position der X-Achse const int END = 2; // == Zumindest ein Ende an dieser Position der X-Achse const int BOTH = 3; // == Ein Start und ein Ende an dieser Position der X-Achse (=touch) int xachse [1000]; // == X-Achse (0-1000) /* X-Achse initialisieren */ for(int i = 0; i < 1001; ++i) xachse[i] = NOTHING; /* X-Achse mit Werten füllen */ for(i = 0; i < n; ++i) { /* Ist bereits ein END and dieser START-Position ein BOTH daraus machen */ if(xachse[start[i]] == END) xachse[start[i]] = BOTH; /* Ansonsten ein gewöhnliches START einfügen */ else xachse[start[i]] = START; /* Ist bereits ein START an dieser END-Position ein BOTH daraus machen */ if(xachse[end[i]] == START) xachse[end[i]] = BOTH; /* Ansonsten ein gewöhnliches END einfügen */ else xachse[end[i]] = END; } /* Zählt die derzeitige Startmarken - Endmarken. Ist diese Variable 0 ist derzeit kein Bereich aktiv, dH ein neues Segment hat begonnen */ int counter = 0; /* Zählt die Anzahl der gefundenen Segmente */ int segments = 0; /* Anzahl der Segmente zählen */ for(i = 0; i < 1000; ++i) { if(xachse[i] == NOTHING) continue; if(xachse[i] == START) ++counter; if(xachse[i] == END) --counter; if(counter==0) ++segments; } return(segments); }BTW: Jedes Mal wenn ich auf die AcmeSofties-Page gehe, schlägt mein Virenscanner an
MfG SideWinder
-
SideWinder schrieb:
Gilt es das hier zu optimieren?:
juhu. ne referenzimplementierung!
jetzt muss nur noch jemand das übliche messprogramm mit rdtsc drumstricken.nein, ich optimiere noch nicht auf assembler rum. ich hab nichteinmal den algo fertig eingetippt. aber wir brauchen halt ein messprogramm, wenn wir uns messen wollen.
ich hab leider wenig zeit diese woche und kümmere mich evtl sogar nur drum, ne unemessene lösung einzuschicken.
-
elise schrieb:
kannst du hiermit was anfangen?
super. thx.
-
Do not use loop unrolling as well.
Hmpf, was für eine blöde Regel ist das bitte?
-
volkard schrieb:
SideWinder schrieb:
Gilt es das hier zu optimieren?:
juhu. ne referenzimplementierung!
jetzt muss nur noch jemand das übliche messprogramm mit rdtsc drumstricken.nein, ich optimiere noch nicht auf assembler rum. ich hab nichteinmal den algo fertig eingetippt. aber wir brauchen halt ein messprogramm, wenn wir uns messen wollen.
ich hab leider wenig zeit diese woche und kümmere mich evtl sogar nur drum, ne unemessene lösung einzuschicken.Das dumme am Messen sind eben immer die verschiedenen Systeme, bei so kleinen Zeiten kann ein laufender Norton bereits den Ausschlag für eine Version geben.
Es müsste Programme geben die exklusiven Zugriff erhalten und die Zeit eines anderen Programms messen.
Apropos Messen: Hattest du nicht mal so eine tolle "Ich messe die Zeit"-Funktion/Klasse?
Achja, und wenn du jetzt g++ verwendest und ich MSVC können wir uns auch kaum messen, da der MSVC anders optimiert als der g++...
MfG SideWinder
-
SideWinder schrieb:
Das dumme am Messen sind eben immer die verschiedenen Systeme, bei so kleinen Zeiten kann ein laufender Norton bereits den Ausschlag für eine Version geben.
gerade bei so kleinen zeiten messe ich auf 6 stellen genau.
edit: mist, wo hab ich nur das messprogramm?
edit2: hier isses: http://forum.c-plusplus.net/viewtopic.php?t=70218&start=0der rumpf des messprogramms steht seit wpc60 oder so recht stabil. oder war das schon wpc37 (sehenswerte lösung)? es geht nur immer wieder darum, eine referenzimplementierung zu bauen (bereits geschehen) und nen testfallgenerator, der einigermaßen treffen könnte, was die softies messen werden (noch nicht geschehen).
Es müsste Programme geben die exklusiven Zugriff erhalten und die Zeit eines anderen Programms messen.
klappt nicht. die gerätetreiber und so sind einfach exklusiver als man jemals selber sein kann. aber zum glück nicht nötig. je kürzer die zu messende zeit, desto sicherer trifft man auch mal ne messung, wo echt kein anderer was macht.
Apropos Messen: Hattest du nicht mal so eine tolle "Ich messe die Zeit"-Funktion/Klasse?
jo. aber rdtsc ist hier vollauf genug.
Achja, und wenn du jetzt g++ verwendest und ich MSVC können wir uns auch kaum messen, da der MSVC anders optimiert als der g++...
viel schlimmer sind die auswirkunen unserer unterschiedlichen prozessoren. und doch macht es wenig genug aus, um einigermaßen vergleichbare zahlen zu kriegen.
allerdings ist doch eine schlimme sache dabei, rand() ist auf msvc ganz anders als auf gcc. zum heutigen messprogramm muß ne eigene implementierung von rand() gebaut werden und ab jetzt immer beim messprog dabei sein.
-
SideWinder schrieb:
Gilt es das hier zu optimieren?:
ich zweifle an deinem ergebnis für
580 796 281 798 589 798 9 157 472 622 292 538 38 179 190 657als referenz-implementierung hab ich mir einfallen lassen:
int wpc112ref(int *start, int *end, int n) { bool field[1000]={0}; for(int i=0;i<n;++i) for(int j=start[i];j<end[i];++j) field[j]=1; int result=0; int s=0; for(int i=0;i<1000;++i) if(field[i]!=s) { ++result; s=1-s; } return result/2; }uih, ist die lahm.
aber irgendwie glaubwürdig.
-
Hier ein kleines Testframework
typedef unsigned long long uint64_t; typedef unsigned int uint32_t; //GCC inline uint64_t rdtsc() { uint32_t high, low; __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high)); return ((uint64_t)high << 32) | low; } /* //MSVC inline uint64_t rdtsc() { uint64_t val; __asm { rdtsc lea ebx, val mov [ebx], eax mov [ebx+4], edx } return val; } */ int wpc112ref(int *start, int *end, int n) { bool field[1000]={0}; for(int i=0;i<n;++i) for(int j=start[i];j<end[i];++j) field[j]=1; int result=0; int s=0; for(int i=0;i<1000;++i) if(field[i]!=s) { ++result; s=1-s; } return result/2; } int wpc112(int *start, int *end, int n) { bool field[1000]={0}; for(int i=0;i<n;++i) for(int j=start[i];j<end[i];++j) field[j]=1; int result=0; int s=0; for(int i=0;i<1000;++i) if(field[i]!=s) { ++result; s=1-s; } return result/2; } #include <iostream> #include <ctime> #include <cstdlib> #include <vector> using namespace std; unsigned const times=10000; int main() { try { srand(static_cast<unsigned>(time(0))); uint64_t cycles=0; for(unsigned i=0; i<times; ++i) { int const count=rand()%1000+1; //1 - 1000 vector<int> start(count); vector<int> end(count); for(int j=0; j<count; ++j) { int a=rand()%1000+1; int b=rand()%1000+1; if(a<b) swap(a, b); start.push_back(a); end.push_back(b); } vector<int> start_copy(start); vector<int> end_copy(end); uint64_t rdtsc_start=rdtsc(); int res=wpc112(&start[0], &end[0], count); uint64_t rdtsc_end=rdtsc(); cycles+= (rdtsc_end-rdtsc_start); if(res!=wpc112ref(&start_copy[0], &end_copy[0], count)) throw "Error"; } cout<<times<<" Durchläufe brauchten "<<cycles<<" - Durchschnittlich: "<<static_cast<long double>(cycles)/times<<'\n'; return 0; } catch(char const* e) { cout<<e<<'\n'; return -1; } }
-
nur mit mingw getestet. mit msvc sind evtl noch ein paar handgriffe notwendig.
int wpc112(int *start, int *end, int n) { } int wpc112ref(int *start, int *end, int n) { bool field[1000]={0}; for(int i=0;i<n;++i) for(int j=start[i];j<end[i];++j) field[j]=1; int result=0; int s=0; for(int i=0;i<1000;++i) if(field[i]!=s) { ++result; s=1-s; } return result/2; } #include <cstdlib> #include <iostream> using namespace std; #ifdef __MSVC__ #define for if(false);else for typedef unsigned __int64 u64; #pragma warning(push) #pragma warning(disable:4035) u64 rdtsc() { __asm rdtsc; } #pragma warning(pop) #else typedef unsigned long long u64; inline u64 rdtsc() { unsigned int hi,lo; __asm__ __volatile__("rdtsc":"=a"(lo),"=d"(hi)); return (u64(hi)<<32)|lo; } #endif pair<u64,int> test(int seed,int wpc(int *start, int *end, int n)) { srand(seed); int n=rand()%10; int start[10]; int end[10]; for(int i=0;i<10;++i) { start[i]=rand()%1000; end[i]=rand()%1000; if(start[i]>end[i]) swap(start[i],end[i]); } u64 sta=rdtsc(); int r=wpc(start,end,n); u64 sto=rdtsc(); return make_pair(sto-sta,r); } int main() { cout<<"testing"<<endl; for(int seed=0;seed<10000;++seed) { int a=test(seed,wpc112ref).second; int b=test(seed,wpc112).second; if(a!=b) { cout<<"fehler bei "<<seed<<endl; return 1; } } cout<<"measuring"<<endl; int left=1000; u64 mintime=u64(-1); int s=0; while(left) { int s=0; u64 time=0; for(int seed=0;seed<1000;++seed) { pair<u64,int> p=test(seed,wpc112); s+=p.second; time+=p.first; } if(time<mintime) { mintime=time; left=1000; cout<<double(mintime)<<endl; } --left; } cout<<s<<endl; cout<<"speedup: "<<7481120/double(mintime)<<endl; return 0; }ich hab speedup 32. und ihr?
-
SideWinder schrieb:
BTW: Jedes Mal wenn ich auf die AcmeSofties-Page gehe, schlägt mein Virenscanner an
Ist wohl ein VBS/Redlof@M Virus. Die scheinen auf Hinweismails aber nicht zu reagieren, also Vorsicht und Scripting ausschalten.
-
for(int i=0;i<1000;++i)Kann es sein das hier ein Fehler ist?
So wie ich das sehe wird hier nicht bis segment tausend
sondern nur bis 999 gezählt!
Also meiner meinung nach folgend:for(int i=0;i<=1000;++i)(Kann auch falsch sein)
bye
-
fan schrieb:
for(int i=0;i<1000;++i)Kann es sein das hier ein Fehler ist?
So wie ich das sehe wird hier nicht bis segment tausend
sondern nur bis 999 gezählt!
[..]Die Analyse ist korrekt, die Diagnose falsch.
Arrays in C/C++ sind von 0..n-1, nicht wie in Pascal von 1..n.
Hat schon seine Richtigkeit
Aber was anderes:
Kann es sein dass entweder volkards oder Shades Referenzimpl falsch sind?int start[] = { 5,8 }; int end[] = { 5,8 }; cout << wpc112 (start, end, 2) << endl;Dies liefert verschiedene Werte zurück.
Einmal wars 0 und einmal 2.Ich denke 1 wäre ein korrekter Rückgabewert, was sagt ihr?
-
Der Ansatz ist schon grundfalsch
start[i] will always be less than or equal to end[i].
Der Fall equal wird von volkards Code nicht berücksichtigt.
-
Headhunter: 2 ist richtig.
-
Was haltet ihr von folgender Lösung?
void wpc112a(int *start, int *end, int n, int number) { ++number; while(number<n) { start[number-1]=start[number]; end[number-1]=end[number]; ++number; } } int wpc112(int *start, int *end, int n) { register int c1=0, c2=1; while(c1<n) { while(c2<n) { if( start[c1]>=start[c2] && start[c1]<=end[c2] || end[c1] >=start[c2] && end[c1] <=end[c2] || start[c2]>=start[c1] && start[c2]<=end[c1] || end[c2] >=start[c1] && end[c2] <=end[c1]) { if(start[c1]>start[c2]) start[c1]=start[c2]; if(end[c1]<end[c2]) end[c1]=end[c2]; wpc112a(start, end, n, c2); --n; } ++c2; } ++c1; c2=c1+1; } return n; }volkard: Mit deiner Testmethode komm ich an meinem Rechner auf 17 und an dem hier auf 24 (der hier ist komischerweise viel älter).
-
0 ist richtig.
die (enorm kurze) linie von 3 bis 3 überdeckt kein einziges centimeterchen!
es ist nix.
-
2 ist richtig. Es ist nirgendwo die Rede von Strecken, sondern von Segmenten, zu denen IMHO auch Punkte gehören.
-
unter der Annahme, dass Segmente auch ohne Ausdehnung sichtbar sind:
int wpc112(int *start, int *end, int n) { register unsigned int j; register int st, en, result = n; int *sptr, *eptr; for (;j = --n;) { // j: count of following elements st = *start++; // load 'start' of element to compare against following ones sptr = start; // pointer to 'start' of first following element en = *end++; // load 'end' of element to compare against following ones eptr = end; // pointer to 'end' of first following element do { if (st <= *eptr && en >= *sptr) { // is there an overlap? if yes, calc min/max to if (st < *sptr) *sptr = st; // merge the two elements to one segment and if (en > *eptr) *eptr = en; // replace the pair in the list result--; // so one segment less break; } sptr++; // points to 'start' of next following element eptr++; // points to 'end' of next following element } while (--j); // do for all following elements } return result; }
-
CME386 schrieb:
2 ist richtig. Es ist nirgendwo die Rede von Strecken, sondern von Segmenten, zu denen IMHO auch Punkte gehören.
in der tat ist diese auslegung denkbar. da hilft nur, die acme softies zu fragen.
-
CME386 schrieb:
Was haltet ihr von folgender Lösung?
die ist im vergleich zur referenzimplementierung beeindruckend schnell.
aber eigentlich war das nicht so gedacht, daß man die echt schnellen algos hier postet, sondern die den acme softies einschickt.