C ++ bisschen Magie
0,84 ms mit einfachem RNG, 1,67 ms mit c ++ 11 std :: knuth
0,16 ms mit geringfügiger algorithmischer Änderung (siehe Bearbeitung unten)
Die Python-Implementierung läuft auf meinem Rig in 7,97 Sekunden. Das ist also 9488- bis 4772-mal schneller, je nachdem, welches RNG Sie auswählen.
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <tuple>
#if 0
// C++11 random
std::random_device rd;
std::knuth_b gen(rd());
uint32_t genRandom()
{
return gen();
}
#else
// bad, fast, random.
uint32_t genRandom()
{
static uint32_t seed = std::random_device()();
auto oldSeed = seed;
seed = seed*1664525UL + 1013904223UL; // numerical recipes, 32 bit
return oldSeed;
}
#endif
#ifdef _MSC_VER
uint32_t popcnt( uint32_t x ){ return _mm_popcnt_u32(x); }
#else
uint32_t popcnt( uint32_t x ){ return __builtin_popcount(x); }
#endif
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
uint32_t s1 = S % ( 1 << n );
uint32_t s2 = (S >> 1) % ( 1 << n );
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
// calculate which bits in the expression S * F evaluate to +1
unsigned firstPosBits = ((s1 & posBits) | (~s1 & negBits));
// idem for -1
unsigned firstNegBits = ((~s1 & posBits) | (s1 & negBits));
if ( popcnt( firstPosBits ) == popcnt( firstNegBits ) )
{
firstZero++;
unsigned secondPosBits = ((s2 & posBits) | (~s2 & negBits));
unsigned secondNegBits = ((~s2 & posBits) | (s2 & negBits));
if ( popcnt( secondPosBits ) == popcnt( secondNegBits ) )
{
bothZero++;
}
}
}
}
return std::make_pair(firstZero, bothZero);
}
int main()
{
typedef std::chrono::high_resolution_clock clock;
int rounds = 1000;
std::vector< std::pair<unsigned, unsigned> > out(rounds);
// do 100 rounds to get the cpu up to speed..
for( int i = 0; i < 10000; i++ )
{
convolve();
}
auto start = clock::now();
for( int i = 0; i < rounds; i++ )
{
out[i] = convolve();
}
auto end = clock::now();
double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;
#if 0
for( auto pair : out )
std::cout << pair.first << ", " << pair.second << std::endl;
#endif
std::cout << seconds/rounds*1000 << " msec/round" << std::endl;
return 0;
}
Kompilieren Sie in 64-Bit für zusätzliche Register. Bei Verwendung des einfachen Zufallsgenerators laufen die Schleifen in convolve () ohne Speicherzugriff, alle Variablen werden in den Registern gespeichert.
Wie es funktioniert: anstatt zu speichern S
und F
als in-Speicherarrays, als Bits in einem uint32_t gespeichert ist.
Für S
werden die n
niedrigstwertigen Bits verwendet, wobei ein gesetztes Bit +1 und ein nicht gesetztes Bit -1 bezeichnet.
F
Benötigt mindestens 2 Bits, um eine Verteilung von [-1, 0, 0, 1] zu erstellen. Dies erfolgt durch Erzeugen von Zufallsbits und Untersuchen der 16 niedrigstwertigen (aufgerufen r
) und 16 höchstwertigen (aufgerufen l
) Bits . Wenn l & ~r
wir annehmen, dass F +1 ist, ~l & r
nehmen wir an, dass dies F
-1 ist. Ansonsten F
ist es 0. Dies erzeugt die gesuchte Distribution.
Jetzt haben wir S
, posBits
mit einem gesetzten Bit an jedem Ort , an dem F == 1 und negBits
mit einem gesetzten Bit an jedem Ort , an dem F == -1.
Wir können beweisen, dass F * S
(wobei * für Multiplikation steht) unter der Bedingung +1 ergibt (S & posBits) | (~S & negBits)
. Wir können auch eine ähnliche Logik für alle Fälle generieren, in denen F * S
-1 ausgewertet wird. Und schließlich wissen wir, dass sum(F * S)
genau dann 0 ergibt, wenn das Ergebnis die gleiche Anzahl von -1 und +1 enthält. Dies ist sehr einfach zu berechnen, indem einfach die Anzahl von +1 Bits und -1 Bits verglichen werden.
Diese Implementierung verwendet 32-Bit-Ints, und das n
akzeptierte Maximum ist 16. Es ist möglich, die Implementierung durch Ändern des Zufallsgenerierungscodes auf 31 Bit und durch Verwenden von uint64_t anstelle von uint32_t auf 63 Bit zu skalieren.
bearbeiten
Die folgende Faltungsfunktion:
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
uint32_t mask = posBits | negBits;
uint32_t totalBits = popcnt( mask );
// if the amount of -1 and +1's is uneven, sum(S*F) cannot possibly evaluate to 0
if ( totalBits & 1 )
continue;
uint32_t adjF = posBits & ~negBits;
uint32_t desiredBits = totalBits / 2;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
// calculate which bits in the expression S * F evaluate to +1
auto firstBits = (S & mask) ^ adjF;
auto secondBits = (S & ( mask << 1 ) ) ^ ( adjF << 1 );
bool a = desiredBits == popcnt( firstBits );
bool b = desiredBits == popcnt( secondBits );
firstZero += a;
bothZero += a & b;
}
}
return std::make_pair(firstZero, bothZero);
}
verkürzt die Laufzeit auf 0.160-0.161ms. Durch manuelles Abrollen der Schlaufe (oben nicht abgebildet) ergibt sich ein Wert von 0,150. Der weniger triviale Fall n = 10, iter = 100000 läuft unter 250ms. Ich bin mir sicher, dass ich es unter 50 ms schaffen kann, wenn ich zusätzliche Kerne nutze, aber das ist zu einfach.
Dies geschieht, indem der innere Loop-Zweig frei gemacht und der F- und S-Loop vertauscht werden.
Wenn bothZero
es nicht erforderlich ist, kann ich die Laufzeit auf 0,02 ms reduzieren, indem ich alle möglichen S-Arrays sparsam durchschleife.
-std=c++0x -mpopcnt -O2
und benötigt 1,01 ms, um im 32-Bit-Modus ausgeführt zu werden (ich habe keine 64-Bit-GCC-Version zur Hand).Python2.7 + Numpy 1.8.1: 10.242 s
Fortran 90+:
0,029 s0,003 s0,022 s0,010 sVerdammt klar, du hast deine Wette verloren! Auch hier kein Tropfen Parallelisierung, nur gerade Fortran 90+.
BEARBEITEN Ich habe Guy Sirtons Algorithmus zum Permutieren des Arrays verwendet
S
(guter Fund: D). Ich hatte anscheinend auch die-g -traceback
Compiler-Flags aktiviert, die diesen Code auf ungefähr 0.017s verlangsamten. Derzeit kompiliere ich dies alsFür diejenigen, die nicht haben
ifort
, können Sie verwendenEDIT 2 : Die Laufzeitverringerung ist darauf zurückzuführen, dass ich zuvor etwas falsch gemacht habe und eine falsche Antwort erhalten habe. Es ist anscheinend langsamer, es richtig zu machen. Ich kann immer noch nicht glauben, dass C ++ schneller ist als meins, also werde ich wahrscheinlich einige Zeit in dieser Woche damit verbringen, den Mist herauszuarbeiten, um ihn zu beschleunigen.
EDIT 3 : Indem ich einfach die RNG-Sektion mit einer auf BSDs RNG basierenden Sektion ändere (wie von Sampo Smolander vorgeschlagen) und die konstante Teilung durch eliminiere
m1
, reduziere ich die Laufzeit auf dieselbe wie die C ++ - Antwort von Guy Sirton . Bei Verwendung von statischen Arrays (wie von Sharpie vorgeschlagen) wird die Laufzeit auf unter die C ++ - Laufzeit gesenkt! Yay Fortran! : DEDIT 4 Offensichtlich kompiliert dies nicht (mit gfortran) und wird nicht korrekt ausgeführt (falsche Werte), da die Ganzzahlen ihre Grenzen überschreiten. Ich habe Korrekturen vorgenommen, um sicherzustellen, dass es funktioniert, aber dazu muss entweder ifort 11+ oder gfortran 4.7+ (oder ein anderer Compiler, der dies zulässt,
iso_fortran_env
und der Typ F2008int64
) vorhanden sein.Hier ist der Code:
Ich nehme an, die Frage ist jetzt, ob Sie aufhören werden, langsam wie Melasse Python zu verwenden und schnell wie Elektronen Fortran bewegen können.
quelle
integer(int64) :: b = 3141592653_int64
für alle int64. Dies ist Teil des fortran-Standards und wird vom Programmierer in einer typdeklarierten Programmiersprache erwartet. (Beachten Sie, dass die Standardeinstellungen dies natürlich außer Kraft setzen können)Python 2.7 -
0.882s0.283s(OP Original: 6.404s)
Edit: Steven Rumbalskis Optimierung durch Vorberechnung von F-Werten. Mit dieser Optimierung schlägt Cpython Pypys 0.365s.
Der ursprüngliche Code von OP verwendet so winzige Arrays, dass die Verwendung von Numpy keinen Nutzen bringt, wie diese reine Python-Implementierung zeigt. Aber siehe auch diese blöde Implementierung, die dreimal schneller ist als mein Code.
Ich optimiere auch, indem ich den Rest der Faltung überspringe, wenn das erste Ergebnis nicht Null ist.
quelle
F
da es nur 4032 davon gibt. Definieren SiechoicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))
außerhalb der Schleifen. Dann in der inneren Schleife definierenF = random.choice(choicesF)
. Mit einem solchen Ansatz bekomme ich eine dreifache Beschleunigung.range(iters)
aus der Schleife. Insgesamt bekomme ich eine Beschleunigung von ca. 7% über Ihre sehr nette Antwort.Rost: 0,011 s
Ursprüngliches Python: 8.3
Eine gerade Übersetzung des ursprünglichen Python.
--opt-level=3
rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)
um genau zu sein)quelle
a
s undb
s in der Faltung verwechselt ; behoben (ändert die Laufzeit nicht merklich).C ++ (VS 2012) -
0,026s,0,015sPython 2.7.6 / Numpy 1.8.1 - 12s
Beschleunigung ~ x800.
Die Lücke wäre viel kleiner, wenn die gefalteten Arrays sehr groß wären ...
Ein paar Anmerkungen:
S[0]
die "niedrigstwertige" Ziffer.Fügen Sie diese Hauptfunktion für ein eigenständiges Beispiel hinzu:
quelle
advance
Funktion erhöht , daher ist mein Code jetzt schneller als Ihr: P (aber sehr gute Konkurrenz!)C
Nimmt 0.015s auf meiner Maschine, wobei der ursprüngliche OP-Code ~ 7.7s benötigt. Versucht zu optimieren, indem das zufällige Array generiert und in derselben Schleife gewickelt wird, aber es scheint keinen großen Unterschied zu machen.
Das erste Array wird erzeugt, indem eine ganze Zahl genommen, in Binärform ausgegeben und alle 1 in -1 und alle 0 in 1 geändert wird. Der Rest sollte sehr einfach sein.
Edit: anstelle von
n
alsint
, jetzt haben wirn
als ein Makro definierte Konstante, so können wir verwendenint arr[n];
stattmalloc
.Edit2: Anstelle der eingebauten
rand()
Funktion wird jetzt ein Xorshift-PRNG implementiert. Außerdem werden beim Generieren des Zufallsarrays viele bedingte Anweisungen entfernt.Kompilieranleitung:
Code:
quelle
do{}while(!flag)
oder etwas in diesem Sinne einschließen . Ich erwarte nicht, dass sich dadurch die Laufzeit stark ändert (möglicherweise schneller).continue;
Anweisung, die ich zugewiesen-1
habek
, wiederk
eine Schleife von 0 ausgeführt wird.-=
eher so aus als=-
:-) Eine while-Schleife wäre besser lesbar.J
Ich erwarte nicht, kompilierte Sprachen zu schlagen, und irgendetwas sagt mir, dass es eine wundersame Maschine braucht, um weniger als 0,09 Sekunden damit zu schaffen, aber ich möchte dieses J trotzdem einreichen, weil es ziemlich clever ist.
Dies dauert auf einem Laptop aus dem letzten Jahrzehnt etwa 0,5 s, nur etwa 20x so schnell wie der Python in der Antwort. Die meiste Zeit verbringen
conv
wir damit, weil wir es faul (wir berechnen die gesamte Faltung) und in voller Allgemeinheit schreiben.Da wir etwas über
S
und wissenF
, können wir die Dinge beschleunigen, indem wir spezifische Optimierungen für dieses Programm vornehmen. Das Beste, was mirconv =: ((num, num+1) { +//.)@:(*/)"1
eingefallen ist, ist: Wählen Sie genau die beiden Zahlen aus, die von den Diagonalsummen bis zu den längsten Elementen der Faltung reichen. Das halbiert ungefähr die Zeit.quelle
Perl - 9.3X schneller ... 830% Verbesserung
Bei meinem alten Netbook dauert die Ausführung des OP-Codes 53 Sekunden. Alistair Buxtons Version dauert ungefähr 6,5 Sekunden, und die folgende Perl-Version dauert ungefähr 5,7 Sekunden.
quelle
Python 2.7 - numpy 1.8.1 mit mkl-Bindungen - 0.086s
(OPs Original: 6.404s) (Buxtons reine Python: 0.270s)
Wie Buxton hervorhebt, verwendet der ursprüngliche OP-Code so winzige Arrays, dass die Verwendung von Numpy keinen Nutzen bringt. Diese Implementierung nutzt Numpy, indem alle F- und S-Fälle auf eine Array-orientierte Weise auf einmal ausgeführt werden. Dies zusammen mit mkl-Bindungen für Python führt zu einer sehr schnellen Implementierung.
Beachten Sie auch, dass das Laden der Bibliotheken und das Starten des Interpreters nur 0,076 Sekunden dauert, sodass die eigentliche Berechnung ~ 0,01 Sekunden dauert, ähnlich wie bei der C ++ - Lösung.
quelle
python -c "import numpy; numpy.show_config()"
zeigt Ihnen, ob Ihre Version von numpy mit blas / atlas / mkl usw. kompiliert ist. ATLAS ist ein kostenloses, beschleunigtes Mathematikpaket, mit dem numpy verknüpft werden kann. Intel MKL, für das Sie normalerweise zahlen müssen (es sei denn, Sie sind Akademiker). und kann mit numpy / scipy verknüpft werden .MATLAB 0.024s
Computer 1
Computer 2
Ich beschloss, das ach so langsame Matlab auszuprobieren. Wenn Sie wissen, wie, können Sie die meisten Schleifen (in Matlab) loswerden, was es ziemlich schnell macht. Die Speicheranforderungen sind jedoch höher als bei Lösungen mit Schleifen. Dies ist jedoch kein Problem, wenn Sie nicht über sehr große Arrays verfügen.
Folgendes mache ich:
Ich nehme an, Sie haben kein Matlab, was schade ist, da ich mir wirklich gewünscht hätte, zu sehen, wie es verglichen wird ...
(Die Funktion kann langsamer sein, wenn Sie sie zum ersten Mal ausführen.)
quelle
Julia: 0,30 s
Ops Python: 21,36 s (Core2-Duo)
71x beschleunigen
Ich habe einige Änderungen an Armans Julia-Antwort vorgenommen: Zunächst habe ich sie in eine Funktion eingeschlossen, da globale Variablen Julias Typinferenz und JIT erschweren: Eine globale Variable kann ihren Typ jederzeit ändern und muss bei jeder Operation überprüft werden . Dann habe ich die anonymen Funktionen und das Array-Verständnis beseitigt. Sie sind nicht wirklich notwendig und immer noch ziemlich langsam. Julia ist momentan schneller mit Abstraktionen auf niedrigerer Ebene.
Es gibt viel mehr Möglichkeiten, es schneller zu machen, aber das macht einen anständigen Job.
quelle
Ok, ich poste dies nur, weil ich der Meinung bin, dass Java hier vertreten sein muss. Ich kann andere Sprachen nicht leiden und muss gestehen, dass ich das Problem nicht genau verstehe. Daher benötige ich Hilfe, um diesen Code zu reparieren. Ich habe den größten Teil des C-Beispiels von Code Ace gestohlen und mir dann einige Ausschnitte von anderen ausgeliehen. Ich hoffe, das ist kein Fauxpas ...
Eine Sache, auf die ich hinweisen möchte, ist, dass Sprachen, die zur Laufzeit optimiert werden, mehrmals ausgeführt werden müssen, um die volle Geschwindigkeit zu erreichen. Ich denke, es ist gerechtfertigt, die voll optimierte Geschwindigkeit (oder zumindest die Durchschnittsgeschwindigkeit) zu wählen, da die meisten Dinge, die Sie mit schnellem Laufen zu tun haben, ein paar Mal ausgeführt werden.
Der Code muss noch repariert werden, aber ich habe ihn trotzdem ausgeführt, um zu sehen, wann ich ihn bekommen würde.
Hier sind die Ergebnisse auf einer Intel (R) Xeon (R) -CPU E3-1270 V2 mit 3,50 GHz unter Ubuntu, die 1000-mal ausgeführt wird:
server: / tmp # time java8 -cp. Prüfer
firstzero 40000
Bothzero 20000
erste Laufzeit: 41 ms letzte Laufzeit: 4 ms
echte 0m5.014s Benutzer 0m4.664s sys 0m0.268s
Hier ist mein beschissener Code:
Und ich habe versucht, den Python-Code nach dem Upgrade von Python und der Installation von Python-Numpy auszuführen, aber ich bekomme Folgendes:
quelle
currentTimeMillis
für das Benchmarking (die Nano - Version im System verwenden) und 1k läuft möglicherweise nicht ausreichen , um den JIT zu bekommen beteiligt (1,5k für Client und 10k für Server die Standardwerte wäre, obwohl Sie rufen Myrand oft genug , dass das wird JITed, was dazu führen sollte, dass einige Funktionen im Callstack kompiliert werden, was hier möglicherweise funktioniert.) Nicht zuletzt betrügt das schwache PNRG, aber auch die C ++ - Lösung und andere, also denke ich, ist das nicht zu unfair.gettimeofday(&time, NULL)
Entwicklungsbaum eingecheckt habe und Linux für Millisekunden verwendet, was nicht monoton ist und keine Genauigkeitsgarantien gibt (also auf einigen Plattformen / Kerneln genau das gleiche) Probleme wie die aktuelle Timemillis-Windows-Implementierung - also entweder dass man auch in Ordnung ist oder keines ist). nanoTime verwendet dagegen,clock_gettime(CLOCK_MONOTONIC, &tp)
was natürlich auch beim Benchmarking unter Linux das Richtige ist.Golang-Version 45X von Python auf meinem Computer unter Golang-Codes:
und die folgenden Python-Codes, die von oben kopiert wurden:
und die Zeit unten:
quelle
"github.com/yanatan16/itertools"
? Würden Sie auch sagen, dass dies in mehreren Goroutinen gut funktionieren würde?C # 0,135s
C # basierend auf Alistair Buxtons einfacher Python : 0.278s
Parallelisiert C #: 0.135s
Python aus der Frage: 5.907s
Alistairs einfacher Python: 0.853s
Ich bin mir nicht sicher, ob diese Implementierung korrekt ist - die Ausgabe ist anders, wenn man sich die Ergebnisse unten ansieht.
Es gibt sicherlich mehr optimale Algorithmen. Ich habe gerade beschlossen, einen sehr ähnlichen Algorithmus wie den von Python zu verwenden.
Single-Threaded C
Paralleles C #:
Testausgang:
Windows (.NET)
Das C # ist unter Windows viel schneller. Wahrscheinlich, weil .NET schneller als Mono ist.
Das Benutzer- und Sys-Timing scheint nicht zu funktionieren (wird
git bash
für das Timing verwendet).Linux (Mono)
quelle
Haskell: ~ 2000-fache Geschwindigkeit pro Kern
Kompilieren Sie mit 'ghc -O3 -funbox-strict-fields -threaded -fllvm' und führen Sie '+ RTS -Nk' aus, wobei k die Anzahl der Kerne auf Ihrem Computer ist.
quelle
Rubin
Rubin (2.1.0) 0.277s
Rubin (2.1.1) 0.281s
Python (Alistair Buxton) 0.330
Python (alemi) 0.097
quelle
Thread wäre nicht vollständig ohne PHP
6.6x schneller
PHP v5.5.9 -
1.2230.646 sec;vs
Python 2.7.6 - 8.072 Sek
convolve
Funktion etwas vereinfacht, um schneller zu sein$F
und$FS
Überprüfungen).Ausgänge:
Bearbeiten. Die zweite Version des Skripts funktioniert nur für
0.646 sec
:quelle
F # -Lösung
Die Laufzeit beträgt beim Kompilieren auf x86 auf dem CLR Core i7 4 (8) bei 3,4 GHz 0,030 Sekunden
Ich habe keine Ahnung, ob der Code korrekt ist.
quelle
Q, 0,296 seg
Q ist eine sammlungsorientierte Sprache (kx.com)
Code umgeschrieben, um das idiomatische Q zu untersuchen, aber keine anderen cleveren Optimierungen
Skriptsprachen optimieren die Programmierzeit und nicht die Ausführungszeit
Erster Codierungsversuch = kein Gewinner, aber angemessene Zeit (ca. 30-fache Geschwindigkeit)
ANMERKUNGEN.-
\S seed
\t sentence
misst die von diesem Satz verbrauchte Zeitquelle
Julia:
12,1496,929 sTrotz ihres Anspruchs auf Geschwindigkeit hält uns die anfängliche JIT-Kompilierungszeit zurück!
Beachten Sie, dass der folgende Julia-Code effektiv eine direkte Übersetzung des ursprünglichen Python-Codes ist (keine Optimierungen vorgenommen), um zu demonstrieren, dass Sie Ihre Programmiererfahrung einfach auf eine schnellere Sprache übertragen können;)
Bearbeiten
Laufen mit
n = 8
dauert 32.935 s. Bedenkt man, dass die Komplexität dieses Algorithmus istO(2^n)
, dann4 * (12.149 - C) = (32.935 - C)
, woC
ist eine Konstante , die JIT - Kompilierung Zeit darstellt. WennC
wir das lösen , finden wir, dassC = 5.2203
die tatsächliche Ausführungszeit fürn = 6
6.929 s beträgt.quelle
Rust, 6,6 ms, 1950x Beschleunigung
So ziemlich eine direkte Übersetzung von Alistair Buxtons Code nach Rust. Ich dachte darüber nach, mehrere Kerne mit Rayon zu verwenden (furchtlose Parallelität!), Aber dies verbesserte die Leistung nicht, wahrscheinlich, weil es bereits sehr schnell ist.
Und Cargo.toml, da ich externe Abhängigkeiten benutze:
Geschwindigkeitsvergleich:
6625608 ns beträgt ca. 6,6 ms. Das bedeutet 1950-fache Beschleunigung. Hier sind viele Optimierungen möglich, aber ich habe mich eher für die Lesbarkeit als für die Leistung entschieden. Eine mögliche Optimierung wäre die Verwendung von Arrays anstelle von Vektoren zum Speichern von Auswahlen, da diese immer
n
Elemente enthalten. Es ist auch möglich, RNG anders als XorShift zu verwenden, da Xorshift zwar schneller als der Standard-HC-128-CSPRNG ist, aber langsamer als der naivste PRNG-Algorithmus.quelle