时间戳

首页 > 解决方案 > 欧拉项目的性能差异 B/n C++ 和 Python

python - 欧拉项目的性能差异 B/n C++ 和 Python

问题描述

我在两个平等的程序之间遇到了一个稍微奇怪的性能差异，我无法以任何真正的原因来推断差异。

我正在解决 Project Euler 问题 46。两种代码解决方案（一个在 Python 中，一个在 Cpp 中）都得到了正确的答案。但是，python 解决方案似乎性能更高，这与我的预期相矛盾。

不要担心实际的算法是最优的——我只关心它们是两个相等的程序。我确信有一个更优化的算法。

Python 解决方案

import math
import time

UPPER_LIMIT = 1000000
HIT_COUNT = 0

def sieveOfErato(number):
    sieve = [True] * number
    for i in xrange(2, int(math.ceil(math.sqrt(number)))):
        if sieve[i]:
            for j in xrange(i**2, number, i):
                sieve[j] = False
    primes = [i for i, val in enumerate(sieve) if i > 1 and val == True]
    return set(primes)

def isSquare(number):
    ans = math.sqrt(number).is_integer()
    return ans

def isAppropriateGolbachNumber(number, possiblePrimes):
    global HIT_COUNT
    for possiblePrime in possiblePrimes:
        if possiblePrime < number:
            HIT_COUNT += 1
            difference = number - possiblePrime
            if isSquare(difference / 2):
                return True
    return False

if __name__ == '__main__':
    start = time.time()
    primes = sieveOfErato(UPPER_LIMIT)
    answer = -1
    for odd in xrange(3, UPPER_LIMIT, 2):
        if odd not in primes:
            if not isAppropriateGolbachNumber(odd, primes):
                answer = odd
                break
    print('Hit Count: {}'.format(HIT_COUNT))
    print('Loop Elapsed Time: {}'.format(time.time() - start))
    print('Answer: {}'.format(answer))

C++ 解决方案

#include <iostream>
#include <unordered_set>
#include <vector>
#include <math.h>
#include <cstdio>
#include <ctime>

int UPPER_LIMIT = 1000000;

std::unordered_set<int> sieveOfErato(int number)
{
    std::unordered_set<int> primes;
    bool sieve[number+1];
    memset(sieve, true, sizeof(sieve));

    for(int i = 2; i * i <= number; i++)
    {
        if (sieve[i] == true)
        {
            for (int j = i*i; j < number; j+=i)
            {
                sieve[j] = false;
            }
        }
    }
    for(int i = 2; i < number; i++)
    {
        if (sieve[i] == true)
        {
            primes.insert(i);
        }
    }
    return primes;
}

bool isPerfectSquare(const int& number)
{
    int root(round(sqrt(number)));
    return number == root * root;
}

int hitCount = 0;

bool isAppropriateGoldbachNumber(const int& number, const std::unordered_set<int>& primes)
{
    int difference;
    for (const auto& prime : primes)
    {
        if (prime < number)
        {
            hitCount++;
            difference = (number - prime)/2;
            if (isPerfectSquare(difference))
            {
                return true;
            }
        }
    }
    return false;
}

int main(int argc, char** argv)
{
    std::clock_t start;
    double duration;
    start = std::clock();
    std::unordered_set<int> primes =  sieveOfErato(UPPER_LIMIT);

    int answer = -1;
    for(int odd = 3; odd < UPPER_LIMIT; odd+=2)
    {
        if (primes.find(odd) == primes.end())
        {
            if (!isAppropriateGoldbachNumber(odd, primes))
            {
                answer = odd;
                break;
            }
        }
    }
    duration = (std::clock() - start) / (double) CLOCKS_PER_SEC;
    std::cout << "Hit Count: " << hitCount << std::endl;
    std::cout << std::fixed << "Loop Elapsed Time: " << duration << std::endl;
    std::cout << "Answer: " << answer << std::endl;
}

我正在编译我的 cpp 代码g++ -std=c++14 file.cpp，然后使用./a.out.

在仅使用time命令行中的命令进行的几次测试运行中，我得到：

Python

Hit Count: 128854
Loop Elapsed Time: 0.393740177155
Answer: 5777

real    0m0.525s
user    0m0.416s
sys 0m0.049s

C++

Hit Count: 90622
Loop Elapsed Time: 0.993970
Answer: 5777

real    0m1.027s
user    0m0.999s
sys 0m0.013s

为什么在 python 版本中会有更多的点击，并且它仍然会更快地返回？我认为更多的点击，意味着更多的迭代，意味着更慢（而且它在 python 中）。我猜我的 cpp 代码中只是有一个性能错误，但我还没有找到它。有任何想法吗？

标签： pythonc++

解决方案

我同意 Kunal Puri 的回答，即更好的算法和数据结构可以提高性能，但它没有回答核心问题：为什么使用相同数据结构的相同算法在 python 上运行得更快。

这一切都归结为std::unordered_set和 python 的区别set。请注意，相同的 C++ 代码std::set运行速度比 python 的替代方案快，如果启用优化（使用-O2），则 C++ 代码的std::set运行速度比 python 快 10 倍以上。

有几部作品表明，以及为什么，std::unordered_set在性能方面被破坏了。例如，您可以观看C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance。似乎 python 在其set.

造成如此糟糕的一件事std::unordered_set是它要求大量的间接到达一个元素。例如，在迭代期间，迭代器指向当前存储桶之前的存储桶。要考虑的另一件事是较差的缓存位置。setpython 似乎更喜欢保留元素的原始顺序，但 GCC倾向于std::unordered_set创建随机顺序。这就是HIT_COUNTC++ 和 python 之间存在差异的原因。一旦代码开始使用，std::set那么HIT_COUNT对于 C++ 和 python 变得相同。在迭代期间保留原始顺序往往会提高新进程中节点的缓存局部性，因为它们以与分配相同的顺序进行迭代（并且新进程的两个相邻分配有更高的机会连续分配内存地址）。

推荐阅读