wpc112

[volkard]

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?

[Geo]

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.

[fan]

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

[Headhunter]

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?

[Geo]

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.

[Michael E.]

Headhunter: 2 ist richtig.

[Michael E.]

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).

[volkard]

0 ist richtig.
die (enorm kurze) linie von 3 bis 3 überdeckt kein einziges centimeterchen!
es ist nix.

[Michael E.]

2 ist richtig. Es ist nirgendwo die Rede von Strecken, sondern von Segmenten, zu denen IMHO auch Punkte gehören.

[Geo]

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;
}

[volkard]

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.

[volkard]

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.

[Michael E.]

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).

[Headhunter]

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

[volkard]

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.

[Christoph]

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...

[_DennisB_]

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

[volkard]

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.

[SideWinder]

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

[SG1]

111 ging ja auch um "brevity", da bringt loop-unrolling recht wenig...