Nun, ich habe diesen Code, der das Programm enorm verlangsamt, weil es eine lineare Komplexität ist, aber oft aufgerufen wird, was das Programm quadratisch kompliziert macht. Wenn es mir möglich ist, möchte ich seine Rechenkomplexität reduzieren, aber sonst werde ich sie nur optimieren, wo ich kann. Bisher habe ich reduziert auf:
%Vor%Wer sieht etwas, das ich vermisst habe? Danke!
EDIT: Ich habe vergessen zu erwähnen: n ist immer eine Primzahl.
EDIT 2: Hier ist mein neues verbessertes Programm (danke für alle Beiträge!):
%Vor%EDIT 3: Und testen Sie es in seinem realen Kontext ist es viel schneller! Nun, diese Frage scheint gelöst, aber es gibt viele nützliche Antworten. Ich sollte auch sagen, dass ich ebenso wie die obigen Optimierungen die Funktion mit Python-Dictionaries in Erinnerung habe ...
Wenn ich den Algorithmus für einen Moment ignoriere (ja, ich weiß, schlechte Idee), kann die Laufzeit von enorm verringert werden, indem man einfach von while auf for wechselt.
(Hoffe, das hat keinen Fehler, der um eins geht. Ich bin geneigt, diese zu machen.)
Eine andere Sache, die ich versuchen würde, ist zu schauen, ob die Schrittweite inkrementiert werden kann.
Schauen Sie sich Ссылка an. Die Funktion sqrtmod erledigt den Job, wenn Sie a = -1 und p = n setzen.
Ein kleiner Punkt, den Sie übersehen haben, ist, dass die Laufzeit Ihres verbesserten Algorithmus immer noch in der Reihenfolge der Quadratwurzel von n liegt. Solange Sie nur kleine Primzahlen n haben (sagen wir weniger als 2 ^ 64), ist das in Ordnung, und Sie sollten wahrscheinlich Ihre Implementierung zu einer komplexeren bevorzugen.
Wenn die Primzahl n größer wird, müssen Sie möglicherweise mit ein wenig Zahlentheorie zu einem Algorithmus wechseln. Nach meinem Wissen kann Ihr Problem nur mit einem probabilistischen Algorithmus in time log (n) ^ 3 gelöst werden. Wenn ich mich richtig erinnere, unter der Annahme, dass die Riemann-Hypothese gilt (was die meisten Leute tun), kann man zeigen, dass die Laufzeit des folgenden Algorithmus (in Ruby - sorry, ich kenne Python nicht) log (log (n)) ist. log (n) ^ 3:
%Vor%Der langsame Teil findet jetzt die Primzahl (was etwa eine logarithmische (logarithmische) Ganzzahloperation von log (n)) erfordert; Das Finden der Quadratwurzel von -1 dauert bei 512-Bit-Primzahlen noch weniger als eine Sekunde.
Erwägen Sie, die Ergebnisse vorzurechnen und sie in einer Datei zu speichern. Heutzutage haben viele Plattformen eine riesige Festplattenkapazität. Dann wird das Ergebnis eine O (1) -Operation sein.
Es sieht so aus, als ob Sie versuchen, die Quadratwurzel von -1 modulo n zu finden. Leider ist dies kein einfaches Problem, abhängig davon, welche Werte von n in Ihre Funktion eingegeben werden. Abhängig von n gibt es möglicherweise keine Lösung. Weitere Informationen zu diesem Problem finden Sie Wikipedia .
(Aufbauend auf Adams Antwort.) Sehen Sie sich die Wikipedia-Seite auf quadratische Reziprozität an:
x ^ 2 ≡ -1 (mod p) ist genau dann lösbar, wenn p ≡ 1 (mod 4).
Dann können Sie die Suche nach einer Wurzel genau für die ungeraden Primzahlen n vermeiden, die nicht mit 1 Modulo 4 übereinstimmen:
%Vor%Bearbeiten 2: Überraschenderweise reduziert die Reduzierung der Stärke der Quadrate die Zeit erheblich, zumindest bei meiner Python 2.5-Installation. (Ich bin überrascht, weil ich dachte, der Overhead des Interpreters würde die meiste Zeit dauern, und dies verringert nicht die Anzahl der Operationen in der inneren Schleife.) Reduziert die Zeit von 0.572s auf 0.146s für die Tabelle (1234577).
%Vor%strager posten die gleiche Idee , aber ich denke weniger eng codiert. Auch hier ist jug's answer am besten.
>Ursprüngliche Antwort: Eine weitere triviale Codierung, die über Konrad Rudolphs Tweak hinausgeht:
%Vor%Beschleunigt es messbar auf meinem Laptop. (Ungefähr 25% für Tabelle (1234577).)
Bearbeiten: Ich habe das python3.0-Tag nicht bemerkt; Die Hauptänderung bestand darin, einen Teil der Berechnung aus der Schleife zu entfernen, nicht die Verwendung von xrange . (Akademisch, da es einen besseren Algorithmus gibt.)
Können Sie die Ergebnisse zwischenspeichern?
Wenn Sie ein großes n berechnen, erhalten Sie die Ergebnisse für die unteren n fast kostenlos.
Eine Sache, die Sie tun, ist die Wiederholung der Berechnung -a * a immer und immer wieder.
Erstellen Sie einmal eine Tabelle mit den Werten und suchen Sie dann in der Hauptschleife nach.
Auch wenn dies wahrscheinlich nicht auf Sie zutrifft, weil Ihr Funktionsname eine Tabelle ist, aber wenn Sie eine Funktion aufrufen, die Zeit zum Berechnen benötigt, sollten Sie das Ergebnis in einer Tabelle zwischenspeichern und eine Tabelle nachschlagen, wenn Sie sie erneut aufrufen mit dem gleichen Wert. Dies spart Ihnen die Zeit für die Berechnung aller Werte bei der ersten Ausführung, aber Sie verschwenden keine Zeit, die Berechnung mehr als einmal zu wiederholen.
Ich ging durch und reparierte die Harvard-Version, damit es mit Python 3 funktioniert. Ссылка
Ich habe ein paar kleine Änderungen vorgenommen, damit die Ergebnisse genau der Funktion des OP entsprechen. Es gibt zwei mögliche Antworten und ich habe es gezwungen, die kleinere Antwort zurückzugeben.
%Vor%Diese Version benötigt ungefähr 3 ms, um die obigen Testfälle zu durchlaufen.
Zum Vergleich mit der Primzahl 1234577
OP Edit2 745ms
Die akzeptierte antwort 522ms
Die obige Funktion 0.2ms
Tags und Links algorithm python-3.x time-complexity complexity-theory