Ich versuche dieses Programmierrätsel zu lösen und obwohl die Lösung (siehe Code unten) funktioniert richtig, es ist zu langsam für die erfolgreiche Einreichung.
Grundsätzlich ist die Aufgabe:
%Vor%Mein Originalcode (er berechnete die 3000 ersten Glückszahlen in etwa einer Sekunde auf meinem Rechner - leider zu langsam):
%Vor%EDIT: Dank der tollen Beiträge von Mark Dickinson, Steve Jessop und gnibbler, kam ich zu folgendem, das ziemlich viel schneller ist als mein ursprünglicher Code (und erfolgreich bei < a href="http://www.spoj.pl"> Ссылка mit 0,58 Sekunden!) ...
%Vor%Diese Serie wird spielerische Zahlen
genannt __delslice__ sollte schneller sein als __setslice__ + filter
So wird die Schleife.
%Vor%Was in weniger als 0,1 Sekunden läuft
Versuchen Sie, diese beiden Zeilen zum Löschen und Filtern zu verwenden, anstatt, was Sie haben; filter(None, ...) läuft erheblich schneller als filter(lambda ...) .
Bearbeiten: viel besser, einfach del sieve[::item] ; Siehe gnibbler's Lösung.
Sie können möglicherweise auch eine bessere Abbruchbedingung für die while-Schleife finden: Wenn beispielsweise das erste verbleibende Element im Sieb i ist, werden die ersten i -Elemente des Siebs zum nächsten i Glückszahlen; also wenn len(luckynumbers) + sieve[0] >= wanted_n , du hättest die Zahl, die du brauchst, schon berechnet --- du musst nur herausfinden wo in sieve ist, damit du es extrahieren kannst.
Auf meinem Computer läuft die folgende Version Ihrer inneren Schleife um das 15-fache schneller als Ihr Original, um die 3000. Glückszahl zu finden:
%Vor%Eine Erklärung, wie Sie dieses Problem lösen können, finden Sie hier . (Das Problem, zu dem ich verlinkt habe, verlangt nach mehr, aber der Hauptschritt in diesem Problem ist der gleiche wie der, den du lösen willst.) Die Site, mit der ich verlinkt habe, enthält auch eine Beispiellösung in C ++.
Die Menge der Zahlen kann in einem Binärbaum dargestellt werden, der die folgenden Operationen unterstützt:
n th Element n th Diese Operationen können so implementiert werden, dass sie in O(log n) time ausgeführt werden, wobei n die Anzahl der Knoten in der Struktur ist.
Um die Struktur zu erstellen, können Sie entweder eine benutzerdefinierte Routine erstellen, die die Struktur aus einem gegebenen Array von Elementen erstellt, oder eine Einfügeoperation implementieren (stellen Sie sicher, dass die Struktur ausgeglichen bleibt).
Jeder Knoten in der Struktur benötigt folgende Informationen:
Wenn eine solche Struktur vorhanden ist, sollte die Lösung des restlichen Problems ziemlich einfach sein.
Ich empfehle auch, die Antworten für alle möglichen Eingabewerte zu berechnen, bevor eine Eingabe gelesen wird, anstatt die Antwort für jede Eingabezeile zu berechnen.
Eine Java-Implementierung des obigen Algorithmus wird in 0,68 Sekunden auf der von Ihnen verlinkten Website akzeptiert.
(Entschuldigung, dass Sie keine Python-spezifische Hilfe bereitstellen, aber hoffentlich wird der oben beschriebene Algorithmus schnell genug sein.)
Es ist besser, ein Array zu verwenden und jedes Nth Item mit dieser Strategie auf Null zu setzen; Nachdem Sie dies einige Male hintereinander getan haben, werden die Aktualisierungen immer schwieriger, sodass Sie das Array neu formatieren müssen. Dies sollte die Geschwindigkeit um mindestens einen Faktor 10 verbessern. Brauchen Sie viel besser als das?
Tags und Links python algorithm performance