Ich versuche eine Funktion zu schreiben, die bei gegebenem (x, y) -Koordinatenpaar und zufälligem Startwert des Programms pseudozufällig für einen voreingestellten Prozentsatz aller solcher Paare als wahr zurückgeliefert wird. Es gibt keine Beschränkungen für x oder y über die Einschränkungen des Datentyps hinaus, der ein 32-Bit-Zeichen mit int. Ist.
Mein derzeitiger Ansatz besteht darin, die Bits von x, y und der Saat zusammen zu verwürfeln und dann die resultierende Zahl mit dem Prozentsatz zu vergleichen:
%Vor%Es scheint jedoch, dass dieser Ansatz für bestimmte Werte von x und y voreingenommen wäre. Wenn beispielsweise für (0, a) der Wert true zurückgegeben wird, wird auch true für (a, 0) zurückgegeben.
Ich weiß, dass diese Implementierung, die sie einfach zu XOR zusammenführt, naiv ist. Gibt es hier einen besseren Bit-Scrambling-Algorithmus, der nicht voreingenommen ist?
Bearbeiten: Um zu verdeutlichen, fange ich nicht mit einer Menge von (x, y) -Koordinaten an, noch versuche ich, eine feste Größe von Koordinaten zu erhalten, die als wahr ausgewertet werden. Die Funktion sollte in der Lage sein, einen Wahrheitswert für beliebige x-, y- und Seedwerte auszuwerten, wobei der Prozentsatz die durchschnittliche Häufigkeit der "wahren" Koordinaten steuert.
Die einfache Lösung besteht darin, einen guten Hash-Algorithmus zu verwenden. Sie können die Bereichsüberprüfung für den Wert von hash(seed || x || y) durchführen.
Natürlich kann die Auswahl von Punkten mit Prozent p nicht garantieren, dass Sie ein Sample erhalten, dessen Größe genau p * N ist. (Das ist die erwartete Größe des Samples, aber jedes Sample wird ein wenig abweichen.) Wenn Sie ein Sample der Größe k aus einem Universum von N -Objekten erhalten möchten, können Sie den folgenden einfachen Algorithmus verwenden:
Untersuchen Sie die Elemente in der Probe nacheinander, bis k 0 erreicht.
Wenn Sie das Element i untersuchen, fügen Sie es zum Beispiel hinzu, wenn sein Hashwert, der auf den Bereich [0, N-i) abgebildet ist, kleiner ist als k . Wenn Sie das Element zum Beispiel hinzufügen, dekrementieren Sie k .
Es gibt keine Möglichkeit, die Arithmetik absolut perfekt zu machen (da es keine Möglichkeit gibt, 2i verschiedene Hashwerte in n Buckets zu partitionieren, wenn n eine Potenz von 2 ist), so wird es immer ein kleines geben vorspannen. (Fließkomma-Arithmetik hilft nicht; die Anzahl der möglichen Fließkommawerte ist ebenfalls festgelegt und leidet unter derselben Verzerrung.)
Wenn Sie eine 64-Bit-Arithmetik ausführen, ist die Verzerrung wirklich winzig, aber die Arithmetik ist komplizierter, wenn Ihre Umgebung keine 128-Bit-Multiplikation liefert. Sie könnten also mit 32-Bit-Berechnungen zufrieden sein, bei denen die Verzerrung von eins in ein paar tausend Millionen [Anmerkung 1] keine Rolle spielt. Hier können Sie die Tatsache verwenden, dass alle 32 Bits in Ihrem Hash so unvoreingenommen wie alle anderen 32 Bits sein sollten, vorausgesetzt, Ihr Hash-Algorithmus ist gut (siehe unten). Daher sollte die folgende Überprüfung funktionieren:
%Vor%Wenn Sie davon ausgehen, dass Sie viel tun müssen, sollten Sie einen schnellen Hash-Algorithmus verwenden. Da Sie nicht in einer sicheren Umgebung arbeiten, müssen Sie sich keine Gedanken darüber machen, ob der Algorithmus kryptografisch sicher ist.
Viele Hochgeschwindigkeits-Hashing-Algorithmen arbeiten mit 64-Bit-Einheiten, sodass Sie die Geschwindigkeit maximieren können, indem Sie eine 128-Bit-Eingabe erstellen, die aus einem 64-Bit-Seed und den zwei 32-Bit-Koordinaten besteht. Sie können die Hash-Schleife dann abwickeln, um genau zwei Blöcke zu machen.
Ich wage keine Vermutung über die beste Hash-Funktion für Ihren Zweck. Vielleicht möchten Sie eine oder mehrere dieser Open-Source-Hashfunktionen auschecken:
... und viele mehr.
Ich würde es vorziehen, seed, x und y durch einen kombinierten linearen kongruenten Generator zu füttern.
Dies ist im Allgemeinen viel schneller als Hashing und es wurde speziell für den Zweck entwickelt: Um eine Pseudozufallszahl gleichmäßig in einem bestimmten Bereich auszugeben.
Unter Verwendung der von Wichmann-Hill empfohlenen Koeffizienten (die auch in einigen Versionen von Microsoft Excel verwendet werden) können wir Folgendes tun:
%Vor% Dabei steht s für den ersten Aufruf und der vorherige si für jeden nachfolgenden Aufruf. (Danke an Ricis Kommentar für diesen Punkt.)