python - 给定同样的一段代码，为什么 python 版本比 C 慢 100x+？

Question

我在做项目 euler Q14。

Which starting number, under one million, produces the longest collatz chain?

看到有人能在 0.7 秒内得到结果，我感到非常惊讶。当我看到它只是一个天真的蛮力解决方案时，我更加惊讶。

我很怀疑，因为我花了很多时间来优化我的 python 版本，将运行时间缩短到大约一分钟。所以我自己运行了代码……OP 没有说谎。

我将相同的代码翻译成 Python，它在 5 分钟后未能终止。

什么给了？

C 版本:http://codepad.org/VD9QJDkt

#include <stdio.h>
#include <time.h>

int main(int argc, char **argv)
{
  int longest = 0;
  int terms = 0;
  int i;
  unsigned long j;
  clock_t begin, end;
  double time_spent;

  begin = clock();

  for (i = 1; i <= 1000000; i++)
  {
    j = i;
    int this_terms = 1;

    while (j != 1)
    {
      this_terms++;

      if (this_terms > terms)
      {
        terms = this_terms;
        longest = i;
      }

      if (j % 2 == 0)
      {
        j = j / 2;
      }
      else
      {
        j = 3 * j + 1;
      }
    }
  }

  printf("longest: %d (%d)\n", longest, terms);

  end = clock();
  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("It took %f seconds\n", time_spent);
  return 0;
}

Python 版本:http://codepad.org/ZloPyEcz

import time

def iterative_brute_force(n):
    longest = 0
    terms = 0
    for i in range(1, n + 1):
        j = i
        this_terms = 1

    while j != 1:
        this_terms += 1
        if this_terms > terms:
            terms = this_terms
            longest = i

    if j % 2 == 0:
        j = j / 2
    else:
        j = 3 * j + 1

    return longest, terms

t0 = time.time()
print(iterative_brute_force(10 ** 6))
t1 = time.time()
total = t1-t0
print(total)

Answer 1

简而言之 - 它并不慢，只是卡住了。

你的 python 版本中的 while 循环是一个无限循环 - 你的缩进不包括更改 j 所以你永远不会退出它。事实上，您的程序不仅“需要更长的时间”，而且实际上完全卡住了，这应该是一个提示(不过不要难过，我曾经等了 3 天才对类似的情况深信不疑)。

这是一回事，修复它会使程序停止，但结果不正确 - 这是因为外部 for 循环也缺少缩进 - 你想对范围内的每个数字运行检查。

固定代码:

import time

def iterative_brute_force(n):
    longest = 0
    terms = 0
    for i in range(1, n + 1):
        j = i
        this_terms = 1

        while j != 1:
            this_terms += 1
            if this_terms > terms:
                terms = this_terms
                longest = i

            if j % 2 == 0:
                j = j / 2
            else:
                j = 3 * j + 1

    return longest, terms

t0 = time.time()
print(iterative_brute_force(10 ** 6))
t1 = time.time()
total = t1-t0
print(total)

给予 -

(837799, 525)
34.4885718822

而 c 版本给出 -

longest: 837799 (525)
It took 0.600000 seconds

好了，现在一切都变得有意义了，python 确实慢了，我们可以进入真正的问题了:)

但请注意 - 这远未得到优化，因为您可能会重复访问过的号码。这里更好的算法是将这些数字的结果存储在一些方便的查找表中。

---

现在，关于这里的基本问题(如您所见，即使在修复代码之后也是相关的)- 跨语言的执行时间是一个棘手的领域，即使您真正在代码中执行相同的算法，实际实现也是受编译器或解释器行为的影响 - Python 被解释，因此您的代码必须通过管理程序的另一层代码执行，而 C 仅在 native 运行。这打开了潜在的语言特性(可能还有一些优化)，并且它取决于对每个应用程序进行基准测试以了解它的工作情况，但可以肯定地说，在大多数工作负载上你会观察到 python(或其他解释语言)由于这种开销，性能会慢 10-100 倍。

此外 - 预先编译 c 代码允许您的编译器生成更好优化的代码。可以在 python 上使用 JITting 来减轻这种情况(并稍微减少解释器开销)，但它是 not available在所有 python 实现上(至少不是“纯”的)

另见讨论 - Why are Python Programs often slower than the Equivalent Program Written in C or C++?