Das deutsche Python-Forum

Gudde ich bräuchte Hilfe dabei, meinen Code kürzer zu halten und schneller zu machen.
Ich versuche mich gerade am project euler, allerdings habe ich öfter das Problem, dass meine Berechnungen einfach zu langsam sind.
Falls mir jemand helfen kann und/oder Tipps und Tricks an mich weitergeben kann, wäre ich sehr dankbar.

Hier der Code:
http://www.python-forum.de/pastebin.php ... &mode=view

@Septimus: Als erstes mal könntest Du die Einschränkung a < b < c aus der Aufgabe auch in Deinen Quelltext aufnehmen. Also bei Dir wäre das h < i < j und Du testest auch Werte die nicht dieser Beschränkung unterliegen, also letztendlich testest Du zu viele Werte.

Edit: Als nächstes könntest Du auch geziehlt nur Werte erzeugen, deren Summe = 1000 ist. Das heisst für den letzten Wert bräuchtest Du keine Schleife mehr, weil der sich aus den anderen beiden zwangsläufig ergibt.

Edit2: Auf was für einem Rechner hast Du das denn ausgeführt? Selbst Dein „langsamer” Ansatz braucht bei mir ca. 8 Sekunden, also weit entfernt von den 2+ Stunden, die Du in den Kommentaren angibst.

Jo mein Rechner ist schon 4 Jahre alt und dementsprechend ''schnell''.
Ich muss mir sowieso bald einen neuen für die Uni kaufen, das sollte also kein Problem sein.

Für die Tipps danke ich schonmal sehr. Ich versuche mal, es so hinzubekommen, dass ich das unnötige rauswerfe.

Bei dem Skript war das Problem ja noch nicht so schlimm, dass es mich beim Lösen der Aufgabe gehindert hat, allerdings hab ich bei der Aufgabe danach noch ein viel größeres Zeitproblem. Ich hab's extra von nem Freund auf einem relativ schnellen Rechneer laufen lassen, dort hat es aber auch nach ein paar Stunden nichts ausgegeben.
Hier der Code:
http://www.python-forum.de/pastebin.php?mode=view&s=367

Vorallem in der Funktion für das Sieb habe ich das Gefühl, dass ich da noch viel verbessern kann. Nur hab ich nicht wirklich ne Ahnung, was genau sich verbessern lässt.
Aufgabe ist es, alle Primzahlen bis 2 000 000 zu addieren. Mein Ansatz ist, eine Liste mit den Primzahlen mit dem Sieb von Eratosthenes zu erstellen und diese dann zu addieren.

edit:
Das Problem 9 kann ich jetzt dank deiner Tipps in wenigen Sekunden berechnen. Fettes Dankeschön
http://www.python-forum.de/pastebin.php?mode=view&s=368
Da sieht man mal, was so kleine Änderungen bringen können.

@Septimus: eigentlich hätte Dir auffallen sollen, dass Du in »euler10« eine andere Art Sieb benutzt als Du in »esieve« erzeugst. Würdest Du das Sieb so aufbauen, wie Du es in »euler10« brauchst, wäre es auch viel schneller.

@Septimus: Deine Siebfunktion ist was die Effezieht angeht superschlecht. Jedes mal wenn Du mit ``in`` eine Zahl suchst, wird die Liste von vorne Element für Element durchgegangen bis die Zahl gefunden wurde oder bis alle Elemente angeschaut wurden. Und beim `remove()` passiert dann noch einmal genau das selbe. Und wenn die Zahl gefunden wurde, werden alle Elemente die danach kommen, im Speicher um eine Position nach „vorne” kopiert. Da werden millionenfach Millionen von Elementen durchsucht und im Speicher herum kopiert.

Das Sieb wird normalerweise als Liste von `n` Wahrheitswerten implementiert, die angeben ob der Index an der Stelle eine Primzahl ist oder nicht. Da lässt sich dann ganz einfach prüfen ob eine Zahl noch als Primzahl gilt und statt die Vielfachen zu Entfernen werden die Elemente einfach auf `False` gesetzt.

Die Funktion zur Berechnung der Summe berechnet auch etwas ganz falsches bei dem Ergebnis was Deine Siebfunktion liefern würde. Zusätzlich ist ``for i in range(len(sequence)):`` in Python ein „anti pattern”. Das macht man nicht, weil man *direkt* über die Elemente von Sequenzen iterieren kann. Sollte man *zusätzlich* noch einen Index benötigen, gibt es die `enumerate()`-Funktion. Das ``+ 1`` würde hier auch unweigerlich zu einem `IndexError` führen, denn den Index ``len(L)`` gibt es nicht. Die Zählung fängt ja bei 0 an, also ist der letzte Index von L ``len(L) - 1``.

