Python和C ++之间异常的速度差异

  • Z时代
  • 2024-01-10
  • 分类：问答

我最近写了一个简短的算法来计算python中的快乐数字。该程序允许您选择一个上限，它将确定其下的所有快乐数字。为了进行速度比较，我决定对我知道的从python到c

++的算法进行最直接的翻译。

令人惊讶的是，c

版本的运行速度明显慢于python版本。执行时间之间的准确速度测试（用于发现前10,000个快乐数字）表明python程序平均在0.59秒内运行，而c

版本平均在8.5秒内运行。

我将这种速度差异归因于这样一个事实，即我必须为已经内置在python语言中的c

++版本的部分计算（例如，确定某个元素是否在列表/数组/向量中）编写辅助函数。 。

首先，这是造成如此荒谬的速度差异的真正原因，其次，我该如何更改c ++版本以比python版本更快地执行（我认为应该如此）。

经过速度测试的两段代码在这里：Python版本，C

++版本。谢谢您的帮助。

#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"

回答：

对于100000个元素，Python代码花费6.9秒，而C ++最初花费了37秒以上。

我对您的代码进行了一些基本的优化，并设法使C 代码比Python实现快100倍以上。现在，它可以在0.06秒内完成100000个元素。这比原始C

代码快617倍。

最重要的是在发布模式下进行所有优化。在调试模式下，这段代码实际上要慢几个数量级。

接下来，我将解释我所做的优化。

  • 将所有矢量声明移出循环；用clear（）操作替换了它们，这比调用构造函数快得多。

  • 将对pow（value，2）的调用替换为一个乘法：value * value。

  • 我没有平方向量并对其求和，而仅使用整数就对值进行求和。

  • 避免了所有与整数运算相比非常慢的字符串运算。例如，可以通过重复除以10并获取结果值的模数10来计算每个数字的平方，而不是将值转换为字符串然后将每个字符转换回int。

  • 避免使用所有向量副本，首先通过将按值传递替换为按引用传递，最后避免完全消除辅助函数。

  • 消除了一些临时变量。

  • 我可能忘记了许多小细节。并行比较您的代码和我的代码，以查看我所做的工作。

通过使用预分配的数组而不是向量，可能甚至可以进一步优化代码，但这将需要更多的工作，我将其作为练习留给读者。：P

这是优化的代码：

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>
#include <windows.h>
using namespace std;
void calcMain(int upperBound, vector<int>& known);
int main()
{
    while(true)
    {
        vector<int> results;
        int upperBound;
        cout << "Pick an upper bound: ";
        cin >> upperBound;
        long start, end;
        start = GetTickCount();
        calcMain(upperBound, results);
        end = GetTickCount();
        for (size_t i = 0; i < results.size(); ++i) {
            cout << results[i] << ", ";
        }
        cout << endl;
        double seconds = (double)(end-start) / 1000.0;
        cout << seconds << " seconds." << endl << endl;
    }
    return 0;
}
void calcMain(int upperBound, vector<int>& known)
{
    vector<int> history;
    for(int i = 0; i <= upperBound; i++)
    {
        int current = i;
        history.clear();
        while(true)
        {
                int temp = current;
                int sum = 0;
                while (temp > 0) {
                    sum += (temp % 10) * (temp % 10);
                    temp /= 10;
                }
                current = sum;
                if(find(history.begin(), history.end(), current) != history.end())
                {
                        if(current == 1)
                        {
                                known.push_back(i);
                        }
                        break;
                }
                history.push_back(current);
        }
    }
}

以上是 Python和C ++之间异常的速度差异 的全部内容， 来源链接： utcz.com/qa/403644.html

回到顶部