Forum: PC-Programmierung Anregung gesucht: modern cpp und backtracking


You were forwarded to this site from EmbDev.net. Back to EmbDev.net
Anregung gesucht: modern cpp und backtracking
von Timm R. (Firma: privatfrickler.de) (treinisch)

Lesenswert?
• ▲
▼ 
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.

1
    if(t.x<3)

2
    {

3
        loesung.push_back(0);

4
        run(würfelvermietung.mieten(w).x(), depth+1, {++t.x, 0, 0});

5
        würfelvermietung.zurückgeben();

6
        loesung.pop_back();

7
    }

8
    if(t.y<3)

9
    {

10
        loesung.push_back(1);

11
        run(würfelvermietung.mieten(w).y(), depth+1, {0,++t.y,0});

12
        würfelvermietung.zurückgeben();

13
        loesung.pop_back();

14
    }

15
    if(t.z<3)

16
    {

17
        loesung.push_back(2);

18
        run(würfelvermietung.mieten(w).z(), depth+1, {0, 0, ++t.z});

19
        würfelvermietung.zurückgeben();

20
        loesung.pop_back();

21
    }


Ich glaube, was die Funktionen ganz genau tun ist für meine Frage nicht 
wichtig, hier aber noch zwei Deklarationen:

1
using Transformationen = struct {int x; int y; int z;};

2
void run(const Würfel& w, int depth, Transformationen t);


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

: Bearbeitet durch User
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Re: Anregung gesucht: modern cpp und backtracking
von mh (Gast)

Lesenswert?
• ▲
▼ 
Kannst du
1
Würfel::x()

 (y/z) in
1
Würfel::rotieren(Achse)

 ä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
1
void foo(Würfel& w, std::vector<Achse>& loesung, int& i, Achse a) {

2
  if(i<3) {

3
    loesung.push_back(a);

4
    run(würfelvermietung.mieten(w).z(), depth+1, {

5
      a==Achse(1)? ++i : 0,

6
      a==Achse(2)? ++i : 0,

7
      a==Achse(3)? ++i : 0

8
    });

9
    würfelvermietung.zurückgeben();

10
    loesung.pop_back();

11
  }

12
}

machen. Das ist immer noch nicht schön, aber ohne das drumrum zu kennen 
und zu verändern würd ich es dabei belassen.

Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Re: Anregung gesucht: modern cpp und backtracking
von Timm R. (Firma: privatfrickler.de) (treinisch)

Lesenswert?
• ▲
▼ 
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

4
5
#include <iostream>

6
#include <vector>

7
#include <array>

8
#include <chrono>

9
#include <cmath>

10
11
template<typename TimeT = std::chrono::milliseconds>

12
struct measure

13
{

14
    template<typename F, typename ...Args>

15
    static typename TimeT::rep execution(F&& func, Args&&... args)

16
    {

17
        auto start = std::chrono::steady_clock::now();

18
        std::forward<decltype(func)>(func)(std::forward<Args>(args)...);

19
        auto duration = std::chrono::duration_cast< TimeT>

20
        (std::chrono::steady_clock::now() - start);

21
        return duration.count();

22
    }

23
};

24
25
26
template <typename T, typename Parameter>

27
class NamedType

28
{

29
public:

30
    explicit NamedType(T const& value) : value_(value) {}

31
    explicit NamedType(T&& value) : value_(value) {}

32
    T& get() { return value_; }

33
    T const& get() const {return value_; }

34
private:

35
    T value_;

36
};

37
38
struct transformationen_t {

39
    int x;

40
    int y;

41
    int z;

42
};

43
44
using Flaeche = NamedType<int, struct FlaecheParameter>;

45
using ZielFlaeche = NamedType<int, struct FlaecheParameter>;

46
using QuellFlaeche = NamedType<int, struct FlaecheParameter>;

47
using Element = NamedType<int, struct ElementParameter>;