``+=`` auf Listen verwendet kaum jemand. Das hat den gleichen Effekt wie `.extend()`. Und wenn man `.extend()` grundsätzlich mit einer literalen Liste mit *einem* Element aufruft, möchte man eigentlich die `append()`-Funktion verwenden.

Okay das ist ja schon relativ viel, was ich verbessern kann.

Also ist das Prinzip eine Liste voll mit True Werten zu erstellen und dann die True Werte auf den entsprechenden Indizes aus False zu setzen?

Die enumerate Funktion setzt dann für jedes Element eine Zahl, praktisch wie eine ID, und die Rechne ich dann zusammen?
Ich kenn mich leider nur mit den Grundfunktionen aus, deshalb frag ich lieber, bevor ich was falsch reinsetze.

Auch bei der .append() Funktion bin ich unsicher, ob ich die richtig verstanden habe.
Kann ich für diese Funktion einfach schreiben, wird ''True'' dann in die Liste geschrieben?

Septimus hat geschrieben:Auch bei der .append() Funktion bin ich unsicher, ob ich die richtig verstanden habe.
Kann ich für diese Funktion einfach

Code: Alles auswählen

L.append(True)

schreiben, wird ''True'' dann in die Liste geschrieben?

Das Tutorial sagt hier: "Add an item to the end of the list".

Wie soll man es anders erklären?

Wenn das Programm wirklich auf Effizienz getrimmt werden soll, sind da Listenoperationen da noch eine Wahl? Ich würde mir mal Gedanken darüber machen, was für Datenstrukturen geeigneter sind.

@Septimus: Die `enumerate()`-Funktion liefert Tupel aus Index (oder fortlaufender Zahl) und Elementen aus dem übergebenen iterierbaren Objekt. Die Funktion ist dokumentiert. Mit Beispiel. Und die `append()`-Methode auf Listen sollte eigentlich in jedem Grundlagentutorial vorkommen. Ausserdem kann man so etwas auch ganz einfach in einer Python-Shell ausprobieren.

Die Liste kannst Du aber auch ohne `append()` erstellen, in dem Du die Multiplikation einer Liste mit einer Zahl verwendest: Verbesserungen für das Sieb: Man kann beim Aussieben die geraden Zahlen ignorieren wenn man die 2 als einzige gerade Primzahl gesondert behandelt. Und man muss nur bis zur Wurzel von `n` gehen um die Vielfachen zu streichen.

Über die 2+ Stunden komme ich immer noch nicht hinweg. Ich habe das eben mal auf einem RaspberryPi laufen lassen (ARM6 Prozessor mit 800Mhz) während ich damit einen Film geschaut habe. Es hat knapp 6 Minuten gedauert das Ergebnis zu finden. Mit was für einer Hardware kommt man auf 2+ Stunden?

@darktrym: Worauf willst Du hinaus? Die normale Implementierung des Siebs macht man mit einer Liste und die ist eigentlich auch hinreichend Leistungsstark.

Die Aussage bezog sich erstmal auf euler10.
Es ist doch verrückt viele Elemente einer Liste hinzuzufügen um anschließend viele davon wieder zu entfernen.

Was mir gerade auffällt:
Ich hab in dem skript zu euler10 statt eine 2 000 000 eine 100 000 eingesetzt, die ich zu Testzwecken eingefügt hatte, das kann die kurze Rechenzeit erklären.

Ich bin im Moment nur mit Schulwissen unterwegs, was über ein Halbjahr ging.
Und ich bin gerade dabei, verschiedene Python Tutorials zu Grundlagen durchzuarbeiten, um wieder ein bischen reinzukommen, damit ich in der Uni weniger Probleme hab.
Bisher bin ich aber in keinem auf die beschriebenen Funktionen gestoßen.

Also im Moment hab ich folgende Verbesserungen im Kopf:
1. Liste erstellen mit 2. Die Liste mit dem Sieb bearbeiten, indem ich alle durch andere Zahlen restlos teilbaren Indizes auf False setze.
3. Den Werten der Liste mit enumerate() die entsprechenden Zahlen zuordnen
Anschließend auf den ersten Wert der Tupel in der Liste zugreifen und diese dann addieren. Um auf das Element im Tupel in der Liste zuzugreifen muss ich Liste[Tupelindex][Elementindex] soweit ich weiß.

Ich mach mich dann mal an die Umsetzung.

