python - 对于 Project Euler，C++ 似乎比 Python Ruby 慢得多

Question

我有 3 个来自 Project Euler 的问题的解决方案。

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

下面列出了我针对每种语言的三种解决方案。

C++:

boost::chrono::steady_clock::time_point start_time = boost::chrono::steady_clock::now();
map<int, int> square_lookup;
for(int i=0; i<= 1500; i++) {
    square_lookup[i*i] = i ;
}
auto end_time = boost::chrono::steady_clock::now();

Python2:

start = time.time()
res = range(1, 1501)
squares = {}
#square_lookups = dict(zip([x*x for x in res], res))
square_lookups = {}
for x in range(1, 1501):
    square_lookups[x*x] = x
end = time.time()

ruby :

start_time = Time.now

square_lookup = {}
(1 .. 1500).map {|x| x*x}.each_with_index do |square, root|
    square_lookup[square] = root+1
end

end_time = Time.now

四核 i5 上的时间:

> lookup gen time: 0.00141787528992 
> Python Result: 840 Time:
> 0.282248973846
> 
> Lookup gen time 4640960 nanoseconds 
> C++: Result: 840 : Time: 695301578 nanoseconds
> 
> 
> Lookup gen time 0.000729416
> Ruby: Result: 840 Time: 0.149393345

查找生成时间是构建一个包含 1500 个元素的哈希表所花费的时间，其中键是一个完美的正方形，值是它们各自的根。

即使在这方面，C++ 仍然比 Python 和 Ruby 慢。我意识到我可能拥有针对每种语言的整体最有效的解决方案，但使用相同类型的操作仍然表明 C++ 非常慢。

重要编辑 我将 map 更改为使用 unordered_map 作为 C++ 解决方案，但它仍然较慢!

修改后的 C++ 文件:http://pastebin.com/2YyB6Rfm

lookup gen time: 0.00134301185608
Python Result: 840 Time: 0.280808925629

Lookup gen time 2021697 nanoseconds
C++: Result: 840 : Time: 392731891 nanoseconds

Lookup gen time 0.000729313
Ruby: Result: 840 Time: 0.148183345

Answer 1

您的代码还有另一个严重的问题——比 map 和 unordered_map(至少是 IMO)严重得多。

特别是，你在哪里:

int result = square_lookup[(i*i) + (j*j)];

if(result)  {
    int perimeter = i + j + result;
    if(perimeter <= 1000) {
        occurences[perimeter] += 1;
    }
}

此代码不仅仅在现有 map 中查找值 i*i+j*j。相反，如果键不存在于 map 中，它会在 map 中插入一个节点，其中 i*i+j*j 作为键，0(或，更具体地说， map 的 value_type 的值初始化对象(在本例中为 int)到 map 中。

在 map 中为所有您不关心的值插入节点非常慢。您在这里要做的实际上只是检查该值是否已在 map 中。为此，您可以使用如下代码:

auto result = square_lookup.find(i*i + j*j);

if (result!=square_lookup.end())  {
    int perimeter = i + j + result->second;
    if (perimeter <= 1000) 
        ++occurences[perimeter];                
}

这使用 find 来查找键是否在映射中。然后，如果(且仅当)键在映射中，它会查找当前与该键关联的值。

这大大提高了速度——无论是使用 VC++ 还是 g++，速度都提高了大约 20-30 毫秒。

有了这个改变，map 和 unordered_map 之间的区别也缩小了。使用 map 的代码仍然可以在大约 20-30 毫秒内运行。使用 unordered_map 的代码平均来说可能只快一点点，但我的系统时钟只有 10 毫秒的粒度，所以我真的必须用更多的数据进行测试才能确定。

作为引用，这是我运行时的代码(请注意，我对代码进行了一些其他的一般清理，但其他任何事情都不会对速度产生任何重大影响):

#include <iostream>
#include <unordered_map>
#include <chrono>
#include <iterator>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

int main() {
    auto start_time = chrono::steady_clock::now();
    map<int, int> square_lookup;
    int ctr = 0;
    generate_n(inserter(square_lookup, square_lookup.end()),
        1500,
        [&]() { ++ctr;  return make_pair(ctr*ctr, ctr); });

    auto end_time = chrono::steady_clock::now();

    cout << "Lookup gen time "
        << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << "\n";

    map<int, int> occurences;
    typedef std::pair<int, int> const &map_t;

    for (int i = 0; i <= 1000; i++) {
        for (int j = i; j <= 1000; j++) {
            auto result = square_lookup.find(i*i + j*j);

            if (result != square_lookup.end())  {
                int perimeter = i + j + result->second;
                if (perimeter <= 1000)
                    ++occurences[perimeter];
            }
        }
    }

    auto it = std::max_element(occurences.begin(), occurences.end(), 
        [](map_t a, map_t b) { return a.second < b.second; });

    end_time = chrono::steady_clock::now();
    cout << "C++: Result: " << it->first << " : Time: "
        << chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() << "\n";
}

总结:在 C++ 中，map 上的 [] 运算符将插入一个不存在的项目。这可能很方便，但并不总是您想要的。如果您只想检索一个已经存在的值，那么它不是适合这项工作的工具——而且 .find 可以快得多。

一旦你纠正了这个问题，map 和 unordered_map 之间的区别(至少大部分)就消失了。