48
using Maske = NamedType<std::vector<int>, struct MaskeParameter>; // 1 = fixiert, 0 = beweglich

49
using Orientierung = NamedType<std::vector<int>, struct OrientierungParameter>;

50
using Anzahl = NamedType<int, struct AnzahlParameter>;

51
using Transformationen = struct {int x; int y; int z;};

52
53
Orientierung orientierungX({0, 3, 0, 1, 2, 3});    // 0 = normal, 1 = invers

54
Orientierung orientierungY({0, 0, 0, 3, 0, 0});

55
Orientierung orientierungZ({1, 0, 0, 0, 0, 2});

56
57
std::vector<int> loesung;

58
int progress;

59
60
class Würfel {

61
public:

62
    void read();

63
    void print();

64
    void testset1();

65
    int& get(int,int);

66
    int  get(int,int) const;

67
    inline Würfel& copy(const Würfel&);

68
    void rotiereBenachbarteFlaechen(Flaeche, Flaeche, Maske, const Orientierung&, const Würfel& tmp);

69
    void flaecheRotieren(Flaeche, const Orientierung&);

70
    std::vector<int> koordinatenRotieren(Flaeche, const Orientierung&);

71
    Würfel& x();

72
    Würfel& y();

73
    Würfel& z();

74
    bool fertig() const;

75
    static const int flaeche_size = 6;

76
    static const int elemente_size = 4;

77
78
    std::array<int, flaeche_size*elemente_size> daten;

79
    

80
private:

81
    

82
};

83
84
int& Würfel::get(int f, int e) {

85
    return daten[f*elemente_size + e];

86
}

87
88
int Würfel::get(int f, int e) const {

89
    return daten[f*elemente_size + e];

90
}

91
92
void Würfel::read() {

93
}

94
95
void Würfel::rotiereBenachbarteFlaechen(Flaeche fZiel, Flaeche fQuelle, Maske m, const Orientierung& orientierung, const Würfel& tmp) {

96
   

97
    std::vector<int> quellKoordinaten = koordinatenRotieren(fQuelle, orientierung);

98
    std::vector<int> zielKoordinaten = koordinatenRotieren(fZiel, orientierung);

99
    

100
    for(int i=0; i<4; ++i) {

101
        if(m.get()[i]==0) {   // Bewegliches Element

102
            get(fZiel.get(), zielKoordinaten[i]) = tmp.get(fQuelle.get(),quellKoordinaten[i]);

103
        }

104
        else {

105
         

106
        }

107
    }

108
}

109
110
void Würfel::flaecheRotieren(Flaeche f, const Orientierung& orientierung) {

111
    

112
    std::vector<int> koordinaten = koordinatenRotieren(f, orientierung);

113
    

114
    for(int i=0; i<orientierung.get()[f.get()]; ++i) {

115
        auto hilf = get(f.get(), koordinaten[0]);

116
        get(f.get(), koordinaten[0]) = get(f.get(), koordinaten[1]);

117
        get(f.get(), koordinaten[1]) = get(f.get(), koordinaten[3]);

118
        get(f.get(), koordinaten[3]) = get(f.get(), koordinaten[2]);

119
        get(f.get(), koordinaten[2]) = hilf;

120
    }

121
}

122
123
std::vector<int> Würfel::koordinatenRotieren(Flaeche f, const Orientierung& orientierung) {   // gegen Uhrzeigersinn

124
    std::vector<int> koordinaten = {0,1,2,3};

125
    

126
    if(orientierung.get()[f.get()]==0) return koordinaten;

127
    

128
    for(int i=0; i<orientierung.get()[f.get()]; ++i) {

129
        auto hilf = koordinaten[0];

130
        koordinaten[0] = koordinaten[1];

131
        koordinaten[1] = koordinaten[3];

132
        koordinaten[3] = koordinaten[2];

133
        koordinaten[2] = hilf;

134
    }

135
    return koordinaten;

136
}

