Python, ProjectEuler, Optimierung macht Code langsamer

Question

Ich habe den folgenden Code verwendet, um Projekt Euler Frage 14 anzugehen. Für diejenigen, die diese Frage nicht kennen, muss ich die Zahl unter einer Million mit der größten Anzahl von "Schritten" finden in seiner Collatz-Sequenz.

largen = 0 

for i in range (1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 

     if k % 2 == 0: 
      k = k/2 
      n = n+1 


     else: 
      k = 3*k+1 
      n = n+1 

    if n > largen: 
     largen = n 
     answer = i 


print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

Dies gibt mir die richtige Antwort in etwa 1m20s. Ich dachte jedoch, ich könnte das auf folgende Weise beschleunigen. Zuerst wies ich das Programm an, die Anzahl der Schritte in der Kollaz-Sequenz für jeden Wert i zu speichern. Wenn ich dann beim Finden der Sequenz für eine Zahl k auf einer vorherigen Zahl lande, für die ich die Sequenz berechnet habe, würde ich einfach die Anzahl der Terme in der Folge für i zu der Zahl addieren, die ich berechnet habe so weit für k.

Zum Beispiel, sagen wir, ich versuche, die Anzahl der Schritte in der Reihenfolge für 13 zu berechnen. Die ersten 3 Schritte sind 13-40-20-10. Jetzt habe ich bereits berechnet, dass die Anzahl der Schritte in der Sequenz für 10 6 (10-5-16-8-4-2-1) ist. So ist die Anzahl der Schritte in der Sequenz für 13 die 3, die benötigt wird, um zu 10 zu kommen, die benötigt werden, um von 10 zu 1 zu kommen, d. H. Insgesamt 9 Schritte.

Zu diesem Zweck geändert ich den Code auf die folgenden:

nterms = [] # for each value i, contains number of terms in collatz sequence 
used = [] # list of used values of i (so can add nterms[i-1] to collatz sequence which redirects to i) 

largen = 0 

for i in range (1, 1000000): 

    n = 0 
    k = i 
    while k != 1: 

     if k in used: 
      n = n+nterms[k-1] 
      break 

     elif k % 2 == 0: 
      k = k/2 
      n = n+1 

     else: 
      k = 3*k+1 
      n = n+1 

    if n > largen: 
     largen = n 
     answer = i 

    used.append(i) 
    nterms.append(n) 

print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

aber wenn ich versuche, und führen Sie diese ich Memory auf dem Terminal-Bildschirm outprinted. Wenn ich kleinere Werte (d. H. Bis zu 10000) versuche, bekomme ich die gleiche Antwort wie mein ursprünglicher Code, aber viel langsamer (d. H. Dauert 7 Sekunden im Gegensatz zu 1 Sekunde).

Warum passiert das?

Answer 1

Der Gedanke der Optimierung ist in Ordnung, aber Sie haben die falsche Datenstruktur gewählt.

nterms = [] 
used = [] 

Diese beiden Listen werden verwendet, um die Collatz-Sequenz zu speichern, die Sie bereits berechnet haben, oder? Um jedoch ein Element in einer Liste zu finden, ist die Zeitkomplexität O (n), was nicht effizient genug ist.

---

Stattdessen versuchen, ein Wörterbuch verwenden, sind die Zahlen die Tasten, und deren Anzahl von Collatz-Sequenz als die Werte. Zum Beispiel hat der Schlüssel 10 einen Wert von 6.

Answer 2

Ein Element in einer Liste nachschlagen ist eine O (n) -Operation, die für große Listen ziemlich langsam werden kann. Ein Wörterbuch, andererseits garantiert eine konstante Lookup Zeitkomplexität (O (1)):

cache = {} 

for i in range (1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 

     if k in cache: 
      n = n + cache[k] 
      break 

     if k % 2 == 0: 
      k = k/2 
      n = n+1 


     else: 
      k = 3*k+1 
      n = n+1 


    cache[i] = n 
    if n > largen: 
     largen = n 
     answer = i 


print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

Auf meinem Rechner dieser Ansatz beschleunigt die Lösung um einen Faktor von etwa 13, von ~ 26 Sekunden für das OP zu ~ 2 Sekunden für das in dieser Antwort präsentierte.

Answer 3

prüfen k kann, da die Überprüfung von used verlangsamt die Berechnung gefunden werden, wenn das Element aus der Liste gefunden werden kann, hat O (n) Zeitkomplexität.

Anstatt zwei Listen zu verwenden, könnten Sie nur eine verwenden, die ursprünglich 1000000 Elemente hat, die alle auf -1 initialisiert sind.Dann bei jeder Iteration, wenn Sie die Collatz-Nummer kennen Sie es auf den jeweiligen Index aktualisieren, so dass Sie es später verwenden können:

largen = 0 
answer = 0 
memo = [-1] * 1000000 
for i in xrange(1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 
     # Since k can grow from original need to check it's within bounds 
     if k < 1000000 and memo[k] != -1: 
      n += memo[k] 
      break 
     if k % 2 == 0: 
      k /= 2 
     else: 
      k = 3 * k + 1 

     n += 1 

    memo[i] = n 
    if n > largen: 
     largen = n 
     answer = i 

Im Vergleich zur Dictionary-Cache ist dieser Ansatz etwa 10-15% schneller auf meiner Maschine.