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

WPC... geht weiter! -> wpc12

  • M

    volkard: Kannst du mir bitte auch noch das hier schicken (jeder andere ist natürlich auch eingeladen):

    #include <fstream>
#include <iterator>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
// Hoffentlich hab ich jetzt nichts vergessen :p
using namespace std;

int main()
{
	ifstream file("testfaelle.txt");
	vector<string> zeile;
	istream_iterator<string> iin(file), eof;
	copy(iin, eof, back_inserter(zeile));

	for(vector<string>::iterator i = zeile.begin(); i != zeile.end(); i+=2)
	{
		vector<size_t> result = wpc12(makeState(*i), makeState(*(i+1)));

		*(i+1) += "\n";
		for(vector<size_t>::iterator j = result.begin(); j != result.end(); ++j)
		{
			stringstream str;
			str << *j;
			string buffer;
			str >> buffer;

			*(i+1) += buffer + " ";
		}
		*(i+1) += "\n\n";
	}
	ofstream out("testfaelle.txt");
	copy(zeile.begin(), zeile.end(), ostream_iterator<string>(out, "\n"));
}
    0
  • V

    Michael E. schrieb:

    volkard: Kannst du mir bitte auch noch das hier schicken

    morgen oder so. will erst nochmal am speed drehen.

    0
  • ?

    TomasRiker schrieb:

    💡 Bin jetzt bei 1.000.000 Zeichen in durchschnittlich 63 ms!

    Hui, das ist schnell, da komme ich nicht einmal annähernd hin. Da werde ich wohl noch an der Speed-Schraube gewaltig drehen müssen 🙂

    Habt ihr übrigens mal versucht, wie groß bei euch der Geschwindigkeitsunterschied zwischen dem in der Aufgabe vorgegebenen vector<bool> und alternativem vector<char> ist? vector<bool> als Pseudo-Container fügt ja schließlich auch zusätzliche Operationen hinzu. Bei mir mit mingw-gcc 3.2 ist der Unterschied bei ca. 90000 Zeichen immerhin von 53ms auf 31ms...

    0
  • L

    ich habe gelesen, dass man den vector<bool> möglichst vermeiden sollte, da er sich nicht wie ein STL-Container verhält...

    0
  • ?

    Das ist das, was ich meine. vector<bool> ist weder ein Container, noch ist er ein vector. Er ist ein fehlgeschlagenes Experiment...
    In dieser Aufgabe funktioniert er trotzdem, aber er ist auf Größe, nicht auf Geschwindigkeit optimiert. Der Geschwindigkeitsunterschied zwischen vector<bool> und vector<char> bei dieser Aufgabe hängt aber von der STL-Implementierung ab, deswegen habe ich interessehalber mal gefragt 🙂

    0
  • D

    Mathematische Betrachtungen, Nummer 1

    (1) Wir stellen fest, dass die Schalter sich wie XOR-Operationen mit Bitmuster (0+)111(0+) (bzw. am Anfang und Ende ein offensichtlich leicht anderes Bitmuster) verhalten.

    (2) (Kommutativität) Es folgt, dass die Reihenfolge, in der die Schalter betätigt werden, egal ist.

    (3) (Eindeutigkeit) In der optimalen Lösung wird kein Schalter mehr als 1 mal betätigt (Bitmuster XOR Bitmuster = 0).

    (4) Sei Z(k) der im k-ten Zug betätigte Schalter und N die Gesamtzahl der benötigten Züge.

    (5) Sei M(k) das Bitmuster des k-ten Schalters.

    (6) Sei S1 das Eingangsmuster und S2 das Ausgangsmuster.

    (7) (Reduktion) Wir suchen eine Zugfolge Z(k) mit S1 XOR(i=1..N) M(Z(k)) = S2.
    Dies kann man offensichtlich reduzieren auf:
    (S1 XOR S2) XOR(i=1..N) M(Z(k)) = 0.

    (8) Wenn eine Zugfolge existiert, die S1 in S2 transformiert, dann es gibt auch eine optimale Zugfolge Z mit der Eigenschaft:
    Z(1) < Z(2) < ... < Z(n)
    Im Folgenden sei Z diese Zugfolge.

    (9) Seien die Bits von 1 bis N angeordnet wie die Schalter. Das Bit an der Stelle k sei Bit(k).

    (10) Wird der Schalter Z(k) betätigt, dann darf nach der Ausführung kein Bit b < Z(k) mehr gesetzt sein, denn es gilt Z(k) < Z(k+1).

    (11) Es gilt also
    (11.1) Z(1) = 1 oder
    (11.2) Z(1) = j+1 mit Bit(j) = 1 und OR(i=1..j-1) Bit(i) = 0 (kein Bit kleiner j ist gesetzt, aber j ist gesetzt).

    (12) Dies ist die hier schon öfter erwähnte Aufspaltung in 2 lineare Fälle.

    0
  • D

    Mathematische Betrachtungen, Nummer 2:
    Bitmuster der Länge 3n

    ... sind immer auf 0 reduzierbar.

    Beweis durch vollst. Induktion:

    Für n=1 ist die Behauptung wahr.

    Nun schliesse ich von n auf n+1:

    Das Teilmuster von Bit 1 bis 3n lässt sich nach Induktionsvoraussetzung auf lauter Nullen bringen. Wir erhalten 0{3n}(0|1){3}
    Für (0|1){3} = 000 | 111 | 011 | 100 sind wir schnell durch betätigen der letzten 2 Schalter fertig.

    Die Fälle (0|1){3} = 001 | 010 | 101 | 110 reduzieren wir durch die letzten 2 Schalter auf 001 und erhalten: 0{3n+2}1

    (000)(000)(000)..., (110)(000)(000)..., (001)(000)(000)..., (000)(110)(000)...

    So kommt man irgendwann bei (000)(000)(000)...(111) an. Fertig.

    0
  • ?

    Jetzt sind wohl alle sehr beeindruckt. 🕶 👍

    0
  • ?

    Ich habe mal noch ein weiteres Geschwindigkeitstestprogramm gebastelt (gestützt auf Michaels Version und d-f-gs Ausführung, dass Ketten der Länge 3n immer lösbar sind), das vielleicht auch noch das ein oder andere interessante Ergebnis liefern könnte. Ob es sich für den eigenen Compiler und Plattform eignet, hängt hauptsächlich davon ab, wie präzise clock() arbeitet 🙂

    #include <vector>
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>

