对于 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 个元素的散列 table 所需的时间，键是一个完美的正方形，值是它们各自的根。

即使在这方面，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

你声称你在计时

The lookup gen time is the time it takes to construct a hash table with 1500 elements, with the keys being a perfect square and the values being their respective roots.

Python 和 Ruby 解决方案也是如此，但在 C++ 示例中，您构建的是 std::map<int, int>。那是不是散列 table - 它是一棵红黑树。插入和查找是 O(lg N)，而不是 O(1)。

为了获得公平的比较，您希望使用 std::unordered_map<int, int> 作为您的类型。那是一个真正的散列table。

Answer 2

您的代码还有另一个严重的问题——比 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;
    }
}

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

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

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 ms g运行频率，所以我真的必须用更多数据进行测试才能确定。

作为参考，这里是我运行的代码（请注意，我对代码进行了一些其他的一般清理，但其他任何事情都不会对速度产生任何重大影响）：

#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 之间的差异（至少大部分）就会消失。

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

C++ appears to be significantly slower than both Python Ruby for Project Euler

c++

ruby

python

algorithm

performance