Unnötige Kopien vermeiden

[StefanUniBonn]

Objekte wie SATs oder vectoren will man normalerweise nicht unnötig kopieren, weil das Laufzeit kostet. Das machst du an sehr vielen Stellen.

1. Beispiel:

   std::vector<int> next(SAT sat, int depth){                          //findet die nächste Besetzung abhängig vn der tiefe der Suche und der aktuelle Besetzung
       std::vector<int> belegung = sat.get_belegung();
       for(int i = depth ; i > 0; i--){
               //std::cout << belegung[i] << std::endl;
               if (belegung[i] == 1){
                       belegung[i] = 0;
               }
               else if (belegung[i] == 0){
                       belegung[i] = 1;
                       break;
               } 
       }
       return belegung;
   }

   Hier git es keinen Grund, das ganze SAT zu kopieren! Du kannst stattdessen einfach std::vector<int> next(SAT const & sat, int depth) verwenden.

2. Beispiel: Um zur nächsten Belegung zu gehen, wird die Belegung beim Aufruf von get_belegung ein mal zu kopieren, dann beim Aufruf von set_belegung noch ein zweites mal, und innerhalb der Impementierung von set_belegung ein drittes mal! Hier ist ein Beispiel, wie man das besser machen könnte:

diff --git a/SAT.cpp b/SAT.cpp
index cc748c4..d4a0c32 100644
--- a/SAT.cpp
+++ b/SAT.cpp
@@ -83,24 +83,11 @@ int SAT::biggesterror(){                          //findet die grösste Variable
      return error;
 }