137
138
Würfel& Würfel::x() {

139
    Würfel tmp(*this);

140
    auto maske = Maske({0,0,1,1});  // 1 = fixiert, 0 = beweglich

141
    rotiereBenachbarteFlaechen(ZielFlaeche(0), QuellFlaeche(3), maske, orientierungX, tmp);

142
    rotiereBenachbarteFlaechen(ZielFlaeche(1), QuellFlaeche(0), maske, orientierungX, tmp);

143
    rotiereBenachbarteFlaechen(ZielFlaeche(3), QuellFlaeche(4), maske, orientierungX, tmp);

144
    rotiereBenachbarteFlaechen(ZielFlaeche(4), QuellFlaeche(1), maske, orientierungX, tmp);

145
    flaecheRotieren(Flaeche(5), orientierungX);

146
    return *this;

147
}

148
149
Würfel& Würfel::y() {

150
    Würfel tmp(*this);

151
    auto maske = Maske({1,0,1,0});   // 1 = fixiert, 0 = beweglich

152
    rotiereBenachbarteFlaechen(ZielFlaeche(0), QuellFlaeche(2), maske, orientierungY, tmp);

153
    rotiereBenachbarteFlaechen(ZielFlaeche(2), QuellFlaeche(4), maske, orientierungY, tmp);

154
    rotiereBenachbarteFlaechen(ZielFlaeche(4), QuellFlaeche(5), maske, orientierungY, tmp);

155
    rotiereBenachbarteFlaechen(ZielFlaeche(5), QuellFlaeche(0), maske, orientierungY, tmp);

156
    flaecheRotieren(Flaeche(3), orientierungY);

157
    return *this;

158
}

159
160
Würfel& Würfel::z() {

161
    Würfel tmp(*this);

162
    auto maske = Maske({0,0,1,1});   // 1 = fixiert, 0 = beweglich

163
    rotiereBenachbarteFlaechen(ZielFlaeche(2), QuellFlaeche(1), maske, orientierungZ, tmp);

164
    rotiereBenachbarteFlaechen(ZielFlaeche(3), QuellFlaeche(2), maske, orientierungZ, tmp);

165
    rotiereBenachbarteFlaechen(ZielFlaeche(5), QuellFlaeche(3), maske, orientierungZ, tmp);

166
    rotiereBenachbarteFlaechen(ZielFlaeche(1), QuellFlaeche(5), maske, orientierungZ, tmp);

167
    flaecheRotieren(Flaeche(0), orientierungZ);

168
    return *this;

169
}

170
171
void Würfel::testset1() {

172
    daten = {'Y','Y','P','R',

173
             'P','W','Y','G',

174
             'B','G','P','G',

175
             'Y','P','W','R',

176
             'W','R','R','B',

177
             'B','W','G','B'};

178
}

179
180
Würfel& Würfel::copy(const Würfel& w)

181
{

182
    daten = w.daten;

183
    return *this;

184
}

185
186
void Würfel::print() {

187
    std::cout << "Würfel:" << std::endl;

188
    for(auto f=0; f < flaeche_size; ++f) {

189
        std::cout << f << ": ";

190
        for(auto e=0; e < elemente_size; ++e) {

191
            std::cout << get(f,e);

192
        }

193
        std::cout << std::endl;

194
    }

195
}

196
197
bool Würfel::fertig() const {

198
    for(auto f=0; f < flaeche_size; ++f) {

199
        auto ref = get(f,0);

200
        for(auto e=0; e < elemente_size; ++e) {

201
            if(ref!=get(f,e))

202
                return false;

203
        }

204
    }

205
    return true;

206
}

207
208
209
class Würfelvermietung {

210
public:

211
    inline Würfel&  mieten() { return meineWürfel[freierWürfel++]; }

212
    inline Würfel&  mieten(const Würfel& w) { return meineWürfel[freierWürfel++].copy(w); }

213
214
    inline void     zurückgeben() {--freierWürfel;}

215
private:

216
    std::array<Würfel, 20> meineWürfel;

217
    int freierWürfel = 0;

218
};

