<P> 100000个元素,Python代码花费6.9秒,而C++最初占用了37秒。</p>
我对代码进行了一些基本的优化,并设法将C++代码的速度提高了100倍。现在它在0.06秒内完成100000个元素。这比原来的C++代码快617倍。</p>
<p>最重要的是在发布模式下编译,并进行所有优化。在调试模式下,这段代码实际上要慢几个数量级。</p>
<p>接下来,我将解释我所做的优化。</p>
<ul>
<li>将所有向量声明移到循环之外;用clear()操作替换它们,这比调用构造函数快得多。</li>
<li>将对pow(value,2)的调用替换为乘法:value*value。</li>
<li>我没有使用平方向量并对其调用sum,而是使用整数对值进行就地求和。</li>
<li>避免了所有字符串操作,这些操作与整数操作相比速度非常慢。例如,可以通过重复除以10并获取结果值的模10来计算每个数字的平方,而不是将值转换为字符串,然后将每个字符转换回int</li>
<li>避免了所有的向量复制,首先用passing by reference替换passing by value,最后完全消除helper函数。</li>
<li>消除了一些临时变量。</li>
<li>可能还有很多我忘了的小细节。把你的代码和我的代码并排比较,看看我到底做了什么。</li>
</ul>
<p>通过使用预先分配的数组而不是向量来优化代码是可能的,但这将是一项更大的工作,我将把它留给读者作为练习。:P页</p>
<p>下面是优化后的代码:</p>
<pre><code>#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);
}
}
}
</code></pre>