Ich habe eine Hashmap in C als Teil eines Projekts implementiert, an dem ich arbeite, und zufällige Einfügungen verwendet, um sie zu testen, als ich bemerkte, dass rand()
unter Linux Zahlen weitaus häufiger wiederholt werden als auf Mac. RAND_MAX
ist 2147483647 / 0x7FFFFFFF auf beiden Plattformen. Ich habe es auf dieses Testprogramm reduziert, das ein Byte-Array RAND_MAX+1
-lang macht, RAND_MAX
Zufallszahlen generiert , notiert, ob jedes ein Duplikat ist, und es wie gesehen von der Liste abhakt.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int main() {
size_t size = ((size_t)RAND_MAX) + 1;
char *randoms = calloc(size, sizeof(char));
int dups = 0;
srand(time(0));
for (int i = 0; i < RAND_MAX; i++) {
int r = rand();
if (randoms[r]) {
// printf("duplicate at %d\n", r);
dups++;
}
randoms[r] = 1;
}
printf("duplicates: %d\n", dups);
}
Linux generiert konsistent rund 790 Millionen Duplikate. Der Mac generiert konsistent nur eine, sodass er jede Zufallszahl durchläuft, die er fast ohne Wiederholung generieren kann . Kann mir bitte jemand erklären, wie das funktioniert? Ich kann nichts anderes als die Manpages sagen, kann nicht sagen, welches RNG jeder verwendet, und kann online nichts finden. Vielen Dank!
Antworten:
Während es zunächst so klingt, als ob das macOS
rand()
irgendwie besser ist, um keine Zahlen zu wiederholen, sollte man beachten, dass bei dieser Anzahl generierter Zahlen viele Duplikate zu erwarten sind (tatsächlich etwa 790 Millionen oder (2 31 -1) ) / e ). Ebenso würde das Durchlaufen der Zahlen nacheinander keine Duplikate ergeben, würde aber nicht als sehr zufällig angesehen. Die Linux-rand()
Implementierung ist in diesem Test also nicht von einer echten Zufallsquelle zu unterscheiden, während dies bei macOSrand()
nicht der Fall ist.Eine andere Sache, die auf den ersten Blick überraschend erscheint, ist, wie das MacOS
rand()
es schaffen kann, Duplikate so gut zu vermeiden. Wenn wir uns den Quellcode ansehen , stellen wir fest, dass die Implementierung wie folgt lautet:Dies führt tatsächlich zu allen Zahlen zwischen 1 und
RAND_MAX
einschließlich genau einmal, bevor sich die Sequenz erneut wiederholt. Da der nächste Zustand auf Multiplikation basiert, kann der Zustand niemals Null sein (oder alle zukünftigen Zustände wären auch Null). Somit ist die wiederholte Zahl, die Sie sehen, die erste, und Null ist diejenige, die niemals zurückgegeben wird.Apple hat die Verwendung besserer Zufallszahlengeneratoren in seiner Dokumentation und seinen Beispielen mindestens so lange gefördert, wie es macOS (oder OS X) gibt, sodass die Qualität von
rand()
wahrscheinlich nicht als wichtig erachtet wird und sie sich nur an einen von ihnen gehalten haben die einfachsten verfügbaren Pseudozufallsgeneratoren. (Wie Sie bemerkt haben, wird ihrrand()
sogar mit einer Empfehlung kommentiert,arc4random()
stattdessen zu verwenden .)Über einen entsprechenden Hinweis, ich die einfachste Pseudo - Zufallszahlengenerator erzeugt , dass anständige Ergebnisse in dieser finden konnten (und viele andere) Tests auf Zufälligkeit ist Xorshift * :
Diese Implementierung führt zu fast genau 790 Millionen Duplikaten in Ihrem Test.
quelle
arc4random()
gleichen Code verwendenrand()
und ein gutesrand()
Ergebnis erzielen. Anstatt zu versuchen, Programmierer dazu zu bringen, anders zu codieren, erstellen Sie einfach bessere Bibliotheksfunktionen. "Sie sind einfach festgefahren" ist ihre Wahl.rand()
macht es so schlimm, dass es für den praktischen Gebrauch nicht nützlich ist: Warum gibt rand ()% 7 immer 0 zurück? , Rand ()% 14 generiert nur die Werte 6 oder 13rand
, dass ein erneutes Ausführen mit demselben Startwert dieselbe Sequenz erzeugt. OpenBSDsrand
sind kaputt und halten sich nicht an diesen Vertrag.rand()
mit demselben Startwert dieselbe Sequenz zwischen verschiedenen Versionen der Bibliothek erzeugt? Eine solche Garantie könnte für Regressionstests zwischen Bibliotheksversionen nützlich sein, ich finde jedoch keine C-Anforderung dafür.MacOS bietet eine undokumentierte rand () - Funktion in stdlib. Wenn Sie es nicht ausgesät lassen, werden als erste Werte 16807, 282475249, 1622650073, 984943658 und 1144108930 ausgegeben. Eine schnelle Suche zeigt, dass diese Sequenz einem sehr einfachen LCG-Zufallszahlengenerator entspricht, der die folgende Formel wiederholt:
Da der Zustand dieses RNG vollständig durch den Wert einer einzelnen 32-Bit-Ganzzahl beschrieben wird, ist seine Periode nicht sehr lang. Um genau zu sein, wiederholt es sich alle 2 31 - 2 Iterationen und gibt jeden Wert von 1 bis 2 31 - 2 aus.
Ich glaube nicht, dass es eine Standardimplementierung von rand () für alle Linux-Versionen gibt, aber es gibt eine glibc rand () -Funktion , die häufig verwendet wird. Anstelle einer einzelnen 32-Bit-Statusvariablen wird ein Pool von über 1000 Bit verwendet, der in jeder Hinsicht niemals eine sich vollständig wiederholende Sequenz erzeugt. Auch hier können Sie wahrscheinlich herausfinden, welche Version Sie haben, indem Sie die ersten Ausgaben dieses RNG drucken, ohne es zuerst zu setzen. (Die Funktion glibc rand () erzeugt die Nummern 1804289383, 846930886, 1681692777, 1714636915 und 1957747793.)
Der Grund, warum Sie unter Linux (und unter MacOS kaum) Kollisionen bekommen, ist, dass die Linux-Version von rand () grundsätzlich zufälliger ist.
quelle
rand()
muss sich wie einer mitsrand(1);
rand()
in macOS ist verfügbar: opensource.apple.com/source/Libc/Libc-1353.11.2/stdlib/FreeBSD/… FWIW, ich habe den gleichen Test gegen diesen aus der Quelle kompilierten ausgeführt und er führt tatsächlich dazu nur ein Duplikat. Apple hatarc4random()
in seinen Beispielen und in seiner Dokumentation die Verwendung anderer Zufallszahlengeneratoren (z. B. vor der Übernahme durch Swift) gefördert.rand()
Daher ist die Verwendung in nativen Apps auf ihren Plattformen wahrscheinlich nicht sehr verbreitet, was möglicherweise erklärt, warum dies nicht besser ist.rand()
sei nicht dokumentiert, aber @Arkku hat einen Link zur offensichtlichen Quelle bereitgestellt. Weiß einer von Ihnen, warum ich diese Datei auf meinem System nicht finden kann und warum ich sie nurint rand(void) __swift_unavailable("Use arc4random instead.");
auf Macs sehestdlib.h
? Ich nehme an, der Code, mit dem @Arkku verknüpft ist, wird nur in ... welche Bibliothek kompiliert?/usr/lib/libc.dylib
. =)rand()
einem Programm C gegeben Verwendungen nicht durch den „Compiler“ oder das „Betriebssystem“, sondern die Umsetzung der C - Standardbibliothek bestimmt ( zum Beispielglibc
,libc.dylib
,msvcrt*.dll
).rand()
wird durch den C-Standard definiert, und der C-Standard gibt nicht an, welcher Algorithmus verwendet werden soll. Offensichtlich verwendet Apple einen schlechteren Algorithmus als Ihre GNU / Linux-Implementierung: Der Linux-Algorithmus ist in Ihrem Test nicht von einer echten Zufallsquelle zu unterscheiden, während die Apple-Implementierung nur die Zahlen mischt.Wenn Sie Zufallszahlen beliebiger Qualität wünschen, verwenden Sie entweder ein besseres PRNG, das zumindest einige Garantien für die Qualität der zurückgegebenen Zahlen gibt, oder lesen Sie einfach aus
/dev/urandom
oder ähnlichem. Letzteres gibt Ihnen kryptografische Qualitätszahlen, ist aber langsam. Selbst wenn es an sich zu langsam ist,/dev/urandom
kann es einem anderen, schnelleren PRNG einige ausgezeichnete Samen liefern.quelle
Im Allgemeinen wurde das Rand / Rand-Paar lange Zeit als veraltet angesehen, da Bits niedriger Ordnung in den Ergebnissen weniger zufällig sind als Bits höherer Ordnung. Dies kann oder kann nicht mit Ihren Ergebnissen zu tun haben, aber ich denke, dies ist immer noch eine gute Gelegenheit, sich daran zu erinnern, dass ältere Implementierungen bestehen bleiben und es besser ist, zufällig zu verwenden, obwohl einige Rand / Rand-Implementierungen jetzt aktueller sind (3) ). Auf meiner Arch Linux-Box befindet sich der folgende Hinweis noch in der Manpage für rand (3):
Direkt darunter finden Sie auf der Manpage sehr kurze, sehr einfache Beispielimplementierungen von rand und srand, die sich mit den einfachsten LC-RNGs befassen, die Sie jemals gesehen haben, und die einen kleinen RAND_MAX haben. Ich glaube nicht, dass sie mit dem übereinstimmen, was in der C-Standardbibliothek enthalten ist, wenn sie es jemals getan haben. Zumindest hoffe ich nicht.
Wenn Sie etwas aus der Standardbibliothek verwenden möchten, verwenden Sie im Allgemeinen zufällig, wenn Sie können (auf der Manpage wird es als POSIX-Standard zurück zu POSIX.1-2001 aufgeführt, aber Rand ist Standard, bevor C überhaupt standardisiert wurde). . Oder noch besser, knacken Sie numerische Rezepte auf (oder suchen Sie online danach) oder Knuth und implementieren Sie eines. Sie sind wirklich einfach und Sie müssen es nur einmal tun, um ein Allzweck-RNG mit den Attributen zu haben, die Sie am häufigsten benötigen und die von bekannter Qualität sind.
quelle
rand()
'besser' bedeuten würde, es langsamer zu machen (was wahrscheinlich der Fall wäre - kryptografisch sichere Zufallszahlen erfordern viel Aufwand), ist es wahrscheinlich besser, es schnell zu halten, auch wenn es geringfügig vorhersehbarer ist. Ein typisches Beispiel: Wir hatten eine Produktionsanwendung, deren Start ewig gedauert hat. Wir haben sie auf ein RNG zurückgeführt, dessen Initialisierung auf die Erzeugung einer ausreichenden Entropie warten musste. Es stellte sich heraus, dass sie nicht so sicher sein musste, also ersetzte sie durch Ein "schlechteres" RNG war eine große Verbesserung.