219
220
static Würfelvermietung würfelvermietung;

221
222
void run(const Würfel& w, int depth, Transformationen t) {

223
    

224
    if(depth>=16) {

225
        return;

226
    }

227
    else if (depth==4) {

228
        std::cout << "Fortschritt: " << ++progress << " von " << 80 << std::endl;

229
    }

230
    

231
    if(w.fertig()) {

232
        std::cout << "fertig " << depth << std::endl;

233
        for(auto e:loesung)

234
            std::cout << e << " ";

235
        std::cout << std::endl;

236
        return;

237
    }

238
    

239
    if(t.x<3)

240
    {

241
        loesung.push_back(0);

242
        run(würfelvermietung.mieten(w).x(), depth+1, {++t.x, 0, 0});

243
        würfelvermietung.zurückgeben();

244
        loesung.pop_back();

245
    }

246
    if(t.y<3)

247
    {

248
        loesung.push_back(1);

249
        run(würfelvermietung.mieten(w).y(), depth+1, {0,++t.y,0});

250
        würfelvermietung.zurückgeben();

251
        loesung.pop_back();

252
    }

253
    if(t.z<3)

254
    {

255
        loesung.push_back(2);

256
        run(würfelvermietung.mieten(w).z(), depth+1, {0, 0, ++t.z});

257
        würfelvermietung.zurückgeben();

258
        loesung.pop_back();

259
    }

260
}

261
262
int main(int argc, const char * argv[]) {

263
    // insert code here...

264
    Transformationen t = {.x = 0, .y = 0, .z = 0};

265
    

266
    std::cout << "Suche gestartet .." << std::endl;

267
    // Würfel w;

268
    Würfel& w = würfelvermietung.mieten();

269
    w.testset1();

270
    

271
    auto timing = measure<std::chrono::milliseconds>::execution(run, w, 0, t);

272
    std::cout << "Zeit: " << timing << " ms" << std::endl;

273
    

274
    return 0;

275
}


  


  



  

  
:
    Bearbeitet durch User
  

  


  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Hab mal fix drübergeschaut und zwei Kommentare unabhängig von der 
eigentlichen Frage.

1.
1
using Flaeche = NamedType<int, struct FlaecheParameter>;

2
using ZielFlaeche = NamedType<int, struct FlaecheParameter>;

3
using QuellFlaeche = NamedType<int, struct FlaecheParameter>;

Lies dir dazu nochmal den Absatz "Using phantoms to be stronger" in 
http://www.fluentcpp.com/2016/12/08/strong-types-for-strong-interfaces/
durch. Fläche, Zielfäche und QuellFläche sind Aliase für den gleichen 
Typ. Sie helfen dir also nicht wenn du
1
foo(ZielFäche(3), QuellFläche(2));

schreibst aber die Funktion
1
void foo(QuellFäche&, ZielFläche&);

erwartet. Du bekommst also nur einen Teil der Vorteile von NamedType.

Wenn du das wirklich willst
wäre
1
using Flaeche = NamedType<int, struct FlaecheParameter>;

2
using ZielFlaeche = Fläche;

3
using QuellFlaeche = Fläche;

sinnvoller.

2.
Im gleichen Program die "guten" Strong types und die bösen globalen 
Variablen benutzen? :-)

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Hallo,

mh schrieb:

> Lies dir dazu nochmal den Absatz "Using phantoms to be stronger" in
> http://www.fluentcpp.com/2016/12/08/strong-types-for-strong-interfaces/
> durch. Fläche, Zielfäche und QuellFläche sind Aliase für den gleichen
> Typ. Sie helfen dir also nicht wenn du
>
1
> foo(ZielFäche(3), QuellFläche(2));

2
>

