WPC... geht weiter! -> wpc12

Ponto

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?

mathik

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?

Jester

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

Ponto

mathik schrieb:

welcher testfall?

State1: 010100111
State2: 011101000

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

d-f-g

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.

volkard

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.

mathik

Ponto schrieb:

mathik schrieb:

welcher testfall?

State1: 010100111
State2: 011101000

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

huh...

was ist der unterschied zwischen:

vector<size_t> alternative(state1.size());

und 

vector<size_t> alternative;
alternative.reserve(state1.size())

?????

ersteres macht irgendwie nicht das, was ich will...

könntest du es nochmal versuchen, mit dem folgenden:

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, alternative2;
	alternative1.reserve(state1.size());
	alternative2.reserve(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();
		}
	}
}

habe nur das geändert:

vector<size_t> alternative1, alternative2;
	alternative1.reserve(state1.size());
	alternative2.reserve(state1.size());

danach kommt bei dem testfall 3,4,7 raus. ohne diese komische nullen davor...

Gruß mathik

Jester

std::vector<size_t> alternative(size) legt einen vector<size_t> mit size Elementen an, die default-initialisiert werden.

das reserve reserviert nur den Speicher ohne direkt Elemente drin abzulegen.

Jester

volkard schrieb:

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.

Okay, dieses Wissen werde ich in die nächste Auswertung mit einfließen lassen.

mathik

Jester schrieb:

std::vector<size_t> alternative(size) legt einen vector<size_t> mit size Elementen an, die default-initialisiert werden.

das reserve reserviert nur den Speicher ohne direkt Elemente drin abzulegen.

oh ja, danke.
hab in letzter zeit zu viel java programmiert...

könntest du den test-code nochmal posten?

würde mal gerne schauen, wo meine lösung gestanden hätte...

Gruß mathik

Ponto

Mathik, nun scheint es korrekt zu laufen, aber nicht besonders schnell.

Sgt. Nukem

Jester schrieb:

So, ich habe die Auswertung fertig:

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

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?
Ist das die Ehre des Gewinners?!?

Jester

der Code enthielt eine Funktion const char* getName();

Ich habe die Namen aus den Ausgaben meines Testprogramms kopiert. Das gibt eben aus was derjenige da reingeschrieben hat.

btw.: volkard heißt volkard

Sgt. Nukem

Jester schrieb:

btw.: volkard heißt volkard

Also ich tippe eher auf "Volkard".

volkard

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Sgt. Nukem

volkard schrieb:

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Weil kleingeschriebene Eigennamen genau wie "Jesus" und Co. in Deutschland verboten sind.

volkard

Sgt. Nukem schrieb:

volkard schrieb:

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Weil kleingeschriebene Eigennamen genau wie "Jesus" und Co. in Deutschland verboten sind.

"volkard" ist großgeschrieben, das siehst du bloß nicht, weil auf dem übertraungsweg von mir bis zu dir ein paar der besonders irrelevanten daten verloren gehen.

mathik

Ponto schrieb:

Mathik, nun scheint es korrekt zu laufen, aber nicht besonders schnell.

stimmt, habe das selber mal mit euren implementierungen verglichen.
so faktor 2 - 3 langsamer.
aber danke.

gruß mathik

WPC... geht weiter! -&gt; wpc12

WPC... geht weiter! -> wpc12