typedef std::vector<char> Chain;
typedef std::vector<size_t> Moves;

Moves wpc12(Chain& state1, Chain& state2);

Chain createRndChain(size_t size)
{
  Chain res;
  res.reserve(size);
  for (size_t i = 0; i < size; ++i)
    res.push_back(rndBool());
  return res;
}

void testAlgorithm(size_t size, size_t loops)
{
  typedef unsigned long long big_uint;
  std::cout << "Kettengroesse: " << size << "; Anzahl Durchlaeufe: " << loops << std::endl;
  big_uint whole = 0;
  size_t min = static_cast<size_t>(-1);
  for (size_t i = 0; i < loops; ++i)
  {
    Chain testStart = createRndChain(size);
    Chain testEnd(testStart.size());
    std::clock_t start = std::clock();
    Moves moves = wpc12(testStart, testEnd);
    std::clock_t end = std::clock();
    whole += (end-start);
    if (end-start < min)
      min = end-start;
    if (i % (loops / 50) == 0)
      std::cout << '#' << std::flush;
  }
  std::cout << " fertig\n";
  size_t avg = whole / loops;
  std::cout << "Durchschnitt: " << avg / (CLOCKS_PER_SEC/1000) << " ms (" << avg << " ticks)\n";
  std::cout << "Minimum: " << min / (CLOCKS_PER_SEC/1000) << " ms (" << min << " ticks)\n";
  std::cout << std::endl;
}