> schreibst aber die Funktion
>
1
> void foo(QuellFäche&, ZielFläche&);

2
>

> erwartet. Du bekommst also nur einen Teil der Vorteile von NamedType.
>
> Wenn du das wirklich willst
> wäre
>
1
> using Flaeche = NamedType<int, struct FlaecheParameter>;

2
> using ZielFlaeche = Fläche;

3
> using QuellFlaeche = Fläche;

4
>

> 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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Bert3 (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        H. S. (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Macht es nicht mehr Sinn, statt der Übergabe eines kompletten Würfels 
nur die Teiländerung in die Rekursion zu werfen?

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Josef (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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?

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  



  

  
:
    Bearbeitet durch User
  

  


  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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ürfel Würfel::x() {

2
  Würfel tmp = *this;

3
4
  // do something with tmp

5
 

6
  return tmp;

7
}

8
9
Würfel a;

10
Würfel b = 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".

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Josef (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Josef schrieb:
> Der Loesungsraum ist aber kleiner 16*(4^6) = 65536.

Sorry, die Abschaetzung ist natuerlich vollkommen falsch.
Nicht mein Tag.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Nachtrag:
Funktionsfähiges Beispiel zu NRVO http://cpp.sh/7pnqu

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  



  

  
:
    Bearbeitet durch User
  

  


  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Hallo,

nur der Vollständigkeit halber, hänge ich noch mal das Endresultat an:

1
#include <iostream>

2
#include <vector>

3
#include <array>

4
#include <chrono>

5
#include <cmath>

6
7
template<typename TimeT = std::chrono::milliseconds>

8
struct measure

9
{

10
    template<typename F, typename ...Args>

11
    static typename TimeT::rep execution(F&& func, Args&&... args)

12
    {

13
        auto start = std::chrono::steady_clock::now();

14
        std::forward<decltype(func)>(func)(std::forward<Args>(args)...);

15
        auto duration = std::chrono::duration_cast< TimeT>

16
        (std::chrono::steady_clock::now() - start);

17
        return duration.count();

18
    }

19
};

20
21
template <typename T, typename Parameter>

22
class NamedType

23
{

24
public:

25
    explicit NamedType(T const& value) : value_(value) {}

26
    explicit NamedType(T&& value) : value_(value) {}

27
    T& get() { return value_; }

28
    T const& get() const {return value_; }

29
private:

30
    T value_;

31
};

32
33
struct transformationen_t {

34
    int x;

35
    int y;

36
    int z;

37
};

38
39
using Flaeche = NamedType<int, struct FlaecheParameter>;

40
using ZielFlaeche = Flaeche;

41
using QuellFlaeche = Flaeche;

42
using Element = NamedType<int, struct ElementParameter>;

43
using Maske = NamedType<std::vector<int>, struct MaskeParameter>; // 1 = fixiert, 0 = beweglich

44
using Orientierung = NamedType<std::vector<int>, struct OrientierungParameter>;

45
using Anzahl = NamedType<int, struct AnzahlParameter>;

46
47
using TransformationsSperre = struct {int achse; int n;};

48
49
std::vector<int> loesung;

50
int progress;

51
52
class Würfel {

53
public:

54
    enum class Achse {x=0, y, z, max};

55
    

56
    void read();

57
    void print();

58
    void testset1();

59
    int& get(int,int);

60
    int  get(int,int) const;

61
    inline Würfel& copy(const Würfel&);

62
    void rotiereBenachbarteFlaechen(ZielFlaeche, QuellFlaeche, const Maske&, const Orientierung&, const Würfel& tmp);

63
    

64
    void flaecheRotieren(Flaeche, const Orientierung&);

65
    std::vector<int> koordinatenRotieren(Flaeche, const Orientierung&);

66
    

67
    Würfel& transformieren(Achse);

68
    Würfel transformierterWürfel(Achse) const;

69
    

70
    bool fertig() const;

71
    static const int flaeche_size = 6;

72
    static const int elemente_size = 4;

73
74
    std::array<int, flaeche_size*elemente_size> daten;     // flaeche*elemente_size + element

75
    

76
    

77
    static const Orientierung orientierungX;    // 0 = normal, 1 = invers

78
    static const Orientierung orientierungY;

79
    static const Orientierung orientierungZ;

80
    

81
    using Transformation = struct {

82
        std::array<int, 5> tauschen;

83
        Flaeche rotieren = Flaeche(0);

84
        Maske maske = Maske({0,0,0});

85
        Orientierung orientierung = Orientierung({0,0,0,0,0,0});

86
    };

87
    

88
    static const Transformation xTransformation_;

89
    static const Transformation yTransformation_;

90
    static const Transformation zZtansformation_;

91
    

92
    static const std::array<Transformation, 3> transformationsvektor_;

93
    

94
private:

95
};

96
97
const auto Würfel::orientierungX = Orientierung({0, 3, 0, 1, 2, 3});

98
const auto Würfel::orientierungY = Orientierung({0, 0, 0, 3, 0, 0});

99
const auto Würfel::orientierungZ = Orientierung({1, 0, 0, 0, 0, 2});

100
101
const Würfel::Transformation Würfel::xTransformation_ = {{0,3,4,1,0}, Flaeche(5), Maske({0,0,1,1}), orientierungX};

102
const Würfel::Transformation Würfel::yTransformation_ = {{0,2,4,5,0}, Flaeche(3), Maske({1,0,1,0}), orientierungY};

103
const Würfel::Transformation Würfel::zZtansformation_ = {{2,1,5,3,2}, Flaeche(0), Maske({0,0,1,1}), orientierungZ};

104
105
const std::array<Würfel::Transformation, 3> Würfel::transformationsvektor_ = {Würfel::xTransformation_, Würfel::yTransformation_, Würfel::zZtansformation_};

106
107
int& Würfel::get(int f, int e) {

108
    return daten[f*elemente_size + e];

109
}

110
111
int Würfel::get(int f, int e) const {

112
    return daten[f*elemente_size + e];

113
}

114
115
void Würfel::read() {

116
}

117
118
void Würfel::rotiereBenachbarteFlaechen(ZielFlaeche fZiel, QuellFlaeche fQuelle, const Maske& m, const Orientierung& orientierung, const Würfel& tmp) {

119
    /*   wichtig ist, dass die statischen Elemente der Zielseite natürlich nicht gedreht werden dürfen

120
     *

121
     */

122
    std::vector<int> quellKoordinaten = koordinatenRotieren(fQuelle, orientierung);

123
    std::vector<int> zielKoordinaten = koordinatenRotieren(fZiel, orientierung);

124
    

125
    for(int i=0; i<4; ++i) {

126
        if(m.get()[i]==0) {   // Bewegliches Element

127
            get(fZiel.get(), zielKoordinaten[i]) = tmp.get(fQuelle.get(),quellKoordinaten[i]);

128
        }

129
        else {

130
         

131
        }

132
    }

133
}

134
135
void Würfel::flaecheRotieren(Flaeche f, const Orientierung& orientierung) {

136
    

137
    std::vector<int> koordinaten = koordinatenRotieren(f, orientierung);

138
    

139
    for(int i=0; i<orientierung.get()[f.get()]; ++i) {

140
        auto hilf = get(f.get(), koordinaten[0]);

141
        get(f.get(), koordinaten[0]) = get(f.get(), koordinaten[1]);

142
        get(f.get(), koordinaten[1]) = get(f.get(), koordinaten[3]);

143
        get(f.get(), koordinaten[3]) = get(f.get(), koordinaten[2]);

144
        get(f.get(), koordinaten[2]) = hilf;

145
    }

146
}

147
148
std::vector<int> Würfel::koordinatenRotieren(Flaeche f, const Orientierung& orientierung) {   // gegen Uhrzeigersinn

149
    std::vector<int> koordinaten = {0,1,2,3};

150
    

151
    if(orientierung.get()[f.get()]==0) return koordinaten;

152
    

153
    for(int i=0; i<orientierung.get()[f.get()]; ++i) {

154
        auto hilf = koordinaten[0];

155
        koordinaten[0] = koordinaten[1];

156
        koordinaten[1] = koordinaten[3];

157
        koordinaten[3] = koordinaten[2];

158
        koordinaten[2] = hilf;

159
    }

160
    return koordinaten;

161
}

162
163
Würfel& Würfel::transformieren(Achse achse) {

164
    Würfel tmp(*this);

165
166
    const auto& orientierung = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].orientierung;

167
    const auto& maske = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].maske;

168
    const auto& rotieren = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].rotieren;

169
    

170
    for(int i=0; i<4; ++i) {

171
        auto ziel = ZielFlaeche(transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].tauschen[i]);

172
        auto quelle = QuellFlaeche(transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].tauschen[i+1]);

173
        

174
        rotiereBenachbarteFlaechen(ziel, quelle, maske, orientierung, tmp);

175
    }