-void SAT::set_belegung(std::vector<int> neubelegung){       //ändert die Belegung zum gegebenen Vektor, Achtung muss die richtige Länge haben
-     belegung = neubelegung;
-}
-
-void SAT::set_belegung(int pos, int val){                   //ändert der Wert der Belegung an der gegebene Stelle zum gegebenen Wert
-     belegung[pos] = val;
-}
-
-void SAT::set_belegung(int pos){                            //ändert der Wert der Belegung an der gegebenen Stelle zum entgegengesetztes Wert, 0->1 1->0 2->2
-     if(belegung[pos] == 0){
-               belegung[pos] = 1;
-     }
-     if(belegung[pos] == 1){
-               belegung[pos] = 0;
-     }
+std::vector<int> const & SAT::get_belegung() const {        //wirft der aktuelle Belegung zurück^M
+     return belegung;^M
 }

-std::vector<int> SAT::get_belegung(){                       //wirft der aktuelle Belegung zurück
+std::vector<int> & SAT::get_belegung() {                    //wirft der aktuelle Belegung zurück^M
      return belegung;
 }

diff --git a/SAT.hpp b/SAT.hpp
index abdf45d..e0719b5 100644
--- a/SAT.hpp
+++ b/SAT.hpp
@@ -11,10 +11,8 @@ class SAT{
         int biggesterror();                                 //findet die grösste Variable die in eine fehlerhafte Klausel ist
         void print();                                       //print
         SAT(std::string filename);                          //baut SAT element aus den Textdokument
-        void set_belegung(std::vector<int> neubelegung);    //ganz neue belegung geben 
-        void set_belegung(int pos, int val);                //belegung an eine Position ändern
-        void set_belegung(int pos);                         //belegung an eine Position ändern (0 ->1, 1 ->0, 2 ->2)
-        std::vector<int> get_belegung();                    //gibt Belegung zurück
+        std::vector<int> const & get_belegung() const;      //Lesezugriff auf Belegung^M
+        std::vector<int> & get_belegung();                  //Schreibzugriff auf Belegung^M
         int variables();                                    //gibt Anxahl an Variablen zurück

     private:
diff --git a/test.cpp b/test.cpp
index eaaccf1..a4d789a 100644
--- a/test.cpp
+++ b/test.cpp
@@ -13,7 +13,7 @@ std::vector<int> backtracking(SAT sat);
 void print(std::vector<int> vec);
 std::vector<int> next(SAT sat, int depth);
 bool last(std::vector<int> belegung, int depth);
-std::vector<int> nextimp(SAT sat, int depth);
+void nextimp(SAT & sat, int depth);^M
 std::vector<int> next(std::vector<int> belegung, int depth);

@@ -29,12 +29,12 @@ int main (int argc, char** argv) {                              //liest text aus
 std::vector<int> backtracking(SAT sat){                         //setzt für jede Variable die Besetzung als falsch, falls ein Problem auftritt, versucht es richtig einzusetzen
         int var = sat.variables();
         for (int i = 0; i < var+1; i++){
-                sat.set_belegung(i, 0);
+                sat.get_belegung()[i] = 0;^M
                 bool correct = sat.verify();
                 //std::std::cout << correct << std::endl;
                 if(correct == 0){
                         //std::cout << "incorrect" << std::endl;
-                        sat.set_belegung(i, 1);
+                        sat.get_belegung()[i] = 1;^M
                         correct = sat.verify();
                         if(correct == 0){
                                 print(sat.get_belegung());
@@ -52,9 +52,8 @@ SAT backtrackingnaiv(SAT sat, int depth){                               //ruft d
         bool end = last(belegung, depth);
         while(sat.verify() == 0 & end == 0){
                 //print(sat.get_belegung());
-                std::vector<int> belegung = nextimp(sat,depth);
-                sat.set_belegung(belegung);
-                end = last(belegung, depth);
+                nextimp(sat,depth);^M
+                end = last(sat.get_belegung(), depth);^M
                 if (end == true){
                         //std::cout << "END" << std::endl;
                 }
@@ -100,8 +99,8 @@ std::vector<int> next(std::vector<int> belegung, int depth){            //gleich
         return belegung;
 }

-std::vector<int> nextimp(SAT sat, int depth){                          //findet die nächste Besetzung abhängig vn der tiefe der Suche und der aktuelle Besetzung
-        std::vector<int> belegung = sat.get_belegung();                    //diese ist die improved version von der obere und schaut sich an welche die größte Variable ist die sich in eine falsche Klausel befindet um nicht durch alle nach diese gehen zu müssen, da man direkt diese verändern kann
+void nextimp(SAT & sat, int depth){                          //findet die nächste Besetzung abhängig vn der tiefe der Suche und der aktuelle Besetzung^M
+        std::vector<int> & belegung = sat.get_belegung();                    //diese ist die improved version von der obere und schaut sich an welche die größte Variable ist die sich in eine falsche Klausel befindet um nicht durch alle nach diese gehen zu müssen, da man direkt diese verändern kann^M
         int pos = sat.biggesterror();
         if(pos != depth){
                 std::cout << "es ist besser als der normale" << std::endl;
@@ -122,7 +121,6 @@ std::vector<int> nextimp(SAT sat, int depth){                          //findet
                 //std::cout << "c" << std::endl;
                 belegung = next(belegung, pos);
         }
-        return belegung;
 }

 bool last(std::vector<int> belegung, int depth){                        //Funktion zum überprüfen ob man schon am Ende aller Besetzungen ist

Es gibt aber wie gesagt auch viele weiter Stellen, wo man Kopien vermeiden sollte

[StefanUniBonn]

Das hast du inzischen an den meisten Stellen gut umgesetzt. Vermutlich würde es aber laufzeitmäßig nochmal ganz gut helfen, wenn man die Belegung weniger oft kopieren würde! Wie oben schon erwähnt würde ich die vier Funktionen

        void set_belegung(const std::vector<int>& neubelegung);             //ganz neue belegung geben 
        void set_belegung(const int pos, const int val);                    //belegung an eine Position ändern
        void set_belegung(const int pos);                                   //belegung an eine Position ändern (0 ->1, 1 ->0, 2 ->2)
        std::vector<int> get_belegung() const;                              //gibt Belegung zurück

einfach durch eine einzige Funktion

      std::vector<int> & get_belegung()

ersetzen. Dann muss man den Code in test.cpp natürlich entsprechend anpassen, z.B. statt

                sat.set_belegung(depth, 0);

einfach

               sat.get_belegung()[0] = depth;

und statt

        std::vector<int> belegung = sat.get_belegung();                    //diese ist die improved version von der obere und schaut sich an welche die größte Variable ist die sich in eine falsche Klausel befindet um nicht durch alle nach diese gehen zu müssen, da man direkt diese verändern kann
        (...)
        sat.set_belegung(belegung);

einfach nur

        std::vector<int> & belegung = sat.get_belegung();                    //diese ist die improved version von der obere und schaut sich an welche die größte Variable ist die sich in eine falsche Klausel befindet um nicht durch alle nach diese gehen zu müssen, da man direkt diese verändern kann