Da ich neu hier bin, versuche ich wirklich zu lernen, wie man Code so einfach wie möglich hält, während er die Arbeit macht, die er eigentlich sollte.
Die Frage, die ich gestellt habe, stammt von Project Euler , heißt es in
Jeder neue Ausdruck in der Fibonacci-Sequenz wird durch Hinzufügen der vorherige zwei Begriffe. Mit 1 anfangen und 2 sind die ersten 10 Begriffe:
%Vor%Finden Sie die Summe aller geradzahligen Terme in der Sequenz die nicht mehr als vier Millionen betragen.
Hier ist mein Code unten. Ich habe mich gefragt, was der beste Weg wäre, dies zu vereinfachen, für den Anfang alle .get (list.length () - 1) zu entfernen ..... Zeug wäre ein guter Anfang, wenn möglich, aber ich nicht wirklich wissen wie?
Danke
%Vor%Die anderen Responder haben alle gute Antworten gegeben. Ich möchte Ihnen zeigen, wie Refactoring in Aktion funktioniert, nicht nur für dieses spezifische Problem, das Dinge über Fibonacci-Zahlen kennt, sondern als einen iterativen Prozess, der den Code sorgfältig auf das Nötigste reduziert. Durch das Refactoring können wir mit der Arbeit beginnen, aber mit kompliziertem Code und Schritt für Schritt einen Schritt nach unten machen. Lassen Sie mich Ihnen alle Zwischenschritte zeigen, die Sie während der Arbeit auf dem Weg zur endgültigen Lösung machen könnten.
Hinweis: Ich habe Ihre anfänglichen Startwerte auf 1 und 1 anstelle von 1 und 2 geändert. Streng genommen beginnt die Fibonacci-Sequenz mit zwei 1en, wie in 1, 1, 2, 3, 5 ...
Wenn Sie die wiederholten list.size() - x -Ausdrücke loswerden wollen, können Sie die Zahlen in umgekehrter Reihenfolge hinzufügen. Dann ist es einfacher, die zwei letzten Zahlen zu finden.
Wechseln wir die ArrayList zu einer LinkedList . Das Einfügen am Anfang eines Arrays ist ineffizient, während es eine schnelle Operation für eine verknüpfte Liste ist.
Entlang dieser Zeilen müssen wir die get() -Aufrufe in der zweiten Schleife loswerden. Das Nachschlagen von Einträgen nach Index erfolgt langsam über verknüpfte Listen. Um dies zu tun, habe ich die zweite Schleife geändert, um for (variable: container) syntax zu verwenden.
Die nächste Optimierung besteht darin, die beiden Schleifen zu kombinieren. Anstatt zuerst alle Zahlen zu generieren und dann später nach geraden Zahlen zu suchen, können Sie beim Generieren nach geraden Zahlen suchen.
%Vor%Jetzt werden Sie vielleicht bemerken, dass Sie nie auf Zahlen jenseits von Index 1 verweisen. Zahlen an den Positionen 2 und darüber hinaus werden nie wieder verwendet. Dies deutet darauf hin, dass Sie nicht einmal mehr eine Liste aller Nummern führen müssen. Da Sie nach den geraden Zahlen suchen, wie sie erzeugt werden, können Sie jetzt alle bis auf die zwei letzten Zahlen wegwerfen.
Lassen Sie uns als kleines Detail auch value in total umbenennen.
Sie brauchen keine Liste, Sie brauchen nur zwei letzte Punkte. Hier ist ein Pseudocode, ich überlasse es Ihnen in Ihre Sprache zu übersetzen.
%Vor%Als Nächstes können Sie beobachten, dass die Zahlen immer hintereinander stehen:
%Vor%und optimieren Sie weiter, wenn Sie
benötigenSie können die Liste ganz loswerden. Behalte einfach die letzten zwei Fibonacci-Zahlen in zwei Variablen und berechne die nächste in einer Schleife (ähnlich wie bei deiner ersten Schleife).
Dann behalten Sie eine laufende Summe aller Zahlen, die die Bedingung (d. h. die sind gerade und weniger als Millionen) in der gleichen Schleife .
Vor dem Versuch, einen Code neu zu schreiben, ist es nützlich, einen Komponententest durchzuführen. Selbst die offensichtlichste Veränderung kann etwas Unerwartetes zerstören.
Zweitens ist es wichtig, sehr vorsichtig zu sein. Sie werden oft im Code sehen, dass X-Aufrufe an dieselben Funktionen durch einen Aufruf, Zuweisung an Variable und Verwendung dieser Variablen ersetzt werden können.
Allerdings musst du vorsichtig sein. In Ihrem aktuellen Code können Sie beispielsweise list.size () nicht wirklich ersetzen, da sich die Größe zwischen den Aufrufen in derselben Iteration ständig ändert.
Was Ihren Code meist schwer verständlich macht, ist, dass Sie beim Aktualisieren der Listen auf Listenindizes verweisen. Sie müssen Indizes in Variablen speichern, in mehrere Zeilen aufteilen und eventuell einige Kommentare hinzufügen, um sie lesbarer zu machen.
Ich würde die Liste fallen lassen. Sie machen hier zwei Iterationen, wenn Sie nur noch die Sequenz durchlaufen und eine Tally-Variable beibehalten müssen.
Um eine einfache Iteration über die Sequenz durchzuführen, müssen Sie nur die zwei letzten Werte ( f (n) und f (n-1) ) und notieren (abhängig von Ihrer Sprache) eine temporäre Variable für das Aktualisieren dieser Werte. Normalerweise etwas in der Art von:
%Vor% Der Simple-Ansatz ist eine grundlegende for-Schleife. Oder Sie können Ihre eigene Klasse rollen, die die Iterator<E> Schnittstelle, wenn Sie ganz OO darüber sein wollten. Dann könnte Ihr Code so einfach sein wie:
Das erinnert mich daran, dass ich eines Tages wieder in Euler zurückkehren muss.
Mein Rat wäre dies (ich werde keine Antwort geben, da es immer am besten ist, selbst zu den Schlussfolgerungen zu kommen)
Denken Sie darüber nach, warum Sie die Werte der Sequenz speichern müssen? Dein Programm wird 4000000 Ganzzahlen in einem großen Array speichern, ist das wirklich nötig? Du könntest einfach 2 Gegenstände benutzen und durch die Fibonacci Berechnung gehen, indem du die geraden Zahlen zu einer Gesamtvariablen hinzufügst.
Nun, für eine Sache, ein Mitglied der Fibonacci-Folge wird durch die beiden vorherigen Werte, bevor es erzeugt. Warum nicht einfach zwei Zahlen im Puffer behalten und testen, ob die Zahl gerade ist. Wenn es auch, fügen Sie Ihre Summe ist und stoppen, wenn Sie vier Millionen erreichen.
code:
%Vor%Wie @John Kugelmans Lösung, aber effizienter. Dies wird nur 1/3 der Zeiten wiederholen und jede Schleife ist kürzer mit weniger Verzweigungen und es ist kein gleichmäßiger Test erforderlich. Dies nutzt die Tatsache aus, dass jeder dritte fib-Wert gerade ist und berechnet nur die Werte dazwischen, um den a- und b-Wert zurückzusetzen.
%Vor%Tags und Links java refactoring