176
    

177
    flaecheRotieren(Flaeche(rotieren), orientierung);

178
    

179
    return *this;

180
}

181
182
Würfel Würfel::transformierterWürfel(Achse achse) const {

183
    Würfel tmp(*this);

184
    

185
    const auto& orientierung = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].orientierung;

186
    const auto& maske = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].maske;

187
    const auto& rotieren = transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].rotieren;

188
    

189
    for(int i=0; i<4; ++i) {

190
        auto ziel = ZielFlaeche(transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].tauschen[i]);

191
        auto quelle = QuellFlaeche(transformationsvektor_[static_cast<std::underlying_type_t<Achse>>(achse)].tauschen[i+1]);

192
        

193
        tmp.rotiereBenachbarteFlaechen(ziel, quelle, maske, orientierung, *this);

194
    }

195
    

196
    tmp.flaecheRotieren(Flaeche(rotieren), orientierung);

197
    

198
    return tmp;

199
}

200
201
void Würfel::testset1() {

202
    daten = {'Y','Y','P','R', 'P','W','Y','G', 'B','G','P','G', 'Y','P','W','R', 'W','R','R','B', 'B','W','G','B'};

203
}

204
205
Würfel& Würfel::copy(const Würfel& w)

206
{

207
    daten = w.daten;

208
    return *this;

209
}

