Beispiel für das Python-Effizienz-/Optimierungsprojekt Euler Nr. 5 ⇐ Python

[Guest]

Ich habe diese Lösung für Projekt Euler Nr. 5 geschrieben.

Code: Select all

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"

Mein System benötigt etwa 8,5 Sekunden.

Dann habe ich beschlossen, die Lösungen anderer Leute zu vergleichen. Ich habe dieses
Projekt Euler 5 in Python gefunden – Wie kann ich meine Lösung optimieren?

Ich hatte nicht an eine eindeutige Primfaktorzerlegung gedacht.

Aber wie auch immer, eine angeblich optimierte, nicht auf Primfaktorzerlegung basierende Lösung wurde dort veröffentlicht:

Code: Select all

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"

Benötigt mein System etwa 37 Sekunden

Mein Code ist etwa viermal schneller, obwohl ich unnötigerweise die Teilbarkeit prüfe von 3,4,5,6,7,8,9,10 und 12.

Ich bin neu in Python und habe Schwierigkeiten zu erkennen, wo die Ineffizienz liegt kommt von.

BEARBEITEN:

Ich habe einen weiteren Test durchgeführt.

Code: Select all

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"

Mein System benötigt 6 Sekunden, aber das hier:

Code: Select all

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"

Dauert etwa 3,7 Sekunden