Python与C++的异常速度差

Question

我最近写了一个简短的算法来计算python中的happy numbers。这个程序允许你选择一个上限，它将决定它下面所有的快乐数字。为了进行速度比较，我决定将我所知道的算法从python直接翻译成c++。

令人惊讶的是，c++版本的运行速度明显慢于python版本。在发现前10000个快乐数字的执行时间之间进行的精确速度测试表明，python程序平均运行时间为0.59秒，而c++版本平均运行时间为8.5秒。

我将这种速度差异归因于这样一个事实：我必须为c++版本中的部分计算编写帮助函数（例如，确定元素是否在列表/数组/向量中），这些计算已经内置到python语言中。

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

这里有两段代码，带有速度测试：Python Version，C++ Version。谢谢你的帮助。

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

Answer 1

看起来像是按值将向量传递给其他函数。这将是一个明显的减速，因为程序实际上会在将向量传递给函数之前复制一个完整的向量。要解决这个问题，请传递对向量的常量引用，而不是副本。所以不是：

int sum(vector<int> given)

使用：

int sum(const vector<int>& given)

当您这样做时，您将无法再使用vector：：iterator，因为它不是常量。您需要用vector：：const_迭代器替换它。

也可以传入非常量引用，但在这种情况下，根本不需要修改参数。

Answer 2

有一个全新的、速度更快的版本，叫做a separate answer，所以这个答案被否决了。

---

我重写了你的算法，让它在找到快乐或不快乐的数字时进行缓存。我还试图使它尽可能像pythonic一样，例如通过创建单独的函数digits()和happy()。很抱歉使用了Python3，但我也会展示一些有用的东西。

这个版本要快得多。它以1.7s的速度运行，比原来的程序要快10倍（好吧，我的MacBook很老很慢：）

#!/usr/bin/env python3

from timeit import Timer
from itertools import count

print_numbers = False
upperBound = 10**5  # Default value, can be overidden by user.


def digits(x:'nonnegative number') -> "yields number's digits":
    if not (x >= 0): raise ValueError('Number should be nonnegative')
    while x:
        yield x % 10
        x //= 10


def happy(number, known = {1}, happies = {1}) -> 'True/None':
    '''This function tells if the number is happy or not, caching results.

    It uses two static variables, parameters known and happies; the
    first one contains known happy and unhappy numbers; the second 
    contains only happy ones.

    If you want, you can pass your own known and happies arguments. If
    you do, you should keep the assumption commented out on the 1 line.

    '''

#        assert 1 in known and happies <= known  # <= is expensive

    if number in known:
        return number in happies

    history = set()
    while True:
        history.add(number)
        number = sum(x**2 for x in digits(number))
        if number in known or number in history:
            break

    known.update(history)
    if number in happies:
        happies.update(history)
        return True


def calcMain():
    happies = {x for x in range(upperBound) if happy(x) }
    if print_numbers:
        print(happies)


if __name__ == '__main__':
    upperBound = eval(
            input("Pick an upper bound [default {0}]: "
                    .format(upperBound)).strip()
            or repr(upperBound))
    result = Timer(calcMain).timeit(1)
    print ('This computation took {0} seconds'.format(result))

Answer 3

100000个元素，Python代码花费6.9秒，而C++最初占用了37秒。

我对代码进行了一些基本的优化，并设法将C++代码的速度提高了100倍。现在它在0.06秒内完成100000个元素。这比原来的C++代码快617倍。

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

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

• 将所有向量声明移到循环之外；用clear（）操作替换它们，这比调用构造函数快得多。
• 将对pow（value，2）的调用替换为乘法：value*value。
• 我没有使用平方向量并对其调用sum，而是使用整数对值进行就地求和。
• 避免了所有字符串操作，这些操作与整数操作相比速度非常慢。例如，可以通过重复除以10并获取结果值的模10来计算每个数字的平方，而不是将值转换为字符串，然后将每个字符转换回int
• 避免了所有的向量复制，首先用passing by reference替换passing by value，最后完全消除helper函数。
• 消除了一些临时变量。
• 可能还有很多我忘了的小细节。把你的代码和我的代码并排比较，看看我到底做了什么。

通过使用预先分配的数组而不是向量来优化代码是可能的，但这将是一项更大的工作，我将把它留给读者作为练习。：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);
        }
    }
}