C++ Collatz-Vermutung Optimierung

Question

In ProjectEuler Problem # 14, muss man die längste Collatz-Kette finden, bis zu 1 Million. Ich habe einen halbwegs vernünftigen Weg gefunden, aber es fühlt sich an, als wäre ich nur dumm, weil ich keinen Weg finden kann, diesen Code effizienter zu machen (der Code soll die Lösung nur ausdrucken, nachdem er getestet hat 1 bis 1 Million, hat aber nach 10 Minuten keine Ausgabe ausgedruckt). Werde ich dieses Problem falsch angehen, oder gibt es eine Möglichkeit, meinen bestehenden Code zu optimieren?

#include <iostream> 
using namespace std; 

int main() 
{ 
    int i; 
    int x; 
    int n; 
    int superN; 
    int superI; 

    superN = 0; 
    superI = 0; 

    for (i = 1; i <= 1000000; i++) { 
     x = i; 
     n = 1; 

     do { 
      if (x % 2 == 0) { 
       x = x/2; 
      } 

      if (x % 2 == 1 && x != 1) { 
       x = 3 * x + 1; 
      } 

      n++; 

      if (n > superN) { 
       superN = n; 
       superI = i; 
      } 
     } while (x != 1); 
    } 

    cout << "The number " << superI << " ran for " << superN << " terms."; 
    system("pause"); 
    return 0; 
} 

Answer 1

Sie haben ein paar kleine Probleme bekommen:

1. Ich bin ziemlich sicher, dass Sie die int Datentypen sind überfüllt. Verwenden Sie eine uint64_t, um dies weit weniger wahrscheinlich zu machen.
2. Sie sollten nur superI und superN außerhalb der While-Schleife aktualisieren. Das sollte nichts ausmachen, aber es tut der Leistung weh.
3. Bei jeder Iteration sollten Sie nur einmal x ändern. Sie können es derzeit möglicherweise zweimal ändern, wodurch Sie möglicherweise in eine Endlosschleife geraten. Und Ihre Berechnung von n wird ebenfalls deaktiviert sein.
4. Verwenden Sie Memo, um die Leistung zu verbessern, indem Sie alte Ergebnisse zwischenspeichern.

dieser Anwendung können Sie mit etwas Code wie folgt kommen:

#include <cstdint> 
#include <iostream> 
#include <map> 
using namespace std; 

int main() 
{ 
    uint64_t i; 
    uint64_t x; 
    uint64_t n; 
    uint64_t superN; 
    uint64_t superI; 

    std::map<uint64_t, uint64_t> memory; 

    superN = 0; 
    superI = 0; 

    for (i = 1; i <= 1000000; i++) { 
     x = i; 
     n = 1; 

     do { 
      if (memory.find(x) != memory.end()) { 
       n += memory[x]; 
       break; 
      } 

      if (x % 2 == 0) { 
       x = x/2; 
      } else { 
       x = 3 * x + 1; 
      } 

      n++; 
     } while (x != 1); 

     if (n > superN) { 
      superN = n; 
      superI = i; 
     } 

     memory[i] = n; 
    } 

    cout << "The number " << superI << " ran for " << superN << " terms.\n"; 
    system("pause"); 
    return 0; 
} 

Welche 4 Sekunden Ausgang nimmt:

The number 837799 ran for 556 terms. 

Answer 2

Ich würde memoization wie für mich nicht verwenden vorschlagen es läuft langsamer; In meinem Fall (bis zu 10.000.000) ist der folgende Code schneller ohne Memo. die wichtigsten Änderungen sind:

1. nur geprüft, ob die aktuelle Nummer auch nur einmal (nicht für einen brauchen else-if).
2. eine bitweise Operation anstelle der Modulo-Operation (etwas schneller)

von Apart, dass ich weiß nicht, warum Ihr Code so lang ist (meine unter 200 Millisekunden ist) vielleicht haben Sie als Debug kompilieren?

bool isEven(uint64_t value) 
{ 
    return (!(value & 1)); 
} 

uint64_t solveCollatz(uint64_t start) 
{ 
    uint64_t counter = 0; 
    while (start != 1) 
    { 
     if(isEven(start)) 
     { 
      start /= 2; 
     } 
     else 
     { 
      start = (3 * start) + 1; 
     } 
     counter++; 
    } 

    return counter; 
}