edit:
Hier die Überarbeitete Version:
http://www.python-forum.de/pastebin.php?mode=view&s=369

@Septimus: Wenn Du eine Liste mit Tupeln hättest, dann wäre ``liste[index_des_tupels][index_des_elements_im_tupel]`` richtig, aber so eine Liste hast Du ja nicht. Du hast eine Liste mit Wahrheitswerten. Oder das gleiche etwas kompakter als „list comprehension” (LC) formuliert: Man könnte auch eine Generatorfunktion schreiben, die per ``yield`` die Primzahlen liefert sobald man beim sieben auf sie stösst. Damit spart man sich den letzten Schritt eine Liste daraus zu erstellen.

Und die `sum()`-Funktion sollte man in diesem Zusammenhang vielleicht noch erwähnen.

BlackJack hat geschrieben:@Septimus: Wenn Du eine Liste mit Tupeln hättest, dann wäre ``liste[index_des_tupels][index_des_elements_im_tupel]`` richtig, aber so eine Liste hast Du ja nicht. Du hast eine Liste mit Wahrheitswerten.

Code: Alles auswählen

    result = list()
    for i, is_prime in enumerate(sieve):
        if is_prime:
            result.append(i)
    return result

Oder das gleiche etwas kompakter als „list comprehension” (LC) formuliert:

Code: Alles auswählen

    return [i for i, p in enumerate(sieve) if p]

Man könnte auch eine Generatorfunktion schreiben, die per ``yield`` die Primzahlen liefert sobald man beim sieben auf sie stösst. Damit spart man sich den letzten Schritt eine Liste daraus zu erstellen.

Und die `sum()`-Funktion sollte man in diesem Zusammenhang vielleicht noch erwähnen.

Also spricht die 1. Zeile alle Elemente der Liste and, dann überprüft die 2. Zeile, ob ein True Wert in dem Element ist, dann wird das element, falls dies der Fall ist in der 3. Zeile der Ergebnisliste hinzugefügt. Richtig verstanden so?
Wie funktioniert das denn mit der 2. Zeile, wo ''if is_prime'' steht? Wird dann für das Tupel abgefragt, ob sich in dem Tupel ein True befindet?

Im Zusammengefassten Code heißt das also i wird ausgegeben, nachdem mit i die Tupel der Liste durchlaufen wurden und mit p geguckt wurde, ob sich ein True Wert in dem entsprechenden Tupel befindet.
Zu dem 1 Zeilen Code:
Heißt das, dass bei ''...i for i, p...'' erstmal der Rückgabe Wert, also i Festgelegt wird, wobei i dann dem ersten Element des Tupels entspricht und p dem zweiten Element des Tupels?
Mit dem [] um die Ausgabe macht man dann daraus ein Element einer Liste?
Und weil nur der Index i in die Ergebnisliste geschrieben wird, brauche ich bei der Summierung mit sum() auch nicht den Bool Wert zu beachten, da er garnicht in der Egebnisliste vorhanden ist.

edit:
hab eben noch was bemerkt:
Bei Sollte es eigentlich sein, sonst fängt das Teil an der falschen Stelle an und liefert falsche Ergebnisse.

edit2:
Hier der nochmal überarbeitete Code:
http://www.python-forum.de/pastebin.php?mode=view&s=370

@Septimus: In der Schleife und in der „list comprehension” passiert ganz normales „tuple unpacking”, wie das auch bei anderen Zuweisungen passieren würde. Zwischen ``for`` und ``in`` darf das selbe stehen, was man auch links von einer Zuweisung mit ``=`` schreiben kann. Das ist ja auch das was im Grunde am Anfang von jedem Schleifendurchlauf passiert — eine Zuweisung an das was zwischen ``for`` und ``in`` steht. „Tuple unpacking” ist zwar als Begriff nicht ungebräuchlich, aber es ist eigentlich viel allgemeiner: Rechts muss etwas iterierbares stehen was so viele Elemente liefert wie von der linken Seite ”aufgenommen” werden. Also man kann rechts auch Listen oder andere iterierbare Objekte verwenden.

Das mit dem Startwert ist nötig weil Du die 0 nicht in der Liste abbildest. Was ich gemacht hätte. Das ist nur ein zusätzlicher Wert, dafür spart man aber bei jedem Zugriff per Index die Rechenoperation den Index um 1 anpassen zu müssen.

Zeile 5 ist überflüssig. Und Zeile 12 im Grunde auch. Insbesondere würde ich da nicht tatsächlich erst einmal eine Liste mit 2 Millionen Tupeln erstellen.