int main( int argc, char * argv[] )
{
  size_t startSize = 1;
  size_t numTests = 7;
  size_t numLoops = 1000;
  for (size_t i = 0; i < numTests; ++i, startSize*=10)
  {
    testAlgorithm(startSize+2, numLoops);
  }
  return 0;
}

    Einfach die eigene wpc12 Funktion dazulinken, müsste funktionieren, hoffe ich. Auf Windows-Plattformen den typedef von big_uint auf __int64 anpassen!

    Hier noch meine Ergebnisse:

    Kettengroesse: 3; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (0 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 12; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (0 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 102; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (20 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 1002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (90 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 10002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (970 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 100002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 10 ms (10940 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 1000002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 109 ms (109570 ticks)
Minimum: 100 ms (100000 ticks)

    Ob die jetzt gut sind, sei dahingestellt - Testplattform war ein Athlon64 3200+ auf einem 64bit-Linux, insofern...

    Zum Vergleich mal das Resultat, wenn ich statt vector<bool> vector<char> verwende:

    Kettengroesse: 3; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (0 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 12; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (0 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 102; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (0 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 1002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (20 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 10002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 0 ms (160 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 100002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 2 ms (2450 ticks)
Minimum: 0 ms (0 ticks)

Kettengroesse: 1000002; Anzahl Durchlaeufe: 1000
################################################## fertig
Durchschnitt: 27 ms (27710 ticks)
Minimum: 10 ms (10000 ticks)

    Schon ein gewisser Unterschied...

    0
  • T

    Ich bin mittlerweile bei 47 ms für eine Million Glühbirnen angelangt (AthlonXP 3000+). Komischerweise hat es aber keinen Einfluss auf die Geschwindigkeit, wenn ich vector<bool> in vector<char> umändere.
    Ob das am Compiler (Visual C++.NET 2002) liegt?

    0
  • ?

    Dann hat die deinem Compiler beiliegende Implementierung der STL möglicherweise die Spezialisierung von vector für bool nicht, was hieße, dass sich dein vector<bool> wie vector<char> bei mir verhalten würde. Könnte man wahrscheinlich testen, wenn man gezielt die Schwächen der Spezialisierung von vector<bool> missbrauchen würde...

    Habe mein Testprogramm übrigens gerade mal auf meinem Router (PII/266Mhz) ausprobiert, und das Ding ist ungefähr 10x langsamer als mein Athlon. Finde ich jetzt irgendwie ein bisschen wenig, ich hätte mit einem größeren Faktor gerechnet, aber nun gut 🙂

    0
  • J

    kwaart schrieb:

    Das ist das, was ich meine. vector<bool> ist weder ein Container, noch ist er ein vector. Er ist ein fehlgeschlagenes Experiment...
    In dieser Aufgabe funktioniert er trotzdem, aber er ist auf Größe, nicht auf Geschwindigkeit optimiert. Der Geschwindigkeitsunterschied zwischen vector<bool> und vector<char> bei dieser Aufgabe hängt aber von der STL-Implementierung ab, deswegen habe ich interessehalber mal gefragt 🙂

    Ich denke ich werde meine Dev-Cpp Entwicklungsumgebung nutzen, da ist ein gcc dabei.

    Ich habe mich für vector<bool> entschieden, da die Aufgabe ja doch irgendwann gewissen Speichermengen benötigt. Wenn ich das recht sehe kann der Container auf 2^32-Elemente anwachsen. Das wäre bei chars dann 4GB. Die kann ich leider nicht performant zur Verfügung stellen. Ich möchte ja auch Eure Algos benchmarken und nicht meine Platte beim swappen. 4GB/8 also 512MB ist zwar auch noch knapp (wir brauchen ja 2 Eingaben) aber das geht gerade noch so.

    Achja, mein System auf dem ich laufen lasse ist entweder ein Celeron 433@475Mhz mit 640MB Speicher oder ein P3 650Mhz mit 256MB RAM.

    Wem das zu lahm ist, der kann mir gerne nen schnelleren Rechner schenken. 😃

    0
  • ?

    Hm, an 4 Mrd. Lichtern dürften so ziemlich alle Algorithmen hier ziemlich lange zu knabbern haben. Allerdings legt meiner weitere Vektoren der gleichen Länge an, also wird er wahrscheinlich bei Speicherknappheit selbst mit vector<bool> in dieser Riege bei dir nicht konkurrieren können 🙂

    0
  • T

    * hat sich erledigt *

    0
  • D

    Mathematische Betrachtungen, Nummer 3:
    Bitmuster der Länge 3n+1

    ... sind immer auf 0 reduzierbar.

    Wie schon bewiesen, kann man die ersten 3n Bit auf 0 reduzieren.
    Man kommt hier an:
    0{3n}(0|1)
    Ist (0|1) = 0 sind wir fertig. Bei (0|1) = 1 geht man wieder so vor:

    (000)(000)(000)..., (110)(000)(000)..., (001)(000)(000)..., (000)(110)(000)...

    und kommt irgendwann hier an: ...(000)...(000)(110)1, was man durch 2 Schalter leicht lösen kann. Fertig.

    0
  • D

    Mathematische Betrachtungen, Nummer 4:
    Bitmuster der Länge 3n+2

    ... sind NICHT immer auf 0 reduzierbar.

    Wie schon bewiesen, kann man die ersten 3n+1 Bit auf 0 reduzieren.
    Man kommt hier an:
    0{3n+1}(0|1)
    Ist (0|1) = 0 sind wir fertig. Bei (0|1) = 1 sind wie in dieser Position:

    ...(000)...(000)(000)01

    Diese Kombination lässt sich nicht auf 0 reduzieren. Warum? Weil es eigentlich nur einen Ansatz (bzw. 2 Ansätze) gibt, das zu lösen. Und der führt nicht zum Ziel.

    Ein wichtiges Ergebnis

    Die Bitmuster, die man nicht auf 0 reduzieren kann, lassen sich alle auf diese Form bringen:

    0{3n}01 - also 3n+1 Nullen und eine 1 am Ende.

    Entsprechend kann man aus dieser Form durch Umlegen von Schaltern alle Bitmuster erhalten, die sich nicht auf 0 reduzieren lassen.

    0
  • V

    d-f-g schrieb:

    Mathematische Betrachtungen, Nummer 4:
    Bitmuster der Länge 3n+2
    ... sind NICHT immer auf 0 reduzierbar.

    sie sind genau dann reduzierbar, wenn die anzahl der bits an positionen (bei 1 beginnend), die nicht durch 3 teilbar sind, gerade ist, oder?

    0
  • D

    Wenn das stimmt, dann natürlich nur für die Bitketten der Länge 3n+2. Das überprüfe ich morgen. Bin jetzt zu müde.

    0
  • J

    volkard schrieb:

    sie sind genau dann reduzierbar, wenn die anzahl der bits an positionen (bei 1 beginnend), die nicht durch 3 teilbar sind, gerade ist, oder?

    Ah, jetzt kommen die neuen Sachen... das hatte ich mir nicht mehr überlegt. 🙂

    Btw.: Kann schon jemand was über die Anzahl der möglichen Lösungen aussagen? (mit Beweis 😉 )

    0
  • V

    d-f-g schrieb:

    Wenn das stimmt, dann natürlich nur für die Bitketten der Länge 3n+2. Das überprüfe ich morgen. Bin jetzt zu müde.

    es sagt aber auch voraus, welcher der beiden linearen läufe bei 3n+1 zum ziel führen wird. danach suchten wird doch?

    mir schwant fast, daß man die beiden pseudobits jenseits des randes miteinrechnen darf und ein muster geht genau nach obiger regel auf.

    allerdings ist bei 3*n sowas zu sehen
    (p==pseudobit, *==beliebiges bit, -==irrelevantes bit)
    -|* * -|p

    bei 3*n+1 sowas
    -|* * - *|p

    bei 3*n+2 sowas
    -|* * - * *|-

    also bei 3*n und 3n+1 kann man stets die parität selber bestimmen, weil das linke pseudobit bei der zählung irrelevant ist aber das rechte relevant ist. aber bei 3*n+2 ist man in den popo ekniffen, weil beide pseudobis irrelevant sind. dann geht's halt auf oder nicht.

    und ich sehe leider keinen ansatz, im vorhinein zu sehen, welche der beiden folgen bei 3*n+2 die kürzere ist.

    noch ne frage: die schalter, die zu den relevanten bitpositionen gehören, sind ja so verteilt, daß genau entweder zur einen oder zur anderen lösung gehören. gibt es aussagen über die schalter an den irrelevanten bitpositionen (vor allem: schalten sie dort schlicht abwechselnd?). das würde nämlich erlauben, wenn man die schalteranzahl einer lösung hat, die schalteranzahl der gegenlösung zu bestimmen.

    0
Anmelden zum Antworten