Ich habe kürzlich einen kurzen Algorithmus zur Berechnung geschriebenglückliche zahlen in Python. Mit dem Programm können Sie eine Obergrenze auswählen und alle Glückszahlen darunter bestimmen. Für einen Geschwindigkeitsvergleich entschied ich mich für die direkteste Übersetzung des mir bekannten Algorithmus von Python nach C ++.

Überraschenderweise läuft die c ++ - Version deutlich langsamer als die Python-Version. Genaue Geschwindigkeitstests zwischen den Ausführungszeiten für die Ermittlung der ersten 10.000 glücklichen Zahlen zeigen, dass das Python-Programm im Durchschnitt in 0,59 Sekunden ausgeführt wird und die c ++ - Version im Durchschnitt in 8,5 Sekunden ausgeführt wird.

Ich würde diesen Geschwindigkeitsunterschied auf die Tatsache zurückführen, dass ich Hilfsfunktionen für Teile der Berechnungen (zum Beispiel das Ermitteln, ob sich ein Element in einer Liste / einem Array / einem Vektor befindet) in der c ++ - Version schreiben musste, die bereits in die Python-Sprache integriert waren .

Erstens ist dies der wahre Grund für solch einen absurden Geschwindigkeitsunterschied, und zweitens, wie kann ich die c ++ - Version so ändern, dass sie schneller ausgeführt wird als die Python-Version (wie es meiner Meinung nach sein sollte).

Die zwei Teile des Codes mit Geschwindigkeitstests sind hier:Python-Version, C ++ Version. Danke für die Hilfe.

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <windows.h>

using namespace std;

bool inVector(int inQuestion, vector<int> known);
int sum(vector<int> given);
int pow(int given, int power);
void calcMain(int upperBound);

int main()
{
    while(true)
    {
        int upperBound;
        cout << "Pick an upper bound: ";
        cin >> upperBound;
        long start, end;
        start = GetTickCount();
        calcMain(upperBound);
        end = GetTickCount();
        double seconds = (double)(end-start) / 1000.0;
        cout << seconds << " seconds." << endl << endl;
    }
    return 0;
}

void calcMain(int upperBound)
{
    vector<int> known;
    for(int i = 0; i <= upperBound; i++)
    {
        bool next = false;
        int current = i;
        vector<int> history;
        while(!next)
        {
            char* buffer = new char[10];
            itoa(current, buffer, 10);
            string digits = buffer;
            delete buffer;
            vector<int> squares;
            for(int j = 0; j < digits.size(); j++)
            {
                char charDigit = digits[j];
                int digit = atoi(&charDigit);
                int square = pow(digit, 2);
                squares.push_back(square);
            }
            int squaresum = sum(squares);
            current = squaresum;
            if(inVector(current, history))
            {
                next = true;
                if(current == 1)
                {
                    known.push_back(i);
                    //cout << i << "\t";
                }
            }
            history.push_back(current);
        }
    }
    //cout << "\n\n";
}

bool inVector(int inQuestion, vector<int> known)
{
    for(vector<int>::iterator it = known.begin(); it != known.end(); it++)
        if(*it == inQuestion)
            return true;
    return false;
}

int sum(vector<int> given)
{
    int sum = 0;
    for(vector<int>::iterator it = given.begin(); it != given.end(); it++)
        sum += *it;
    return sum;
}

int pow(int given, int power)
{
    int original = given;
    int current = given;
    for(int i = 0; i < power-1; i++)
        current *= original;
    return current;
}

#!/usr/bin/env python

import timeit

upperBound = 0

def calcMain():
    known = []
    for i in range(0,upperBound+1):
        next = False
        current = i
        history = []
        while not next:
            digits = str(current)
            squares = [pow(int(digit), 2) for digit in digits]
            squaresum = sum(squares)
            current = squaresum
            if current in history:
                next = True
                if current == 1:
                    known.append(i)
                    ##print i, "\t",
            history.append(current)
    ##print "\nend"

while True:    
    upperBound = input("Pick an upper bound: ")
    result = timeit.Timer(calcMain).timeit(1)
    print result, "seconds.\n"