Учитывая этот же фрагмент кода, почему версия python 100x + медленнее, чем C?

Question

Я делаю проект Эйлера Q14.

Какой стартовый номер, менее одного миллиона, производит самую длинную цепь collatz?

Я был очень удивлен, увидев кого-то, кто смог получить результат в 0,7 сек. Еще больше удивляюсь, когда вижу, что это просто наивное решение для грубой силы.

Я был настроен скептически, так как потратил столько времени, чтобы оптимизировать мою версию python, получив время работы примерно до минуты. Поэтому я сам запускал код. О. П. не лгал.

Я перевел один и тот же код на 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

Короче - это не медленнее, это просто застрял.

Цикл while в вашей версии python представляет собой бесконечный цикл - ваш отступ не включает изменение j, поэтому вы никогда не выйдете из него. Тот факт, что ваша программа не просто «занимала больше времени», а фактически полностью застряла, должна была быть подсказкой (не чувствую себя плохо, хотя я как-то ждал 3 дня, прежде чем убеждался в подобном сценарии).

Это одно, исправление, которое остановит программу, но с неправильными результатами - это потому, что для внешнего цикла также отсутствует отступ - вы хотите запустить проверку для каждого числа в диапазоне.

Исправлен код:

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 

, а с версии дает -

longest: 837799 (525) 
It took 0.600000 seconds 

Там, теперь все имеет смысл снова, питон действительно медленнее, и мы может получить реальный вопрос :)

На стороне заметки - это далеко не оптимизировано, так как вы можете повторить уже зашедшие номера. Лучшим алгоритмом здесь было бы хранение результатов для этих чисел в некоторой удобной таблице поиска.

---

Теперь, что касается основного вопроса здесь (который имеет отношения даже после фиксации коды, как вы можете видеть) - время выполнения разных языков является сложным доменом, даже если вы на самом деле выполнить тот же самый алгоритм в коде, фактическая реализация зависит от поведения компилятора или интерпретатора - Python интерпретируется, и поэтому ваш код должен выполнять через другой уровень кода, который управляет вашей программой, а C просто запускается изначально.Это открывает потенциальные возможности языка (и, возможно, некоторые оптимизации), и это будет зависеть от бенчмаркинга каждого приложения, чтобы увидеть, насколько хорошо он работает, но, вероятно, можно с уверенностью сказать, что на большинстве рабочих нагрузок вы заметите, что python (или другие интерпретируемые языки) ведет себя на 10-100x медленнее из-за этих накладных расходов.

Кроме того, скомпилировав код c заранее, ваш компилятор может создать гораздо лучший оптимизированный код. Можно использовать JITting на питон, чтобы смягчить, что (и уменьшить переводчик над головой чуть позже), но это not available на все реализации Python (по крайней мере, не «чистых» из них)

Смотрите также обсуждение на - Why are Python Programs often slower than the Equivalent Program Written in C or C++?