鉴于这段代码,为什么python版本比C语言慢100倍？

Question

我正在做项目euler Q14.

哪个起始编号低于一百万,产生最长的collat​​z链？

看到有人能在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只是本机运行.这开启了潜在的语言功能(可能还有一些优化),它将依赖于对每个应用程序进行基准测试以了解它的工作情况,但可以肯定地说,在大多数工作负载上,您将观察到python(或其他解释语言)由于这种开销,行为慢了10-100倍.

此外 - 预先编译c代码允许编译器生成更好的优化代码.可以在python上使用JITting来缓解这种情况(并稍微减少解释器开销),但它并不适用于所有python实现(至少不是"纯"实现)

另请参阅讨论 - 为什么Python程序通常比用C或C++编写的等效程序慢？