Das dürfte so auch noch nicht funktionieren. Du filterst da nicht nur Nicht-Primzahlen, sondern ziemlich gründlich und unnötig mehrfach *alle* Zahlen aus der Liste raus.

Statt einer „list comprehension” könnte man auch aus den eckigen Klammern um den Ausdruck runde Klammern machen. Dann hat man einen Generator-Ausdruck und spart Speicher, weil die Liste mit den Primzahlen nicht erstellt wird.

Edit: Ich hoffe übrigens, dass Du Python 3 verwendest, denn sonst wären die `range()`-Aufrufe anstatt `xrange()` vielleicht auch ein Bremsklotz bei vielen Aufrufen und langen Listen.

Komisch. Ich hab damit das Ergebnis berechnet und project Euler sagt mir, dass das Ergebnis(142913828922) richtig ist.
Die 0 ist ja nicht in der Liste, da ich genau 2 000 000 Elemente in die Liste schreibe, also von 1 - 2 000 000. Das Start=1 ist dann nötig, damit die Nummerierung der Listen-Elemente bei 1 anfängt und nicht bei 0.

Ich hab mal versucht in der 2. Schleife auch n**0.5 einzusetzen, das hat allerdings das Ergebnis verändert, deshalb hab ich das wieder entfernt.

Und ja ich benutze Python 3. Da brauch ich mir keine Gedanken über die Länge der Integers zu machen und xrange oder range ist egal.

@Septimus: Okay, mich hatte der Name `primzahl` verwirrt, denn da werden ganz offensichtlich keine Primzahlen dran gebunden oder wenn, dann nur zufällig. Solltest Du vielleicht ändern den Namen.

Und dann solltest Du die innere Schleife nur so oft durchführen wie nötig. So wie es im Pastebin steht wird die bei Dir 2,8 *Milliarden* mal durchlaufen. Wenn etwas was ”nur” 50 Millionen mal durchlaufen wird, bei Dir schon mehr als 2 Stunden dauert, dann dürftest Du hier das Ergebnis noch nicht gesehen haben. So etwas um die 4 bis 4½ Millionen Durchläufe des Codes in der innersten Schleife sollten für Primzahlen bis 2 Millionen nicht überschritten werden müssen.

Mir ist schon klar *das* Du den Elementen in der Liste die Werte 1 bis 2.000.000 zuordnest, nur nicht *warum* Du das machst. Denn nur deswegen musst Du beim `enumerate()` einen Startwert von 1 angeben und beim Indexzugriff auf die Liste immer 1 von der Zahl abziehen. *Beides* könnte man sich sparen. Man verbraucht einen Listenplatz mehr, muss den mit `False` belegen, und beim letzten Schritt eine Nicht-Primzahl mehr einfach überlesen. Dem Gegenüber stehen ca. vier Millionen mal eine 1 vom Index abziehen wenn man es richtig macht, oder eben 2,8 Milliarden mal in Deinem Fall, die man sich an Rechenzeit sparen kann.

Hmm jo hast schon recht, aber ich bezweifle mal, dass die eine Position sehr viel Unterschied macht. Ich würde ja nur die Summe am Anfang 1 setzen und dann den einen Eintrag der Liste weglassen, der sowieso übersprungen wird bei der Berechnung.
Ist wirklich unnötig, aber für mich ist das jetzt nicht so signifikant, dass ich es unbedingt weglassen würde. Die Idee hinter dem Algorithmus ist so besser erhalten, so kann ich wenn ich später darauf zurückgreifen muss, besser nachvollziehen, was ich gemacht hab.

Ich hab auch mal die Zeit für die Berechnung gestoppt:
2066.5651290876353 Sekunden oder 34.44 Minuten hat's gedauert. Wieso das so viel weniger dauert, kann ich aber auch nicht feststellen.

@Septimus: Ich habe es ja schon geschrieben: Du tauschst ein gespartes Element und minimale, konstante Zeit für dessen Initialisierung und überspringen, gegen die Zeit für sehr viele Rechenoperationen.

Die Idee des Algorithmus verändert sich doch dadurch kein bisschen, im Gegenteil es ist sogar etwas klarer wenn man sagen kann der Index in die Liste entspricht genau der Zahl für den der Wahrheitswert angibt ob es eine Primzahl ist oder nicht. Statt das der Index plus 1 dieser Zahl entspricht, weswegen man von der Zahl 1 abziehen muss um den Index zu erhalten.

Wieso *was* so viel weniger dauert? Warum 2,8 Milliarden innere Schleifendurchläufe lange dauern kann ich Dir sagen: Weil das verdammt viele sind. Und zwar um Grössenordnungen *zu* viele. Die Frage ist eher warum die 50 Millionen Durchläufe bei Euler9 bei Dir angeblich so lange brauchen.

