Hallo,
ich schreibe im Moment lauter kleine Programme um meine sehr
prähistorischen C++ Kenntnisse aufzupolieren. Gestern habe ich ein
kleines Programm geschrieben um einen Pocket Magic Cube zu lösen (mein
Sohn hat ihn nicht wieder hinbekommen, eine gute Gelegenheit zum Üben
:-)).
Das Programm ist etwas länglich und mir geht es nur um eine Stelle,
daher ausnahmsweise nur ein Code-Ausschnitt.
Es geht mir nicht um den Algorithmus oder eine Performance-Verbesserung,
mir ist nur heute aufgefallen, dass die drei Code-Abschnitte extrem
identisch sind. Ich finde das an dieser Stelle nicht so schlimm, habe
aber die folgende Frage:
Sieht jemand ad hoc eine in modernem C++ idiomatische Formulierung um
die drei fast identischen Abschnitte durch einen generischen und dessen
dreimalige Anwendung zu ersetzen? Es geht mir nur um für moderne C++
Programmierer offensichtliche Varianten, nicht um esoterische Klimmzüge.
Der Code-Schnipsel ist der Kern der klassischen rekursiven Backtracking
Funktion.
Würfel& Würfel::x() etc. führen eine Rotation mit dem virtuellen Pocket
Cube durch, eben um die x, y oder z Achse.
Würfel& Würfelvermietung::mieten(const Würfel& w) stellt einfach eine
Würfel-Instanz bereit und kopiert die Werte von const Würfel& w hinein.
Ich hoffe, das reicht an Informationen?
Wie gesagt: Die Frage dreht sich nur um eine generischere Formulierung
des oben gezeigten Abschnittes, wenn eine solche für einen modernen C++
Programmierer offensichtlich ist.
Vielen Dank schonmal!
Herzliche Grüße
Timm
P.S.: Ja die Umlaute, ich weiß. Wollts nur mal ausprobieren, hätte
eigentlich schon damals mit C++98 gehen sollen ...
ändern, mit Achse als enum oder tag für x/y/z? Ich vermute der vector
"loesung" enthält die durchgeführten Rotationen mit 1=x, 2=y, 3=z, dann
kannst du daraus einen std::vector<Achse> machen. Dann könntest du aus
den drei ifs einfach drei Funktionsaufrufe von
Hallo,
war wohl nicht so clever, die Sache mit dem Ausschnitt, ich poste doch
mal das ganze Programm.
Deinen Vorschlag schaue ich mir morgen in Ruhe an, danke schonmal.
(Da sind noch ein paar kleine Experimente drin, zum Beispiel inline
Würfel& copy(const Würfel&); statt des default = Operators, damit ich
leichter die Aufrufe zählen kann, aber wenn ich jetzt noch ad hoc am
Code rumfummle, dann mache ich noch was kaputt, spielt aber für die
Frage ja nun wirklich keine Rolle, hoffe ich.
Herzliche Grüße
Timm
1
// 1. um x (x zeigt zum Betrachter), gegen den Uhrzeigersinn, vorne steht, hinten dreht
2
// 2. um y (y zeigt horizontal nach rechts), bewegliche Hälfte wird vom Betrachter weg rotiert, die linke Hälfte steht, die rechte dreht
3
// 3. um z (z zeigt von unten nach oben), unten steht, oben dreht, gegen den Uhrzeigersinn
> sinnvoller.
Mist, das ist echt gefährlich. Als ich das hinschrieb, war mir das noch
klar, mittlerweile nicht mehr. Guter Hinweis! Danke.
> 2.> Im gleichen Program die "guten" Strong types und die bösen globalen> Variablen benutzen? :-)
Ja, muss eigentlich nicht sein.
Danke schonmal für Deine Hinweise!
Herzliche Grüße
Timm
Noch ein weiterer Kommentar.
Was ist der Sinn von Würfelvermietung? Möchtest du damit eine Art Vorrat
für Würfel bildern, damit sie nicht so häfig kopiert werden müssen? Wenn
ja hilft dir das nicht wirklich, weil in mieten(Würfel&) so oder so
kopiert wird und danach effektiv in Würfel::x() noch ein weiteres Mal.
Warum hat das array meineWürfel eine Größe von 20? Ist das ein
willkürlich festgelegter Wert, oder ist die Anzahl der Würfel logisch
begrenzt? Die Zugriffe sehen auf jeden Fall sehr gefährlich aus.
Wäre alles nicht viel einfacher, wenn Würfel::x() statt einer Referenz
eine Kopie zurückliefern würde? Damit musst du nur einmal kopieren statt
zweimal und alles wird viel einfacher und übersichtlicher.
Hi mh,
die Würfelvermietung war nur ein Experiment. Eigentlich hätte ich
erwartet, dass ich so, weil ich Deallokationen und Allokationen einspare
schneller wird, es ist aber signifikant langsamer, als wenn ich immer
wieder neue Objekte erzeugen und zerstören würde. In der Version, die
ich hier geschrieben habe, sollten max. 15 Würfel nötig sein, die 20
sind nur, weil ich mich im Bus nicht genug konzentrieren konnte und zu
dem Zeitpunkt noch nicht wusste wie tief man suchen muss.
Aber: Ja, du hast recht, sobald ich rausgefunden habe, warum die
Würfelvermietung so langsam ist, mache ich sie tot.
Danke und Viele liebe Grüße
Timm
wie findest du denn heraus ob es langsam ist?
wie sieht denn dein Benchmark aus?
Debug(unptimierte) Builds anzuschauen ist völlig sinnlos weil die
Release-Varianten sehr sehr sehr viel schneller sind
Es gibt verschiedene Profiler die du nutzen kannst z.B. den eingebauten
in VStudio
Hallo Bert3,
Bert3 schrieb:> wie findest du denn heraus ob es langsam ist?>> wie sieht denn dein Benchmark aus?>> Debug(unptimierte) Builds anzuschauen ist völlig sinnlos weil die> Release-Varianten sehr sehr sehr viel schneller sind>> Es gibt verschiedene Profiler die du nutzen kannst z.B. den eingebauten> in VStudio
es lag nicht am Debug/Release Thema, aber Du hast trotzdem einen guten
Punkt angesprochen. Es lag wohl zu viel Zeit zwischen den beiden
Messungen und das Betriebsystem war einmal mit Indexieren beschäftigt
und einmal nicht.
Korrektes Ergebnis: Mit Würfelvermietung ist das Prog. ziemlich genau
drei mal so schnell, wie ohne. Das entspricht ja wohl auch dem, was man
erwarten würde.
Auch Dir vielen Dank.
vlg
Timm
Hi,
auch wenn du zum Algorithmus keinen Kommentar willst
kann ich es mir doch nicht verkneifen.
Dein run() wird ueber 45 Millionen mal aufgerufen, falls w.fertig()
keine
Loesung findet.
Der Loesungsraum ist aber kleiner 16*(4^6) = 65536.
Gruss
Timm R. schrieb:> Korrektes Ergebnis: Mit Würfelvermietung ist das Prog. ziemlich genau> drei mal so schnell, wie ohne. Das entspricht ja wohl auch dem, was man> erwarten würde.
Das ist nicht das was ich erwarten würde, da deine Würfelvermietung eine
unnötige Kopie der Würfel erfordert. Es sei denn du änderst irgendwas
anderes (z.B. ohne Grund dynamisch Speicher anfordern).
Bei der Gelegenheit: Warum benutzt du in einigen Funktionen
std::vector<int> und in anderen std::array?
Hallo Josef,
Josef schrieb:> Dein run() wird ueber 45 Millionen mal aufgerufen, falls w.fertig()> keine> Loesung findet.
auch wenn es eine Lösung findet. Die Suche soll erschöpfend sein. D.h.
es soll garantiert sein, dass alle Lösungen mit maximal der zulässigen
Länge (15) gefunden werden.
> Der Loesungsraum ist aber kleiner 16*(4^6) = 65536.
da hätte ich drei Fragen:
1. Könntest Du mir das eventuell noch etwas detaillierter erläutern? Vom
bloßen betrachten erschließt sich mir das leider nicht.
2. Besonders interessant finde ich, dass die Lösungsmenge offensichtlich
Raumstruktur hat, das sehe ich ad hoc auch nicht, gibt es dafür eine
triviale Begründung?
3. Warum bedeutet das, dass es ein Problem mit dem Algorithmus gibt? Es
gibt zahllose erschöpfende Suchen mit winzigen Lösungsmengen. Oder folgt
daraus, dass meine Suche über-erschöpfend ist?
Sorry, bin kein Zauberwürfel-Guru.
vlg
Timm
Hi,
mh schrieb:> Das ist nicht das was ich erwarten würde, da deine Würfelvermietung eine> unnötige Kopie der Würfel erfordert. Es sei denn du änderst irgendwas> anderes (z.B. ohne Grund dynamisch Speicher anfordern).
naja, der Vergleich ist natürlich ceteris paribus, also einmal mit der
Würfelvermietung und einmal mit ctor/dtor statt der Würfelvermietung.
Da hatte ich ja bei meinem ersten Anlauf das verrückte Ergebnis, dass
ctor/dtor schneller war, als die Würfelvermietung. Was ja eigentlich gar
nicht sein konnte.
> da deine Würfelvermietung eine unnötige Kopie der Würfel erfordert.
Hmm, sehe ich nicht. Magst Du mir auf die Sprünge helfen?
> Bei der Gelegenheit: Warum benutzt du in einigen Funktionen> std::vector<int> und in anderen std::array?
Das ist simpel. Als ich das letzte Mal C++ programmiert habe, gab es
std::array noch nicht. Deswegen befindet es sich aktuell an der Grenze
des aktiven Wortschatzes :-)
vlg
Timm
Die unnötige Kopie hatte ich schon in
Beitrag "Re: Anregung gesucht: modern cpp und backtracking" erklärt.
Was meinst du mit ctor/dtor? Würfel hat auch in der Variante, die du
gepostest hast, ctors und nen dtor und ich sehe aktuell keinen Grund die
vom Compiler generierten Versionen zu ändern, wenn du auf die Vermietung
verzichtest.
Timm R. schrieb:>>> da deine Würfelvermietung eine unnötige Kopie der Würfel erfordert.>> Hmm, sehe ich nicht. Magst Du mir auf die Sprünge helfen?
ah, ok, ich glaube, ich habs.
Du meinst, den Würfel, der run() übergeben wird mit einer nicht
zerstörenden x() Routine, also Würfel x() const statt Würfel& x() zu
bearbeiten. Dann habe ich in x() statt dem tmp, das wieder verworfen
wird ein tmp, das ich per Value zurückliefere.
Dann hätte ich eine Allokation und den Kopiervorgang in run()
eingespart, hätte aber einen neuen Kopiervorgang bei x(). Ich bin noch
nicht sattelfest, was die moderne Move Semantik angeht, aber eigentlich
müsste dieser Kopiervorgang automatisch durch ein move ersetzt werden,
ohne, dass ich etwas dafür tun müsste, oder? Das wäre natürlich extrem
performanter!
vlg
Timm
move-Semantik sollte bei std::array keine Vorteile bringen, da die Daten
nicht von einem Stack in an eine andere Stelle im Stack "gemoved" werden
können. Was du in Würfel::x() ausnutzen möchtest ist NRVO
(http://en.cppreference.com/w/cpp/language/copy_elision).
1
WürfelWürfel::x(){
2
Würfeltmp=*this;
3
4
// do something with tmp
5
6
returntmp;
7
}
8
9
Würfela;
10
Würfelb=a.x();
sollte, wenn die Randbedingung an NRVO eingehalten werden, nur 1
Würfelinstanz per default-ctor construieren (a) und insgesamt eine
Instanz per copy-ctor erzeugen (b), alle anderen Kopien werden "elided".
Hallo,
nicht schlecht! Muss ich sagen.
Danke für Deine Hartnäckigkeit!
Die NRVO Variante ist in jedem Fall sowieso schonmal die
übersichtlichste und ordentlichste.
Durch Dein Rumreiten auf der Kopie habe ich noch einen anderen Fehler
gefunden, durch den der Destruktor viel langsamer wurde, so dass das
Programm auf meinem 4GHz Core i7 genauso schnell war, wie auf meinem
2007er Laptop mit Dampfprozessor. Tolle Nebenwirkung.
Also: Bei der NRVO Variante wird der dtor genau so oft aufgerufen, wie
bei der Vermietungsvariante, irre! Und .copy fällt halt weg.
Im Ergebnis: 2656 ms für die Vermietung und 2111 ms für die NRVO
Variante.
Also, wie gesagt, herzlichen Dank noch mal an Dich, mh, aber auch an die
anderen beiden.
vlg
Timm
Noch ein Paar Kommentare.
Du benutzt in einer Funktion mehrere Ausdrücke der Form
1
std::cout<<...<<std::endl;
dabei wird für std::endl jedes Mal flush aufgerufen, was ziemlich
Zeitintensiv sein kann. Wenn das ein Problem ist und du nur einen
Zeilenumbruch willst, nimm lieber '\n'. Wenn du wirklich flush brauchst,
benutz std::endl nur einmal.
In einem Programmteil dessen Laufzeit du untersuchst (mit Mikrosekunden
Auflösung), solltest du komplett auf Ausgaben verzichten.
Hast du Mal ausprobiert wie sich die Laufzeit ändert, wenn du die ganzen
kleinen std::vector<int> durch entsprechende std::array ersetzt? Also
implizit new/delete + move mit stack + copy ersetzen.
Züfälliger Tipp für die Lesbarkeit:
Benutze const auto oder const auto& in ranged-for-loops, wenn du in der
Schleife nur lesend zugreifst und die range nicht modifizierst.
Hallo,
@lalala
Ja, hab ich mir auch gedacht, aber irgendwie gehört das wohl dazu?
Iteration über enum class is nich, implizite Konversion ja auch nicht,
würde ja auch den Sinn gerade komplett zunichte machen.
Und den Effekt, dass für Achse kein ungültiger Wert übergeben werden
kann, oder zumindest schwieriger, habe ich ja.
Naja, war mein erstes enum class, beim nächsten Mal weiß ich dann,
worauf ich mich einlasse :-) War mir diesmal ehrlich gesagt nicht ganz
klar, was das für eine Explosion gibt.
mh schrieb:> Du benutzt in einer Funktion mehrere Ausdrücke der Form>
1
>std::cout<<...<<std::endl;
2
>
das mit dem flush() war mir nicht (mehr) klar! Danke!
> Hast du Mal ausprobiert wie sich die Laufzeit ändert, wenn du die ganzen> kleinen std::vector<int> durch entsprechende std::array ersetzt? Also> implizit new/delete + move mit stack + copy ersetzen.
Hmm, sehr interessant,
ich habe exakt alle std::vector<int> durch std::array<int, 4> ersetzt.
Sonst habe ich nichts gemacht.
Mittelwert über 100 Durchläufe von: 2016 ms bei vector und 2096 ms bei
array.
Ist das nicht schräg?
> Züfälliger Tipp für die Lesbarkeit:> Benutze const auto oder const auto& in ranged-for-loops, wenn du in der> Schleife nur lesend zugreifst und die range nicht modifizierst.
Ah ja! Sehr gut! Ging ja beim alten for nicht :-)
Vielen Dank!
Herzliche Grüße
Timm