Python застревает при компиляции

Question

Я написал программу, которая находит наименьшее число, которое имеет каждое число от 1 до 20 как несколько. Мой код в C++ прекрасно работает и находит правильный ответ:

#include <iostream> 

using namespace std; 

int main(){ 

    for(int i = 1; i < 300000000; i++){ 

     int check = 1; 

     for(int j = 6; j <= 20; j++){ 

      if(i % j == 0){ 

       continue; 

      } else { 

       check = 0; 
       break; 

      } 

     } 

     if(check == 1){ 

      cout << i << endl; 
      break; 

     } 

    } 

} 

Однако, та же программа в Python - который работает при нахождении наименьшего числа со всеми от 1 до 10, как кратные, но только если диапазон обыскиваемого меньше (он работает с 5000000) - просто не будет компилироваться. Я продолжаю вечно, и мне нужно закрыть окно терминала.

for i in range(1, 300000000): 

    check = 1 

    for j in range(6, 21): 
     if i % j == 0: 
      continue 
     else: 
      check = 0 
      break 

    if check == 1: 
     print i 
     break 

Я использую Mac OS X Mavericks, если это уместно.

Редактировать: Я попытался переключиться на xrange, но это, к сожалению, не имеет значения.

Edit2: Я оставил его на заднем плане - на самом деле это заняло всего около 14 минут! Прошу прощения, я должен был сделать это в первую очередь.

Answer 1

Я думаю, вы используете Python 2.

Ваша задача заключается в следующем:

range(1, 300000000) 

Вы строите список 300000000 Python Int объектов. Если предположить, что ints в Python составляют 4 байта (это чрезвычайно false), то вы выделяете 300000000 × 4 = 1200000000 байт = 1 ГБ.

Вы должны заменить его следующим:

xrange(1, 300000000) 

Преимущество xrange является то, что он не предварительно выделить все Интс Python заранее. Смотрите документацию xrange для получения дополнительной информации:

Преимущество xrange() по диапазону() является минимальным [...] кроме случаев, когда очень большой диапазон используется в памяти голодали машины [... ]

с Python 3 эта проблема уже больше не существует, потому что диапазон был удален и xrange был переименован в диапазоне.

Обратите внимание, что это решит любую ошибку памяти, с которой вы столкнулись. Это не решит проблему использования плохого медленного алгоритма. Python не очень быстрый при работе с номерами (но и другие языки будут медленно работать при использовании огромных чисел).

Answer 2

Если это python 2, то вам действительно нужно изменить range на xrange. range работает, создавая список указанного размера, который вы затем выполняете по элементу по позиции. Однако в этом случае вам не нужен сам список, только индексы, которые содержались в этом списке. Поэтому вы должны предпочесть xrange, потому что это генератор, который означает, что он может выполнять итерацию без создания списка в памяти. Это избавит вашу программу от необходимости создавать действительно большой список, который займет много памяти.

Обратите внимание, что в Python 3 range имеет такое же поведение, что и у Python 2 xrange.

for i in xrange(1, 300000000): 

    check = 1 

    for j in xrange(6, 21): 
     if i % j == 0: 
      continue 
     else: 
      check = 0 
      break 

    if check == 1: 
     print i 
     break 

Также Python является интерпретируемым языком, не существует этапа компиляции, как в C++. То, что вы видите, - это просто медленное время работы.

Answer 3

Что значит «скомпилировать»? Как вы компилируете код Python?

Попробуйте использовать xrange()

Answer 4

Ваша программа Python не неправильно, это просто очень-очень медленно, потому что вы используете очень плохой алгоритм.

Попробуйте вместо этого:

def gcd(a, b): 
    while b: 
     a, b = b, a%b 
    return a 

def lcm(a, b): 
    return (a // gcd(a, b)) * b 

res = 1 
for i in range(2, 21): 
    res = lcm(res, i) 
print("Least common multiple of 1..20 is {}".format(res)) 

Edit: в качестве альтернативы, вы можете использовать свой алгоритм (но сделать это о 400x быстрее), понимая, что 19 и 20 взаимно просты, поэтому любое решение должно быть кратна 19 * 20:

UPTO = 300000000 
STEP = 19 * 20 

for i in xrange(STEP, UPTO, STEP): 
    if any(i % div for div in xrange(6, 19)): 
     continue 
    else: 
     print("Solution: {}".format(i)) 
     break 

который проходит примерно 0,94 с на моей машине (против 0.0000249 сек для «хорошего» алгоритма == около 37000 раз быстрее снова!).