Schau Dir hier doch mal an wie oft Du die innere Schleife durchläufst obwohl ``primzahl * h`` schon deutlich über `n` liegen, also völlig unnötig. Wenn man sich das Siebverfahren anschaut, dann wird das ja eigentlich immer so beschrieben, dass man die nächste Primzahl sucht, und dann alle Vielfachen davon streicht. Du suchst aber nicht nach Primzahlen sondern streichst Vielfache von allen möglichen Zahlen, auch von solchen die keine Primzahlen sind, aber durch das streichen von Primzahlen sowieso schon eliminiert wurden. Plus die Obergrenze die Du so ungünstig hoch festsetzt. Man kann die innere Schleife schon direkt über Vielfache von einer Zahl bis `n` laufen lassen — `range()` kennt auch drei Argumente. Dann hätte man ausserdem die Multiplikation durch Additionen ersetzt, was eventuell schneller abgearbeitet wird.

Ja ich sehe jetzt, was du meinst mit viel zu viele Berechnungen.
Ich hab bei der inneren Schleife jetzt ein else: break eingefügt, die Berechnung dauert jetzt nurnoch 22 Sekunden.

Vorher war mir nicht so wirklich klar, wo ich einsparen sollte, aber da hatte ich wohl einfach nen Brett vor'm Kopp u_u'

Das Problem, das ich beim anpassen der inneren Schleife im Moment habe ist, dass sich das Ergebnis verändert, wenn ich in h-Schritten laufen lasse oder die obere Grenze niedriger setze. Ich blick da glaub ich noch nicht ganz durch, was ich da verändere. Ich setz mich mal morgen Abend nochmal dran, dann kann ich vielleicht besser arbeiten.

Zum Thema langsam und Euler 9: Dein erster hier gezeigter Ansatz als BASIC-Programm für den C64:
[codebox=locobasic file=Unbenannt.txt]10 TI$="000000":X=500:Y=1000
20 FOR A=1 TO X:FOR B=1 TO X:FOR C=1 TO X:IF A+B+C=Y AND A*A+B*B=C*C THEN 40
30 NEXT:NEXT:NEXT
40 PRINT A,B,C
50 PRINT TI$[/code]
Lief über Nacht, und ich habe es heute morgen mal unterbrochen um zu sehen wie weit es gekommen ist. Die äussere Schleife ist in 14 Stunden und 42 Minuten gerade einmal 12 mal durchlaufen worden. Hochgerechnet auf den gesamten Suchraum wären das cirka 25½ Tage. Da wir das Ergebnis ja schon kennen, kann man abschätzen, dass der C64 ”schon” nach cirka 10 Tagen das Ergebnis ausspucken wird. Oder würde — ich lasse das jetzt mal nicht weiterlaufen.

Eine Variante die gezielt nur A, B, und Cs generiert die zusammenaddiert 1000 ergeben kommt schon nach 46½ Minuten zum Ergebnis. Mit Basic-Boss kompiliert läuft es nur noch 24 Minuten.
[codebox=locobasic file=x]1 REM@ £PROTOCOL:£FASTFOR:£FASTARRAY:£SHORTIF
2 REM@ £CONSTANT X,Y,Z
10 TI$="000000":X=1000:Y=999:Z=998
20 FOR A=1 TO Z:FOR B=A+1 TO Y-A:C=X-A-B:IF A*A+B*B=C*C THEN 40
30 NEXT:NEXT
40 PRINT A,B,C
50 PRINT TI$[/code]
Man kann A, B, und C für den Compiler leider nicht einfach als WORD deklarieren, weil dann die Berechnung der ``IF``-Bedingung nicht mehr korrekt berechnet wird, da die Zwischenergebnisse der Rechnung die 16-Bit-Grenze sprengen.

Nur mit ganzen Zahlen geht es in C mit dem cc65-Cross-Compiler:
[codebox=c file=Unbenannt.c]#include <stdint.h>
#include <stdio.h>

int main(void)
{
register uint16_t a, b, c;

for (a = 1; a < (1000 - 2); ++a) {
for (b = a + 1; b < (1000 - 1) - a; ++b) {
c = 1000 - a - b;
if ((uint32_t) a * a + (uint32_t) b * b == (uint32_t) c * c) {
printf("%u, %u, %u\n", a, b, c);
return 0;
}
}
}
return 1;
}[/code]
Damit schafft es der C64 in etwas unter 18 Minuten.