3. WPC... geht weiter! -> wpc12

WPC... geht weiter! -> wpc12

  • V

    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;
}
    0
  • V

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

    0
  • K

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

    0
  • V

    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.

    0
  • J

    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?

    0
  • J

    Jo Ponto ist grad bei ner 120Mio-Kette rausgeflogen.

    0
  • P

    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

    0
  • T

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

    0
  • P

    TomasRiker schrieb:

    @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 😉

    Die Zeiten sind Milisekunden, weshalb es nicht so lange gedauert hat. Hab jetzt einen Lauf eingefügt, wo immer eine Exception fliegt.

    0
  • M

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    void pressButton(const size_t button, vector<bool>& state){
    if(button > 0)
        state[button-1]=! state[button-1];
    state[button]=! state[button];
    if(button + 1 < state.size())
        state[button+1]=! state[button+1];
}

void wpc12_h(std::vector<bool> &state1, const std::vector<bool> & state2, vector<size_t> & actions) {

	size_t button = 1;

	for (; button < state1.size(); ++button) {
		if (state1[button - 1] != state2[button - 1]) {
			pressButton(button, state1);
			actions.push_back(button);
		}
	}

	if (state1[button - 1] != state2[button - 1]) {
		throw Unsolvable();
	}
}

std::vector<size_t> wpc12(const std::vector<bool> & state1, const std::vector<bool> & state2) {

	//probiere erstmal mit pressen
	vector<size_t> alternative1(state1.size()), alternative2(state1.size());
	bool alternative1Available = false;
	try {
		vector<bool> state1Pressed(state1);
		pressButton(0, state1Pressed);
		alternative1.push_back(0);
		wpc12_h(state1Pressed, state2, alternative1);
		alternative1Available = true;
	} catch (const Unsolvable& ) {}

	//probiere ohne pressen und suche beste alternative aus
	try {
		vector<bool> state1Copy(state1);
		wpc12_h(state1Copy, state2, alternative2);
		if (alternative1Available) {
			return alternative1.size() < alternative2.size() ? alternative1 : alternative2;
		} else {
			return alternative2;
		}

	} catch (const Unsolvable& ) {
		if (alternative1Available) {
			return alternative1;
		} else {
			throw Unsolvable();
		}
	}
}

    Gruß mathik

    0
  • J

    TomasRiker schrieb:

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

    Schon, aber ich hab gesagt Kriterium ist speed. Ich denke nen Schnitt über je 10 Ketten der Länge 10000000, 10000001, 10000002 ist das fairste. 🙂

    0
  • T

    Das war auch nicht auf diesen Wettbewerb hier bezogen, sondern auf Zukünftige 😉

    0
  • P

    Ich hab mal meinen Testrunner komplettiert, so dass er auch zufällige Ketten testen kann und diese nach Exception und nicht Exception trennt. Das Testprogramm findet ihr unter http://www.pontohonk.de/wpc/testrunner.C. Die Ergebnisse der Läufe unter http://www.pontohonk.de/wpc/lauf.html

    0
  • P

    mathik schrieb:

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    ...

    Gruß mathik

    Dein Code arbeitet nicht korrekt.

    0
  • P

    Ich hab mal die stark wechselnden Zeiten meines Algrithmus untersucht, wie sie Volkards Graphik und auch meine Zeiten zeigen. Dabei bin ich auf etwas gestossen, was ich mir nicht erklären kann. So sehen die Messergebnisse in einem Bereich aus:

    vor 10452832 Werte um die 128 ms
    10452832 128.156 ms
    10452833 264.206 ms
    nach 10452833 um die 264 ms
    .
    .
    . Werte steigen langsam bis zu 270 ms
    .
    .
    11009888 274.9
    11009889 128.505
    nach 11009889 um die 264 ms

    Im Bereich 10452833-11009888 braucht der Algorithmus ungefähr 270 ms. Davor und danach bewegt er sich bei um die 130 ms. Es gibt noch viele weitere Bereiche, in denen der Algorithmus wesentlich mehr Zeit benötigt, als die Instanzen drumherum. Die Algorithmen von Volkard und TomasRiker zeigen ein ähnliches Verhalten hier nur dort ist die Differenz nicht so hoch. Dort steigt die Laufzeit plötzlich von 180 ms auf 215 ms. Kann sich jemand erklären, was hier passiert?

    0
  • M

    Ponto schrieb:

    mathik schrieb:

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    ...

    Gruß mathik

    Dein Code arbeitet nicht korrekt.

    welcher testfall?

    0
  • J

    So, ich habe die Auswertung fertig:

    1. David Scherfgen
    2. volkard
    3. ponto
    4. edx

    die Codes und ein paar Meßergebnisse gibt's auf wpc.schornboeck.net

    MfG Jester

    0
  • P

    mathik schrieb:

    welcher testfall?

    State1: 010100111
    State2: 011101000

    Falsches Ergebnis: 0 0 0 0 0 0 0 0 0 3 4 7

    0
  • D

    Mathematische Betrachtungen: Paritäten

    Ich gehe wieder von der transformierten Aufgabe aus, den State S = xxxx... auf 0 zu reduzieren.

    Parität: 1, wenn die Anzahl der 1en ungerade ist. 0, wenn die Anzahl der 1en gerade ist.

    3n+2:

    xxxxxxxxx...xxxxx  and
110110110   11011  (110 wiederholend)

    Egal welchen Schalter man umlegt - die Parität ändert sich nicht.
    Die Kette ist genau dann lösbar (auf 0 reduzierbar), wenn die Parität 0 ist. Wenn sie 1 ist, existiert keine Lösung.

    3n:

    xxxxxxxxx...xxxxxx  and
011011011   011011  (011 wiederholend)

    Die Parität lässt sich nur durch den Schalter ganz links ändern.
    Dieser Schalter muss also genau dann betätigt werden, wenn die Parität 1 ist.

    3n+1:

    xxxxxxxxx...xxxxxxx  and
101101101   1011011  (101 wiederholend)

    Die Parität lässt sich nur durch den Schalter ganz links ändern.
    Dieser Schalter muss also genau dann betätigt werden, wenn die Parität 1 ist.

    0
  • V

    Jester schrieb:

    Btw.: volkard: mit was machst Du diese tollen Grafiken?

    ms-excel.
    zuerst schreibe ich ne von excel lesbare tabelle, indem ich starte "wpc12.exe > t.cvs" (dazu hab ich \t im prog als trenner genommen). dann starte ich excel und lade die daten "excel t.cvs". dann drücke ich den button (das smart-icon) "diagramm-assistent". dann suche ich xy-dagramm aus. dann klicke ich auf "fertig stellen", weil alle weiteren fragen des assis unerheblich sind. fertig.

    0
Anmelden zum Antworten