Codeoptimierungen anhand von Beispielen

  • Schönen guten Tag Community! :)
    In der letzten Zeit habe ich mich intensiv mit Algorithmen beschäftigt, darunter auch um die Optimierungen dieser. Durch die Project Euler bin ich auf ein paar interessante Aufgaben gestoßen, welche das Thema Primzahlen betrifft. Ich bin erstaunt was sich mit ein wenig Fachwissen an einem Algorithmus alles an Geschwindigkeit heraus holen lässt. Ich möchte mit euch meine Erkenntnisse teilen und einfach mal niederschreiben was ich gelernt habe. In Zukunft werde ich Probleme so angehen, wie ich es durch diese Website gelernt habe. Nun denn, fangen wir einmal an:


    Die Primfaktorzerlegung:
    Eine natürliche Zahl über 1 lässt sich in Primzahlen zerlegen (sofern diese nicht selber eine Primzahl ist). In diesen Teilabschnitt geht es darum einen Algorithmus zu entwickeln, der eine beliebige Zahl in ihre Primfaktoren zerlegt und diese als 2 dimensionales Array aus gibt. Gehen wir beispielsweise einmal von der Zahl 140 aus, ihre Primfaktoren sind 2^2 * 5 * 7. Doch wie genau können wir jetzt vorgehen um diese Primzahlen zu ermitteln?

    Ein Denkbarer (und einfacher) Ansatz wäre, einfach die Zahl ständig durch 2 zu dividieren, bis ein Rest entsteht. Danach dividieren wir die Zahl durch 3, 4 und 5 (usw.) bis aus unserer ursprünglichen Zahl 1 geworden ist. Versuchen wir das mal mit der 140:

    Code
    140 / 2 = 70 Rest 0
    70 / 2 = 35 Rest 0
    35 / 2 = 17 Rest 1 > Da ein Rest besteht, kann 2 als weiterer Faktor nicht mehr zutreffen...
    35 / 3 = 11 Rest 2
    35 / 4 = 8 Rest 3
    35 / 5 = 7 Rest 0
    7 / 5 = 1 Rest 2
    7 / 6 = 1 Rest 1
    7 / 7 = 1 Rest 0 > Abbruchbedingung erfüllt! Ergebnis ist 1 und Rest = 0.


    Wir sehen nun in unseren Rechnungen, dass jener Divisor welche als Faktor in Frage kommt ein restloses Ergebnis liefert. Dadurch sehen wir auch welche die Primfaktoren sind und wie oft diese vorkommen. Hier der dazu passende AutoIt Code:

    Spoiler anzeigen
    [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global $zahl = 140
    Global $faktoren[Int(Sqrt($zahl))][2] ; Genug Speicher reservieren
    Global $zaehler = 0 ; Der Zähler um auf das Array zuzugreifen
    Global $divisor = 2 ; Der Divisor
    Global $time = TimerInit() ; Zum Zeit messen ^^

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    While $zahl <> 1 ; Da bei $zahl = 1 die Abbruchbedingung erfüllt ist...
    If Not Mod($zahl, $divisor) Then ; Wenn eine restlose Teilung besteht haben wir einen Faktor gefunden
    $faktoren[$zaehler][0] = $divisor ; Faktor in das Array schreiben
    $faktoren[$zaehler][1] = 1 ; Und die Anzahl

    [/autoit] [autoit][/autoit] [autoit]

    ; Den Faktor von der Zahl abziehen...
    $zahl /= $divisor

    [/autoit] [autoit][/autoit] [autoit]

    ; ... und gucken ob dieser nicht mehrmals vorkommt:
    While Not Mod($zahl, $divisor)
    $faktoren[$zaehler][1] += 1
    $zahl /= $divisor
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Da ein Faktor gefunden wurde und jetzt der nächste folgt muss der Zähler erhöht werden:
    $zaehler += 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; Nicht vergessen den Divisor um eins zu erhöhen!
    $divisor += 1
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Zuletzt das Array auf die passende Größe zuschneiden:
    ReDim $faktoren[$zaehler][2]

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    ConsoleWrite('Benötigte Zeit: ' & Round(TimerDiff($time) / 1000, 3) & ' Sekunden' & @CRLF)
    _ArrayDisplay($faktoren)

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit]

    Funktioniert doch, erste Sahne. Nun fangen wir an mit den Optimierungen an. Sicherlich fragt sich jetzt der schlaue Leser, warum überhaupt Optimierungen vorgenommen werden sollten? Tja, ich sag nur eins: Setzt doch mal die Zahl 98765432123 spaßeshalber ein und lasst euch davon die Primfaktoren ausrechnen. Mein Rechner hat 2 Minuten gebraucht um herauszufinden dass die Primfaktoren von 98765432123 = 1447^1 * 68255309^1 sind. Jetzt wird auch schnell klar weshalb das unser Algorithmus für solch eine Zahl so lange braucht. Es muss 68255309 Schleifendurchgänge durchlaufen, um auch diesen großen Primfaktor zu ermitteln. Nicht gerade optimal. Jedoch können wir mit ein wenig Know-How die Laufzeit um 50% verringern ohne dass wir auf irgend eine Akademie gegangen sein müssen. Es gibt (außer der 2) keine geraden Primzahlen! Wie denn auch? Jede gerade Zahl lässt sich durch 2 teilen und ist daher keine Primzahl, wir können uns also ersparen die geraden Zahlen zu durchlaufen und überspringen diese einfach. Das bedeutet wir müssen am Anfang überprüfen ob die Zahl durch 2 teilbar ist, danach nur noch ob diese durch eine ungerade Zahl teilbar ist. Unser Algorithmus verändert sich also folgendermaßen:

    Spoiler anzeigen
    [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global $zahl = 98765432123
    Global $faktoren[Int(Sqrt($zahl))][2]
    Global $zaehler = 0
    Global $divisor = 3 ; Da wir die Teilung durch 2 explizit behandeln können wir direkt bei 3 loslegen.
    Global $time = TimerInit()

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    ; Explizite Behandlung bei geraden Zahlen:
    If Not Mod($zahl, 2) Then
    $faktoren[0][0] = 2

    [/autoit] [autoit][/autoit] [autoit]

    While Not Mod($zahl, 2)
    $faktoren[0][1] += 1
    $zahl /= 2
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    $zaehler = 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    While $zahl <> 1
    If Not Mod($zahl, $divisor) Then
    $faktoren[$zaehler][0] = $divisor
    $faktoren[$zaehler][1] = 1

    [/autoit] [autoit][/autoit] [autoit]

    $zahl /= $divisor
    While Not Mod($zahl, $divisor)
    $faktoren[$zaehler][1] += 1
    $zahl /= $divisor
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    $zaehler += 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; Divisor muss nur noch um 2 erhöht werden
    $divisor += 2
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ReDim $faktoren[$zaehler][2]

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    ConsoleWrite('Benötigte Zeit: ' & Round(TimerDiff($time) / 1000, 3) & ' Sekunden' & @CRLF)
    _ArrayDisplay($faktoren)

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit]

    Super, damit haben wir unseren Anwender eine Wartezeit von einer Minute beschert, auf Toilette gehen kann er also auch nicht mehr, also müssen wir die Rechenzeit doch noch etwas verkürzen damit unsere Arbeit doch nicht ganz umsonst ist. Damit das allerdings klappt müssen wir eine andere Eigenschaft der Primzahlen ausnutzen. Jede Zahl kann(!) genau ein Primfaktor besitzen, welcher die Quadratwurzel der Zahl übersteigt. Dadurch müssen alle anderen Primfaktoren auf jeden Fall unter der Quadratwurzel der Zahl liegen. Damit haben wir schon mal ein Limit für unsere Schleifendurchgänge, und zwar die Quadratwurzel der Zahl. Damit können wir unseren Code noch mehr optimieren:

    Spoiler anzeigen
    [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global $zahl = 98765432123
    Global $faktoren[Int(Sqrt($zahl))][2]
    Global $zaehler = 0
    Global $divisor = 3
    Global $time = TimerInit()
    Global $wurzel

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    If Not Mod($zahl, 2) Then
    $faktoren[0][0] = 2

    [/autoit] [autoit][/autoit] [autoit]

    While Not Mod($zahl, 2)
    $faktoren[0][1] += 1
    $zahl /= 2
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    $zaehler = 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    $wurzel = Sqrt($zahl)
    While $zahl <> 1 And $divisor <= $wurzel ; Weitere Abbruchbedingung ;)
    If Not Mod($zahl, $divisor) Then
    $faktoren[$zaehler][0] = $divisor
    $faktoren[$zaehler][1] = 1

    [/autoit] [autoit][/autoit] [autoit]

    $zahl /= $divisor
    While Not Mod($zahl, $divisor)
    $faktoren[$zaehler][1] += 1
    $zahl /= $divisor
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Die Wurzel neu berechnen da sich die Zahl verändert hat:
    $wurzel = Sqrt($zahl)
    $zaehler += 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    $divisor += 2
    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Da es noch eine Primfaktor geben könnte der die Quadratwurzel übersteigt (wenn $zahl <> 1 ist):
    If $zahl <> 1 Then
    $faktoren[$zaehler][0] = $zahl
    $faktoren[$zaehler][1] = 1
    $zaehler += 1
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ReDim $faktoren[$zaehler][2]

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit] [autoit][/autoit] [autoit]

    ConsoleWrite('Benötigte Zeit: ' & Round(TimerDiff($time) / 1000, 3) & ' Sekunden' & @CRLF)
    _ArrayDisplay($faktoren)

    [/autoit] [autoit][/autoit] [autoit]

    ; ++++++++++ +++++++++ ++++++++ +++++++ ++++++ +++++ ++++ +++ ++ +

    [/autoit]

    Und wenn wir den Code jetzt ausführen, brauchen wir für die gleiche Zahl, die uns vorhin mit unverschämten 120 Sekunden geärgert hat, knapp nur noch 10 Millisekunden. Wenn das mal keine Steigerung der Geschwindigkeit von unseren ursprünglichen Algorithmus ist! Die Geschwindigkeit hat sich um den Faktor 12000 verringert! Nun könnten wir nur noch berechnen wie viele Primfaktoren in etwa die Zahl hat und somit den Speicherbedarf für das Array senken. Eine Möglichkeit wäre es, alle Primzahlen zu multiplizieren (ab 2 aufwärts) bis wir die Zahl 2^64 -1 (x64) bzw. 2^32 -1 (x86) übersteigen. Die Anzahl der Faktoren entspricht somit die Anzahl der meist möglichen Primfaktoren für den überhaupt möglichen Speicherbereich. Dadurch können wir dem Array eine fixe Größe Zuteilen dessen Anzahl der Elemente wir nicht zur Laufzeit berechnen müssen.

    >> Weiteres folgt noch...
    Gerne dürft ihr auch selber was dazu schreiben :)

    4 Mal editiert, zuletzt von Yjuq (1. April 2015 um 07:23)

  • Danke!
    Schön dargestellt.

    Lieben Gruß,
    Alina

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Geheime Information: ;)
    OuBVU5ebLhHu5QvlnAyQB4A7SzBrvWulwL7RLl2BdH5tI6sIYspeMKeXMSXl