wpc112
-
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.
-
Ich mache mir keinerlei Hoffnungen, beim Wettbewerb eine Chance zu haben. Ich habe meine Lösung (oder besser gesagt, eine meiner Lösungen) hierhin gestellt, um mal von den Profis zu erfahren, was man noch besser machen könnte (natürlich nur Anfängeroptimierungen, ist ja klar, dass keiner hier seine Tricks vor Einsendeschluss verraten will).
-
Geo:
Dein Programm crasht bei mir.
Ich benutze den gcc3.3 unter linux.
Auf anderen PCs mit gleicher Compilerversion läufts aber.Wieso bei mir nicht?
Viele Grüße
-
Headhunter schrieb:
Dein Programm crasht bei mir.
geos korrekter code crasht bei meinem falschen testprogramm. es crasht bei n==0. laut aufgabenstellung ist n aber immer positiv, was vermutlich n!=0 impliziert. ansonsten liefert immer das gleiche ergebnis, wie meine (20% schnellere) implementierung.
> what is the output for {(10,10)}? > in other words: will a zero-length line segment be visible? I discussed the matter with the panel. If there is any confusion regarding that sort of inputs, we might exclude such cases from the test sets. And that message from the panel indicates that there is some confusion. Sorry for the error on our part. neway nice of you to get back to us asking about the same.
-
MaSTaH schrieb:
Do not use loop unrolling as well.
Hmpf, was für eine blöde Regel ist das bitte?
Der winnercode des wpc111 benutzte loop-unrolling mit Hilfe des Präprozessors. Wenn ich das geahnt hätte, dass die sowas durchgehen lassen...
-
Stand das auh beim wpc111 dabei? ich bin mir nicht mehr ganz sicher.
Für dieses wpc ist auf jeden Fall klar, dass man damit sowieso nicht viel anfangen kann
__
Grüße, DennisB
-
cd9000 schrieb:
Der winnercode des wpc111 benutzte loop-unrolling mit Hilfe des Präprozessors. Wenn ich das geahnt hätte, dass die sowas durchgehen lassen...
ich sehe nur den winning code von wpc110.
-
volkard schrieb:
cd9000 schrieb:
Der winnercode des wpc111 benutzte loop-unrolling mit Hilfe des Präprozessors. Wenn ich das geahnt hätte, dass die sowas durchgehen lassen...
ich sehe nur den winning code von wpc110.
Me 2
MfG SideWinder