210
211
void Würfel::print() {

212
    std::cout << "Würfel:" << std::endl;

213
    for(auto f=0; f < flaeche_size; ++f) {

214
        std::cout << f << ": ";

215
        for(auto e=0; e < elemente_size; ++e) {

216
            std::cout << get(f,e);

217
        }

218
        std::cout << std::endl;

219
    }

220
}

221
222
bool Würfel::fertig() const {

223
    for(auto f=0; f < flaeche_size; ++f) {

224
        auto ref = get(f,0);

225
        for(auto e=0; e < elemente_size; ++e) {

226
            if(ref!=get(f,e))

227
                return false;

228
        }

229
    }

230
    return true;

231
}

232
233
void run(const Würfel& w, int depth, const TransformationsSperre& t) {

234
    if(depth>=16) {

235
        return;

236
    }

237
    else if (depth==4) {

238
        std::cout << ++progress <<" ";

239
    }

240
    

241
    if(w.fertig()) {

242
        std::cout << "fertig " << depth << std::endl;

243
        for(auto e:loesung)

244
            std::cout << e << " ";

245
        std::cout << std::endl;

246
        return;

247
    }

248
    

249
    TransformationsSperre hilf{0,0};

250
    

251
    for(int i = static_cast<std::underlying_type_t<Würfel::Achse>>(Würfel::Achse::x); i < static_cast<std::underlying_type_t<Würfel::Achse>>(Würfel::Achse::max); ++i) {

252
        

253
        if(t.achse !=i || (t.achse == i && t.n < 3)) {

254
            loesung.push_back(i);

255
            

256
            if(t.achse==i) {

257
                hilf.n = t.n+1;

258
                hilf.achse = t.achse;

259
            }

260
            else{

261
                hilf.n = 1;

262
                hilf.achse = i;

263
            }

264
            run(w.transformierterWürfel(static_cast<Würfel::Achse>(i)), depth+1, hilf);

265
            loesung.pop_back();

266
        }

267
    }

268
}

