python - 在C++中更快地执行两个程序的可能解释(与Python比较)？

更新:C++程序(如下所示)在编译时没有其他标志，即g++ program.cpp。但是，提高优化级别不会改变以下事实:蛮力运行的速度比记忆技术快(我的计算机上为0.1秒VS 1秒)。

语境

我尝试计算最长Collatz sequence的数量(
我的问题是:蛮力执行比C++中所谓的优化(记忆化)版本执行得更快的原因可能是什么？

下面是我在机器(Macbook Air)上进行的比较；时间在注释中的程序代码开头。

C++(强力)

/**
 * runs in 1 second
 */

#include <iostream>
#include <vector>

unsigned long long nextSequence(unsigned long long n)
{
  if (n % 2 == 0)
    return n / 2;
  else
  {
    return 3 * n + 1;
  }
}

int main()
{
  int max_counter = 0;
  unsigned long long result;
  for (size_t i = 1; i < 1000000; i++)
  {
    int counter = 1;
    unsigned long long n = i;
    while (n != 1)
    {
      n = nextSequence(n);
      counter++;
    }
    if (counter > max_counter)
    {
      max_counter = counter;
      result = i;
    }
  }

  std::cout << result << " has " << max_counter << " sequences." << std::endl;

  return 0;
}

C++(记忆)

/**
 * runs in 2-3 seconds
 */

#include <iostream>
#include <unordered_map>

int countSequence(uint64_t n, std::unordered_map<uint64_t, uint64_t> &cache)
{
  if (cache.count(n) == 1)
    return cache[n];

  if (n % 2 == 0)
    cache[n] = 1 + countSequence(n / 2, cache);
  else
    cache[n] = 2 + countSequence((3 * n + 1) / 2, cache);

  return cache[n];
}

int main()
{
  uint64_t max_counter = 0;
  uint64_t result;
  std::unordered_map<uint64_t, uint64_t> cache;
  cache[1] = 1;
  for (uint64_t i = 500000; i < 1000000; i++)
  {
    if (countSequence(i, cache) > max_counter)
    {
      max_counter = countSequence(i, cache);
      result = i;
    }
  }

  std::cout << result << std::endl;

  return 0;
}

在Python中，记忆技术实际上运行得更快。

Python(记忆)

# runs in 1.5 seconds

def countChain(n):
    if n in values:
        return values[n]
    if n % 2 == 0:
        values[n] = 1 + countChain(n / 2)
    else:
        values[n] = 2 + countChain((3 * n + 1) / 2)
    return values[n]


values = {1: 1}
longest_chain = 0
answer = -1

for number in range(500000, 1000000):
    if countChain(number) > longest_chain:
        longest_chain = countChain(number)
        answer = number

print(answer)

Python(强力)

# runs in 30 seconds


def countChain(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + countChain(n / 2)
    return 2 + countChain((3 * n + 1) / 2)


longest_chain = 0
answer = -1

for number in range(1, 1000000):
    temp = countChain(number)
    if temp > longest_chain:
        longest_chain = temp
        answer = number

print(answer)

最佳答案

我了解您的问题是关于两个C++变体之间的区别，而不是关于已编译的C++与解释的python之间的区别。果断地回答它，将需要在打开优化的情况下编译代码并对其执行进行性能分析。明确说明编译器目标是64位还是32位。

但是，考虑到两个C++代码版本之间的数量级，快速检查已经显示，您的备忘录消耗的资源多于获得的资源。

这里的一个重要性能瓶颈是无序映射的内存管理。 unordered_map 与buckets of items一起使用。该映射会在必要时调整存储桶的数量，但这需要分配内存(以及可能移动的内存块，具体取决于存储桶的实现方式)。

现在，如果在缓存初始化之后和显示结果之前添加以下语句，您会发现number of buckets allocated发生了巨大变化:

std::cout << "Bucket count: "<<cache.bucket_count()<<"/"<<cache.max_bucket_count()<<std::endl;

为了避免与此相关的开销，您可以在构造时预先分配存储桶的数量:

std::unordered_map<uint64_t, uint64_t> cache(3000000);

在ideone上进行此小型和非正式测试可以节省近50％的性能。

但是，没什么...在unordered_map中存储和查找对象需要计算由很多算术运算组成的哈希码。因此，我想这些操作仅比进行蛮力计算要重。