Effizienz für vollkommene Zahlen

[vladima]

Hallöchen,

ich hab ein kleines Programm geschrieben, das mir ermittelt, ob eine Zahl vollkommen (also die Summe aller echten Teiler = Zahl, zB 6 = 1*2*3 = 1+2+3)

Es funktioniert auch. Nur leider seeeehr langsam.. ich wollte mir die ersten 4 vollkommenen Zahlen ausgeben lassen, aber das dauert schon ewig.

Hat jemand einen Perfomance-Tipp für mich?

Liebe Grüße!

Code: Alles auswählen

import math
def is_perfect_number(n):
    k = 1 #teiler
    sum = 0 #teilersumme
    while k <= n//2: #ich muss ja nur bis zur hälfte gehen
        if n%k == 0:
            sum += k
        k += 1
    if sum == n:
        return True
    else:
        return False

achso, und mein Codeschnippsel zur Überprüfung für die ersten 4, aber daran sollte es ja eigentlich nicht liegen

Code: Alles auswählen

def perfect_numbers(n):
    x = []
    z = 1
    while n > 0:
        if (is_perfect_number(z)):
            x.append(z)
            n -= 1
        z += 1
    return x

[narpfel]

Moin,

der Performance-Tipp wäre, die Teilersumme effizient zu berechnen.

Sonstige Anmerkungen zum Code:

• `math` wird nicht benutzt und sollte deswegen nicht importiert werden.
• Um binäre Operatoren sollten der Lesbarkeit wegen Leerzeichen gesetzt werden.

• Code: Alles auswählen

  if something:
      return True
  else:
      return False
  

  ist genau das selbe wie

  Code: Alles auswählen

  return bool(something)
  

  und wenn `something` sowieso schon ein `bool` ist (wie das Ergebnis eines Vergleichsoperators), dann wird daraus

  Code: Alles auswählen

  return something
  

• Die `while`-Schleife in `is_perfect_number` sollte eigentlich eine `for`-Schleife sein. Damit ergibt sich

  Code: Alles auswählen

  def is_perfect_number(n):
      sum = 0
      for k in range(1, n // 2 + 1):
          if n % k == 0:
              sum += k
      return sum == n
  

• Eine `for`-Schleife, die nur eine Liste erstellt oder die nur aus einer (bedingten) Anweisung besteht, kann sehr oft in eine List Comprehension oder (wie hier) einen Generatorausdruck umgewandelt werden:

  Code: Alles auswählen

  def is_perfect_number(n):
      return n == sum(k for k in range(1, n//2 + 1) if not n % k)
  

• Das gleiche gilt für `perfect_numbers`. Da bietet sich zusätzlich ein (möglicherweise unendlicher) Generator an, der sich auch in einen Generatorausdruck umwandeln lässt:

  Code: Alles auswählen

  from itertools import count
  
  def iter_perfect_numbers():
      for n in count(1):
          if is_perfect_number(n):
              yield n
  
  # als Generatorausdruck
  
  def iter_perfect_numbers():
      return (n for n in count(1) if is_perfect_number(n))
  

Benutzung:

Code: Alles auswählen

from itertools import islice
perfect_numbers = list(islice(iter_perfect_numbers(), 4))

Das waren jetzt zwar überhaupt keine (!) Performanceoptimierungen, aber trotzdem haben sie den Code bei mir um 60 % schneller gemacht (2.96 s → 1.23 s). Mit effizient berechneter Teilersumme dürfte die Laufzeit nochmal um den Faktor ~1000 schneller werden (geschätzt).

[Sirius3]

@narpfel: nicht ganz. Bis 8128 braucht meine "optimale" Version 0.18s im Vergleich zu Deiner Variante mit 1.03s, also nicht ganz Faktor 1000. Bis 33Mio dauert das natürlich quadratisch länger, und läuft noch.

[vladima]

Mit Generatoren kenne ich mich noch nicht so gut aus, werde mich da mal mehr reinarbeiten.
Danke für die ganzen Optimierungsvorschläge Werde mir das mal zu Herzen nehmen und schaue mir die effiziente Berechnung später an. Damit sind meine Fragen so weit geklärt, dankeschön!

[narpfel]

@Sirius3: Meine beste Version braucht für die ersten vier perfekten Zahlen 43.5 ms (28 mal schneller) unter Python 3 und mit PyPy3 läuft eine andere Version in 7.67 ms (160 mal schneller). Also ja, Faktor 1000 war ein wenig optimistisch.