269
270
int main(int argc, const char * argv[]) {

271
    // insert code here...

272
    TransformationsSperre t = {0, 0};

273
    

274
    std::cout << "Suche gestartet .." << std::endl;

275
    Würfel w;

276
277
    w.testset1();

278
    

279
    progress = 0;

280
    auto timing3 = measure<std::chrono::milliseconds>::execution(run, w, 0, t);

281
    std::cout << "Zeit: " << timing3 << " ms" << std::endl;

282
    

283
    return 0;

284
}


  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        lalala (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Mir machen die static_cast mit underlying type leichte Bauchschmerzen. 
Vielleicht ist ein enum nicht der richtige type for diese Daten.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        mh (Gast)
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Timm R.
            (Firma: privatfrickler.de)
        (treinisch)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
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

  


  



  

  
:
    Bearbeitet durch User
  

  


  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  







      

      



  

    Re: Anregung gesucht: modern cpp und backtracking
  


  

    

      von
      
        Kurt
        (kurtcontroller)
        
      
      


      
    


    

      
    

    

    

  
  


  

  Lesenswert?
  

  •
  
  ▲  
  

  ▼  
  		
  

  


  

      
Hallo

Ist schon etwas älter.

Bekomme diese Fehlermeldung.
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

Bin gerade in der Lernphase mit C++.

Danke für eine Info.


g++ -Wall -c "wuerfel.cpp" (im Verzeichnis: 
/home/user/uebung/CPP/Uebung)
wuerfel.cpp:116:12: error: conflicting declaration ‘const auto 
Würfel::orientierungX’
  116 | const auto Würfel::orientierungX = Orientierung({0, 3, 0, 1, 2, 
3});
      |            ^~~~~~
wuerfel.cpp:86:31: note: previous declaration as ‘const Orientierung 
Würfel::orientierungX’
   86 |     static const Orientierung orientierungX;
      |                               ^~~~~~~~~~~~~
wuerfel.cpp:117:12: error: conflicting declaration ‘const auto 
Würfel::orientierungY’
  117 | const auto Würfel::orientierungY = Orientierung({0, 0, 0, 3, 0, 
0});
      |            ^~~~~~
wuerfel.cpp:87:31: note: previous declaration as ‘const Orientierung 
Würfel::orientierungY’
   87 |     static const Orientierung orientierungY;
      |                               ^~~~~~~~~~~~~
wuerfel.cpp:118:12: error: conflicting declaration ‘const auto 
Würfel::orientierungZ’
  118 | const auto Würfel::orientierungZ = Orientierung({1, 0, 0, 0, 0, 
2});
      |            ^~~~~~
wuerfel.cpp:88:31: note: previous declaration as ‘const Orientierung 
Würfel::orientierungZ’
   88 |     static const Orientierung orientierungZ;
      |                               ^~~~~~~~~~~~~
Kompilierung fehlgeschlagen.

  


  




  

    Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
  








    

    

       Thread beobachten

      |
         Seitenaufteilung abschalten

    

        


Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.



  Bestehender Account

  


  
  

  
    

      

        
          
        
        
          
        
      

      

        
          
        
        
          
        
      

    


    
    
    





  Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!

  Mit Google-Account einloggen
  





  Noch kein Account? Hier anmelden.