Пример проекта Эйлера № 5 по эффективности/оптимизации Python ⇐ Python

[Anonymous]

Я написал это решение для проекта Эйлера №5.

Код: Выделить всё

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

a = m
start = 2
while (m % start) == 0:
start += 1

b = start
while b < m:
if ( a % b) != 0:
a += m
b = start
continue
else:
b += 1
return a

import sys

if (len(sys.argv)) > 2:
print "error: this function takes a max of 1 argument"
elif (len(sys.argv)) == 2:
print ProjectEulerFive(int(sys.argv[1]))
else:
print ProjectEulerFive();

print "took " + str(time.time() - start_time ) + " seconds"

Моя система занимает около 8,5 секунд.

Затем я решил сравнить решения других людей. Я нашел этот
Проект Эйлера 5 на Python: как оптимизировать свое решение?

Я не думал об уникальной факторизации простых чисел.

Но в любом случае там опубликовано одно предположительно оптимизированное решение, основанное на непростой факторизации:

Код: Выделить всё

import time
start_time = time.time()

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
for num in xrange(step, 999999999, step):
if all(num % n == 0 for n in check_list):
return num
return None

if __name__ == '__main__':
solution = find_solution(20)
if solution is None:
print "No answer found"
else:
print "found an answer:", solution

print "took " + str(time.time() - start_time ) + " seconds"

В моей системе это занимает около 37 секунд.

Мой код работает примерно в 4 раза быстрее, хотя я без необходимости проверяю делимость из 3,4,5,6,7,8,9,10 и 12.

Я новичок в Python, и мне трудно понять, в чем заключается неэффективность исходя из.

РЕДАКТИРОВАТЬ:

Я провел еще один тест.

Код: Выделить всё

import time
start_time = time.time()

def ProjectEulerFive (m = 20):
ls = [11, 13, 14, 15, 16, 17, 18, 19]
a = m
i = 0
while i < len(ls):
if ( a % ls[i]) != 0:
a += m
i = 0
continue
else:
i += 1
return a

print ProjectEulerFive();
print "took " + str(time.time() - start_time ) + " seconds"

У моей системы это занимает 6 секунд, но это:

Код: Выделить всё

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

a = m
start = 11

b = start
while b < m:
if ( a % b) != 0:
a += m
b = start
continue
else:
b += 1
return a

print ProjectEulerFive()
print "took " + str(time.time() - start_time ) + " seconds"

Занимает около 3,7 секунды

Подробнее здесь: https://stackoverflow.com/questions/114 ... -5-example