Ich versuche ein Python-Skript zu schreiben, das alle Ganzzahlen (N) findet, bei denen eine bestimmte Potenz der Summe der Ziffern von N gleich N ist. Zum Beispiel ist N = 81 qualifiziert, weil 8 + 1 = 9 und eine bestimmte Potenz von 9 (nämlich 2) = 81.
Die von mir gewählten Bereiche sind beliebig. Mein Skript funktioniert, aber es ist sehr, sehr langsam. Im Idealfall möchte ich die ersten 30 solcher Ganzzahlen in etwa 6000ms finden.
Meine erste Lösung:
%Vor%In meiner zweiten Lösung habe ich versucht, alle Kräfte für jedes sumOfDigits zu speichern, aber das hat die Leistung nicht sehr verbessert.
%Vor%Ich habe noch keine Datenstrukturen und Algorithmen untersucht, daher würde ich mich über Hinweise freuen, die dieses Skript effizienter machen.
Update : Ich habe festgestellt, dass dies ein Project Euler Problem ist (# 119) und ich habe im Grunde die gleiche Lösung gefunden, die bereits dokumentiert ist: Ссылка
Ich bin mir nicht sicher, ob ich zu viel vereinfache, aber es ist ziemlich schnell, nur über die Kräfte für eine Reihe von Zahlen zu iterieren. Du kannst die Bestellung nicht garantieren, also berechne mehr als du brauchst und sortiere dann und nimm die Top 30. Ich kann nicht beweisen, dass ich sie alle habe, aber ich habe base bis zu 500 und exp bis zu getestet 50 und es gibt die gleichen Top 30 zurück. Es sollte beachtet werden, dass das OP nur Exponenten bis 5 getestet, was die Anzahl der Ergebnisse signifikant begrenzt:
Ausgabe
%Vor% Running timeit (einschließlich der Sortierung) Ich bekomme:
Dies ist eine großartige Zeit, um einen Profiler zu öffnen und zu sehen, wo Ihr Code seine ganze Zeit verbringt. Um das zu tun, habe ich einen kleinen cProfiler -Wrapper um deinen Code gelegt:
Hier läuft's, hier ist was ich habe:
%Vor% Wenn du schaust, scheint es so, als ob die meiste Zeit für diesen map -Aufruf ausgegeben wird, wo du num in eine Zeichenkette umwandelst, dann stellst du jede Zahl zu int, die dann summiert wird.
Es ist sehr sinnvoll, dass dies der langsame Teil des Programms ist. Sie tun das nicht nur viel, sondern es ist eine langsame Operation: In dieser einen Zeile führen Sie einen String-Parsing-Vorgang durch und bilden dann eine Int-Konvertierungsfunktion für jedes Zeichen in der Zeichenfolge ab, und dann summieren Sie sie.
Ich wette, dass, wenn Sie die Summe der Ziffern berechnen können, ohne zuerst die Umwandlung der Zeichenkette zu machen, es viel schneller ist.
Lass es uns versuchen. Ich habe einige andere Änderungen vorgenommen, wie zum Beispiel das Entfernen der redundanten Listen-Comprehensions zu Beginn. Folgendes habe ich bekommen:
%Vor% Was sagt cProfile ?
4 Sekunden bis 0,9 Sekunden? Viel besser.
Wenn Sie den Effekt wirklich sehen wollen, fügen Sie der oberen Grenze von arange eine zusätzliche Null hinzu. Auf meiner Box dauert der Originalcode ~ 47 Sekunden. Der modifizierte Code benötigt ~ 10.
Der Profiler ist dein Freund, und String-Konvertierung ist nicht kostenlos, wenn du es hunderttausende Male machst:)
Ihre Lösung untersucht jede mögliche ganze Zahl, um zu sehen, dass sie eine Lösung sein könnte. Es ist effizienter, nur die ganzen Zahlen zu untersuchen, die tatsächlich Befugnisse sind, um zu sehen, ob sie gültige Antworten sind - weil es weniger davon gibt. Hier ist etwas, das dies tut. Aber es wird wahrscheinlich länger als 6s dauern, um 30 zu finden - sie werden schnell knapp.
BEARBEITEN - aktualisiert, um die in den Kommentaren von Padraic Cunningham und fjarri vorgeschlagene schnellere Ziffernsummierung zu machen, und dann aktualisiert, um ein paar weitere Optimierungen hinzuzufügen, macht es zu einem Generator und macht es Python-3 freundlich.
Es wird immer noch schnell langsam, aber der Algorithmus kann parallelisierbar sein - vielleicht könnten Sie die Ziffern-Summierung in einen separaten Prozess einfügen.
BEARBEITEN 2 - Rasiere dich etwas ab, indem du schnell kontrollierst, ob die Basis und der Ergebniswert gleich modulo 9 sind. Es könnte weitere Zahlen-Theorie-Tricks geben ...
%Vor%[edit: Aufgrund eines Fehlers im angegebenen Algorithmus, den ich transkribiert habe, ist diese Methode ziemlich langsam (ungefähr so schnell wie die anderen Methoden). Ich behalte das hier für die Code-Referenz. Dies scheint jedoch das Beste zu sein, was man tun kann, ohne auf Zahlentricks zurückgreifen zu müssen.]
Wenn Sie Integer-Sequenzen berechnen, sollten Sie zuerst zu Sloane gehen und die Sequenz eingeben. Dies ist die Folge A023106 "a (n) ist eine Potenz der Summe ihrer Ziffern." . Die ersten 32 solcher Nummern bis zu 68719476736 können durch Klicken auf den Link "Liste" gefunden werden. Oft kann man Algorithmen (die auch effizient sein können) sowie Referenzen finden. Es gibt auch die ersten 1137 Nummern bis zu [eine Nummer, die groß genug ist, um ein paar Absätze zu füllen]
>Nun zu einem effizienten Algorithmus: Wenn Sie keine Möglichkeit haben, Bereiche von Zahlen zu überspringen, ohne sie zu betrachten, oder wenn wir eine mathematische Eigenschaft der Zahlen ausnutzen können, stecken Sie fest mit einem O (N) Algorithmus. Eine andere Möglichkeit, wie du es angehen kannst, ist, alle Kräfte zu berechnen (wodurch du alle Zahlen überspringen kannst) und dann jede Potenz P = n ^ m zu testen. "Gibt es eine Zahl, deren Ziffern sich zu einer Potenz von P addieren? ".
Dieser Algorithmus wird uns in der obigen Verknüpfung bereits zur Verfügung gestellt. Der im obigen Link angegebene Algorithmus ist (in Mathematica):
%Vor%Die lose Übersetzung ist:
%Vor%Eine vollständige Implementierung wäre:
%Vor%Ausgabe:
%Vor%Das kostet leider viel Zeit. Zum Beispiel müssen wir 53.863.062 Kandidaten prüfen, was Minuten dauern könnte.
Tags und Links python algorithm performance sum-of-digits