Jetzt, da jeder seine (oft erstaunliche) Programmierkenntnisse auf niedrigem Niveau für Wie langsam ist Python wirklich? (Oder wie schnell ist deine Sprache?) Und wie langsam ist Python wirklich (Teil II)? Es ist Zeit für eine Herausforderung, die auch Ihre Fähigkeit zur Verbesserung eines Algorithmus erweitert.
Der folgende Code berechnet eine Liste der Länge 9. Die Position i
in der Liste gibt an, wie oft mindestens i
aufeinanderfolgende Nullen gefunden wurden, wenn die inneren Produkte zwischen F
und berechnet wurden S
. Um dies genau zu tun, werden alle möglichen F
Längen- n
und Längenlisten S
durchlaufen n+m-1
.
#!/usr/bin/python
import itertools
import operator
n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
for F in itertools.product([-1,1], repeat = n):
i = 0
while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
leadingzerocounts[i] +=1
i+=1
print leadingzerocounts
Die Ausgabe ist
[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]
Wenn Sie mit diesem Code n auf 10,12,14,16,18,20 erhöhen, wird es sehr schnell viel zu langsam.
Regeln
- Die Herausforderung besteht darin, die richtige Ausgabe für ein möglichst großes n zu liefern. Nur gerade Werte von n sind relevant.
- Wenn es einen Gleichstand gibt, geht der Gewinn an den schnellsten Code auf meinem Computer für das größte n.
- Ich behalte mir das Recht vor, keinen Code zu testen, der länger als 10 Minuten dauert.
- Sie können den Algorithmus beliebig ändern, solange er die richtige Ausgabe liefert. Tatsächlich müssen Sie den Algorithmus ändern, um angemessene Fortschritte auf dem Weg zum Sieg zu erzielen.
- Der Gewinner erhält eine Woche ab dem Zeitpunkt, zu dem die Frage gestellt wurde.
- Das Kopfgeld wird bei Fälligkeit ausgezahlt, kurz danach wird der Gewinner ausgezahlt.
Mein Computer Die Timings werden auf meinem Computer ausgeführt. Dies ist eine Ubuntu-Standardinstallation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen. Verwenden Sie daher nur leicht verfügbare kostenlose Software und fügen Sie vollständige Anweisungen zum Kompilieren und Ausführen Ihres Codes bei.
Status .
- C . n = 12 in 49 Sekunden von @Fors
- Java . n = 16 in 3:07 von @PeterTaylor
- C ++ . n = 16 in 2:21 von @ilmale
- Rpython . n = 22 in 3:11 von @primo
- Java . n = 22 in 6:56 von @PeterTaylor
- Nimrod . n = 24 in 9:28 Sekunden von @ReimerBehrends
Der Gewinner war Reimer Behrends mit einem Eintrag in Nimrod!
Zur Kontrolle sollte der Ausgang für n = 22 sein [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
.
Der Wettbewerb ist jetzt vorbei, aber ... Ich werde 200 Punkte für jede Einsendung anbieten , die n um 2 erhöht (innerhalb von 10 Minuten auf meinem Computer), bis mir die Punkte ausgehen. Dieses Angebot ist für immer offen .
quelle
Antworten:
Nimrod (N = 22)
Kompilieren mit
(Nimrod kann hier heruntergeladen werden .)
Dies läuft in der zugewiesenen Zeit für n = 20 (und für n = 18, wenn nur ein einziger Thread verwendet wird, was im letzteren Fall ungefähr 2 Minuten dauert).
Der Algorithmus verwendet eine rekursive Suche, die den Suchbaum beschneidet, wenn ein inneres Produkt angetroffen wird, das nicht Null ist. Wir halbieren auch den Suchraum, indem
(F, -F)
wir beobachten, dass wir für jedes Paar von Vektoren nur einen berücksichtigen müssen, weil der andere genau die gleichen Mengen innerer Produkte erzeugt (indem wirS
auch negieren ).Die Implementierung verwendet die Metaprogrammierungsfunktionen von Nimrod, um die ersten Ebenen der rekursiven Suche zu entrollen / inline zu schalten. Dies spart ein wenig Zeit, wenn Sie gcc 4.8 und 4.9 als Backend von Nimrod verwenden, und eine angemessene Menge für das Klingen.
Der Suchraum könnte weiter eingeschränkt werden, indem beobachtet wird, dass wir nur Werte von S berücksichtigen müssen, die sich in einer geraden Anzahl der ersten N Positionen von unserer Wahl von F unterscheiden. Die Komplexität oder der Speicherbedarf davon skalieren jedoch nicht für große Werte von N, vorausgesetzt, der Schleifenkörper wird in diesen Fällen vollständig übersprungen.
Die Tabellierung, bei der das innere Produkt Null ist, scheint schneller zu sein, als die Verwendung einer Bitzählfunktion in der Schleife. Offensichtlich hat der Zugang zum Tisch eine ziemlich gute Lokalität.
Angesichts der Funktionsweise der rekursiven Suche scheint das Problem für die dynamische Programmierung zugänglich zu sein, aber es gibt keinen offensichtlichen Weg, dies mit einer angemessenen Speicherkapazität zu tun.
Beispielausgaben:
N = 16:
N = 18:
N = 20:
Um den Algorithmus mit anderen Implementierungen zu vergleichen, dauert N = 16 auf meinem Computer bei Verwendung eines einzelnen Threads etwa 7,9 Sekunden und bei Verwendung von vier Kernen 2,3 Sekunden.
N = 22 dauert ungefähr 15 Minuten auf einem 64-Core-Rechner mit gcc 4.4.6 als Nimrods Backend und überläuft 64-Bit-Ganzzahlen
leadingZeros[0]
(möglicherweise nicht vorzeichenlose, habe es nicht angeschaut).Update: Ich habe Raum für ein paar Verbesserungen gefunden. Erstens
F
können wir für einen gegebenen Wert von die ersten 16 Einträge der entsprechendenS
Vektoren genau aufzählen , da sie sich genau an denN/2
Stellen unterscheiden müssen . Wir berechnen also eine Liste von Bitvektoren der GrößeN
, für dieN/2
Bits gesetzt sind, und leiten daraus den Anfangsteil vonS
abF
.Zweitens können wir die rekursive Suche verbessern, indem wir beobachten, dass wir immer den Wert von kennen
F[N]
(da das MSB in der Bitdarstellung Null ist). Auf diese Weise können wir genau vorhersagen, in welchen Zweig wir vom inneren Produkt zurückkehren. Während dies uns tatsächlich erlauben würde, die gesamte Suche in eine rekursive Schleife umzuwandeln, führt dies tatsächlich dazu, dass die Verzweigungsvorhersage ziemlich durcheinander gerät, sodass wir die obersten Ebenen in ihrer ursprünglichen Form beibehalten. Wir sparen immer noch Zeit, vor allem durch die Reduzierung der Verzweigungen.Für einige Aufräumarbeiten verwendet der Code jetzt vorzeichenlose Ganzzahlen und korrigiert diese auf 64-Bit (nur für den Fall, dass jemand dies auf einer 32-Bit-Architektur ausführen möchte).
Die Gesamtbeschleunigung liegt zwischen einem Faktor von x3 und x4. N = 22 benötigt immer noch mehr als acht Kerne, um in weniger als 10 Minuten ausgeführt zu werden, aber auf einem 64-Kern-Computer sind es jetzt nur noch etwa vier Minuten (mit entsprechend
numThreads
erhöhten Werten). Ich glaube nicht, dass es ohne einen anderen Algorithmus viel mehr Raum für Verbesserungen gibt.N = 22:
Erneut aktualisiert, um weitere mögliche Reduzierungen des Suchraums zu nutzen. Läuft in ca. 9:49 Minuten für N = 22 auf meinem Quadcore-Rechner.
Endgültiges Update (glaube ich). Bessere Äquivalenzklassen für die Auswahl von F, Verkürzung der Laufzeit für N = 22 auf
3:19 Minuten57 Sekunden (Bearbeiten: Ich hatte das versehentlich mit nur einem Thread ausgeführt) auf meinem Computer.Diese Änderung nutzt die Tatsache, dass ein Vektorpaar die gleichen führenden Nullen erzeugt, wenn eine durch Drehen in die andere transformiert werden kann. Leider erfordert eine ziemlich kritische Low-Level-Optimierung, dass das oberste Bit von F in der Bitdarstellung immer das gleiche ist, und während diese Äquivalenz verwendet wird, wird der Suchraum ziemlich stark gekürzt und die Laufzeit um etwa ein Viertel gegenüber einem anderen Zustandsraum verringert Reduzierung von F, der Overhead durch das Eliminieren der Low-Level-Optimierung mehr als kompensiert. Es stellt sich jedoch heraus, dass dieses Problem behoben werden kann, indem auch die Tatsache berücksichtigt wird, dass F, die Inverse voneinander sind, ebenfalls äquivalent sind. Dies trug zwar etwas zur Komplexität der Berechnung der Äquivalenzklassen bei, erlaubte mir jedoch auch, die oben erwähnte Optimierung auf niedriger Ebene beizubehalten, was zu einer Beschleunigung von etwa x3 führte.
Ein weiteres Update zur Unterstützung von 128-Bit-Ganzzahlen für die akkumulierten Daten. Um mit 128-Bit-Ganzzahlen zu kompilieren, müssen Sie
longint.nim
von hier aus und mit kompilieren-d:use128bit
. N = 24 dauert immer noch mehr als 10 Minuten, aber ich habe das Ergebnis für die Interessenten unten angegeben.N = 24:
quelle
Java (
n=22
?)Ich denke, die meisten Antworten sind besser, als
n=16
einen ähnlichen Ansatz zu verwenden, obwohl sie sich in den Symmetrien, die sie ausnutzen, und in der Art und Weise, wie sie die Aufgabe zwischen den Threads aufteilen, unterscheiden.Die in der Frage definierten Vektoren können durch Bitfolgen ersetzt werden, und das innere Produkt kann durch XOR-Verknüpfung des überlappenden Fensters und durch Überprüfen, ob genau
n/2
Bits gesetzt (und dahern/2
Bits gelöscht) sind. Es gibtn! / ((n/2)!)
(zentraler Binomialkoeffizient) Folgen vonn
Bits mitn/2
gesetzten Bits (die ich ausgeglichene Folgen nenne ), alsoF
gibt es für jede gegebene Zahl so viele Fenster, vonS
denen ein Null-Innenprodukt erhalten wird. Darüber hinaus entspricht die Aktion des GleitensS
entlang eins und des Überprüfens, ob noch ein eingehendes Bit gefunden werden kann, das ein inneres Produkt von Null ergibt, der Suche nach einer Kante in einem Graphen, dessen Knoten die Fenster sind und dessen Kanten einen Knotenu
mit einem Knoten verknüpfen ,v
dessen ersten-1
Bits sind die letztenn-1
Bits vonu
.Zum Beispiel erhalten wir mit
n=6
undF=001001
diesen Graphen:und dafür
F=001011
bekommen wir diese Grafik:Dann müssen wir für jeden
i
von0
bis zu der Anzahl dern
Pfadei
zählen, die es gibt, und für jeden die Diagramme aufsummierenF
. Ich denke, die meisten von uns verwenden die Tiefensuche.Beachten Sie, dass die Grafiken spärlich sind: Es ist leicht zu beweisen, dass jeder Knoten einen In-Grad von höchstens 1 und einen Out-Grad von höchstens 1 aufweist. Das bedeutet auch, dass nur einfache Ketten und einfache Schleifen möglich sind. Dies vereinfacht die DFS ein wenig.
Ich nutze ein paar Symmetrien: Die ausgeglichenen Zeichenfolgen werden unter Bit-Inverse (die
~
Operation in vielen Sprachen aus der ALGOL-Familie) und unter Bit-Rotation geschlossen, sodass wir Werte zusammenfassen können,F
die durch diese Operationen zusammenhängen, und nur die DFS ausführen Einmal.Auf meinen 2.5GHz Core 2 bekomme ich
Da Lembiks Computer über 8 Kerne verfügt und mein früheres Single-Thread-Programm doppelt so schnell ausgeführt hat wie ich, bin ich optimistisch, dass es
n=22
in weniger als 8 Minuten ausgeführt wird.quelle
C
Es handelt sich im Grunde genommen nur um eine leicht optimierte Implementierung des in Frage kommenden Algorithmus. Es kann
n=12
innerhalb der Frist verwalten.Testlauf
n=12
inklusive Kompilierung für:Bemerkung: Ich habe gerade mein Gehirn angeschaltet und mit einfachen Kombinatoren berechnet, dass der erste Wert immer sein wird
n! / ((n / 2)!)^2 * 2^(n + m - 1)
. Es scheint mir, dass es eine völlig algebraische Lösung für dieses Problem geben muss.quelle
Java,
n=16
Für jeden gegebenen Wert von
F
gibt es\binom{n}{n/2}
Vektoren, die ein inneres Produkt von Null haben. So können wir ein Diagramm erstellen, dessen Eckpunkte die übereinstimmenden Vektoren sind und dessen Kanten der Verschiebung von entsprechenS
, und dann müssen wir nur die Längenpfade bis zumn
Diagramm zählen.Ich habe nicht versucht, dies durch Ersetzen von Bedingungen durch bitweise Operationen zu optimieren, aber jede doppelte Erhöhung der
n
Laufzeit um das 16-fache. Das wird also keinen ausreichenden Unterschied bewirken, es sei denn, ich bin ziemlich nahe an der Schwelle. Auf meiner Maschine bin ich nicht.Auf meinen 2.5GHz Core 2 bekomme ich
quelle
f
und Startknoten effizient zu durchlaufen , iterieren Sief_xor_g
mit genaun/2
gesetzten Bits über alle . Für jedes von diesen iteriere über allesf
und nimmg = f ^ f_xor_g
.RPython, N = 22 ~ 3: 23
Multithreaded mit einem stapellosen rekursiven Abstieg. Das Programm akzeptiert zwei Befehlszeilenargumente: N und die Anzahl der Arbeitsthreads.
Kompilieren
Erstellen Sie einen lokalen Klon des PyPy-Repositorys mit Quecksilber, Git oder was auch immer Sie bevorzugen. Geben Sie die folgende Beschwörung ein (unter der Annahme, dass das obige Skript benannt ist
convolution-high.py
):Hierbei handelt es sich
%PYPY_REPO%
um eine Umgebungsvariable, die auf das soeben geklonte Repository verweist. Die Kompilierung dauert ungefähr eine Minute.Beispiel-Timings
N = 16, 4 Fäden:
N = 18, 4 Fäden:
N = 20, 4 Fäden:
N = 22, 4 Fäden:
quelle
Python 3.3, N = 20, 3,5 min
Haftungsausschluss: Ich beabsichtige NICHT , dies als meine eigene Antwort zu veröffentlichen, da der von mir verwendete Algorithmus nur ein schamloser Port aus der RPython-Lösung von primo ist . Ich möchte hier nur zeigen, was Sie in Python tun können, wenn Sie die Magie der Numpy- und Numba- Module kombinieren .
Numba erklärte kurz:
Update 1 : Nachdem ich die Zahlen herumgeworfen habe, ist mir aufgefallen, dass wir einfach einige der Zahlen komplett überspringen können. So , jetzt maxf wird (1 << n) // 2 und maxs wird maxf 2 **. Dies beschleunigt den Prozess erheblich. n = 16 dauert jetzt nur noch ~ 48s (von 4,5min). Ich habe auch eine andere Idee, die ich versuchen werde, um zu sehen, ob ich es etwas schneller machen kann.
Update 2: Geänderter Algorithmus (primos Lösung). Mein Port unterstützt zwar noch kein Multithreading, das Hinzufügen ist jedoch ziemlich trivial. Es ist sogar möglich, CPython GIL mit Numba und ctypes freizugeben. Diese Lösung läuft aber auch auf Single Core sehr schnell!
Und schlussendlich:
Dies läuft auf meinem Rechner in 212688ms oder ~ 3.5min.
quelle
C ++ N = 16
Ich teste auf einem EEEPC mit einem Atom. Meine Zeit ergibt keinen Sinn. : D
Das Atom löst n = 14 in 34 Sekunden. Und n = 16 in 20 Minuten. Ich möchte n = 16 am OP-PC testen. Ich bin optimistisch.
Die Idee ist, dass wir jedes Mal, wenn wir eine Lösung für ein gegebenes F finden, eine 2 ^ i-Lösung gefunden haben, weil wir den unteren Teil von S ändern können, was zum gleichen Ergebnis führt.
kompilieren:
gcc 26459.cpp -std = c ++ 11 -O3 -march = native -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459
quelle
JAVASCRIPT n: 12
In meinem Computer dauerte es 231.242 Sekunden. In der Demo verwende ich Webworker, um das Einfrieren des Browsers zu verhindern. Dies kann mit Parallelarbeitern sicher noch weiter verbessert werden. Ich weiß, dass JS bei dieser Herausforderung keine Chance hat, aber ich habe es aus Spaß gemacht!
Klicken Sie hier, um die Online-Demo auszuführen
quelle
n=22
[235388928,86292480,19031048,5020640,1657928,783920,545408,481256,463832,460256,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744]
i.imgur.com/FIJa2Ch.pngFortran: n = 12
Ich habe gerade in Fortran eine 30-minütige Version erstellt, keine Optimierungen außer OpenMP. Es sollte bei n = 12 auf der OPs-Maschine knapp unter 10 Minuten einrasten, es dauert 10:39 auf meiner Maschine, die etwas langsamer ist.
64-Bit-Ganzzahlen wirken sich in der Tat negativ auf die Leistung aus. Ich denke, ich müsste den gesamten Algorithmus überdenken, damit dies viel schneller geht. Ich weiß nicht, ob ich mich darum kümmern werde, ich denke, ich werde lieber etwas Zeit damit verbringen, mir eine gute Herausforderung auszudenken, die eher meinem Geschmack entspricht. Wenn jemand anderes das nehmen und damit rennen will, mach weiter :)
quelle
Lua: n = 16
Haftungsausschluss: Ich beabsichtige NICHT, dies als meine eigene Antwort zu veröffentlichen, da der Algorithmus, den ich verwende, schamlos aus Anna Jokelas cleverer Antwort gestohlen wurde . Das wurde schamlos aus Ilmeas kluger Antwort gestohlen .
Außerdem ist es nicht einmal gültig - es weist Ungenauigkeiten auf, die durch Gleitkommazahlen verursacht werden (es wäre besser, wenn Lua 64-Bit-Ganzzahlen unterstützen würde). Ich lade es jedoch immer noch hoch, um zu zeigen, wie schnell diese Lösung ist. Es ist eine dynamische Programmiersprache und dennoch kann ich n = 16 in angemessener Zeit berechnen (1 Minute bei 800 MHz CPU).
Mit LuaJIT ausführen, Standardinterpreter ist zu langsam.
quelle
long long
anstelledouble
einer Kompilierungseinstellung bereits unterstützt wird ), nicht um LuaJIT.