171

と呼ばれるクラスを作成しましたQuickRandom。その仕事は、乱数をすばやく生成することです。それは本当に簡単です。古い値を取り、。を掛けてdouble、小数部分を取ります。

これが私のQuickRandomクラス全体です:

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

}

そして、これが私がそれをテストするために書いたコードです:

public static void main(String[] args) {
        QuickRandom qr = new QuickRandom();

        /*for (int i = 0; i < 20; i ++) {
            System.out.println(qr.random());
        }*/

        //Warm up
        for (int i = 0; i < 10000000; i ++) {
            Math.random();
            qr.random();
            System.nanoTime();
        }

        long oldTime;

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            Math.random();
        }
        System.out.println(System.nanoTime() - oldTime);

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            qr.random();
        }
        System.out.println(System.nanoTime() - oldTime);
}

これは、前のdoubleに「マジックナンバー」のdoubleを単純に乗算する非常に単純なアルゴリズムです。私はそれをかなり速く一緒に投げたので、おそらくそれをより良くすることができましたが、奇妙なことに、それはうまく機能しているようです。

mainこれは、メソッドのコメント化された行の出力例です。

0.612201846732229
0.5823974655091941
0.31062451498865684
0.8324473610354004
0.5907187526770246
0.38650264675748947
0.5243464344127049
0.7812828761272188
0.12417247811074805
0.1322738256858378
0.20614642573072284
0.8797579436677381
0.022122999476108518
0.2017298328387873
0.8394849894162446
0.6548917685640614
0.971667953190428
0.8602096647696964
0.8438709031160894
0.694884972852229

うーん。かなりランダム。実際、これはゲーム内の乱数ジェネレーターで機能します。

コメントアウトされていない部分の出力例は次のとおりです。

5456313909
1427223941

わお!の約4倍の速度で動作しMath.randomます。

クレイジーなモジュラスと除算のものをMath.random使ったものをどこかで読んだことを覚えています。System.nanoTime()それは本当に必要ですか?私のアルゴリズムははるかに高速に実行され、かなりランダムに見えます。

2つの質問があります:

  • 私のアルゴリズムは「十分に良い」ですか(たとえば、実際には乱数がそれほど重要ではないゲームの場合)?
  • Math.random単純な乗算と小数の切り取りで十分だと思われるのに、なぜそんなに多くのことをするのでしょうか。
4

14 に答える 14

351

あなたのQuickRandom実装は実際には一様分布ではありません。頻度は一般に低い値で高くなりますMath.random()が、より均一な分布になります。これがSSCCEであり、次のことを示しています。

package com.stackoverflow.q14491966;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        int[] frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (qr.random() * 10)]++;
        }
        printDistribution("QR", frequencies);

        frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (Math.random() * 10)]++;
        }
        printDistribution("MR", frequencies);
    }

    public static void printDistribution(String name, int[] frequencies) {
        System.out.printf("%n%s distribution |8000     |9000     |10000    |11000    |12000%n", name);
        for (int i = 0; i < 10; i++) {
            char[] bar = "                                                  ".toCharArray(); // 50 chars.
            Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#');
            System.out.printf("0.%dxxx: %6d  :%s%n", i, frequencies[i], new String(bar));
        }
    }

}

平均的な結果は次のようになります。

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  11376  :#################################                 
0.1xxx:  11178  :###############################                   
0.2xxx:  11312  :#################################                 
0.3xxx:  10809  :############################                      
0.4xxx:  10242  :######################                            
0.5xxx:   8860  :########                                          
0.6xxx:   9004  :##########                                        
0.7xxx:   8987  :#########                                         
0.8xxx:   9075  :##########                                        
0.9xxx:   9157  :###########                                       

MR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  10097  :####################                              
0.1xxx:   9901  :###################                               
0.2xxx:  10018  :####################                              
0.3xxx:   9956  :###################                               
0.4xxx:   9974  :###################                               
0.5xxx:  10007  :####################                              
0.6xxx:  10136  :#####################                             
0.7xxx:   9937  :###################                               
0.8xxx:  10029  :####################                              
0.9xxx:   9945  :###################    

テストを繰り返すと、初期シードによってQR分布が大きく変化し、MR分布は安定していることがわかります。場合によっては、目的の一様分布に達することもありますが、多くの場合、そうではありません。これは、より極端な例の1つであり、グラフの境界を超えています。

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  41788  :##################################################
0.1xxx:  17495  :##################################################
0.2xxx:  10285  :######################                            
0.3xxx:   7273  :                                                  
0.4xxx:   5643  :                                                  
0.5xxx:   4608  :                                                  
0.6xxx:   3907  :                                                  
0.7xxx:   3350  :                                                  
0.8xxx:   2999  :                                                  
0.9xxx:   2652  :                                                  
于 2013-01-24T01:14:59.650 に答える
133

あなたが説明しているのは、線形合同法と呼ばれる一種のランダムジェネレータです。ジェネレータは次のように機能します。

  • シード値と乗数から始めます。
  • 乱数を生成するには:
    • シードに乗数を掛けます。
    • シードをこの値に等しく設定します。
    • この値を返します。

このジェネレータには多くの優れた特性がありますが、優れたランダムソースとして重大な問題があります。上にリンクされているウィキペディアの記事では、長所と短所のいくつかについて説明しています。つまり、適切なランダム値が必要な場合、これはおそらくあまり適切なアプローチではありません。

お役に立てれば!

于 2013-01-24T00:51:55.133 に答える
113

内部状態が少なすぎるため、乱数関数は貧弱です。任意のステップで関数によって出力される数値は、前の数値に完全に依存しています。たとえば、それmagicNumberが2であると仮定すると(例として)、シーケンスは次のようになります。

0.10 -> 0.20

同様のシーケンスによって強くミラーリングされます:

0.09 -> 0.18
0.11 -> 0.22

多くの場合、これによりゲーム内で顕著な相関関係が生成されます。たとえば、関数を連続して呼び出してオブジェクトのX座標とY座標を生成すると、オブジェクトは明確な対角線パターンを形成します。

乱数ジェネレーターがアプリケーションの速度を低下させていると信じる十分な理由がない限り(そしてこれは非常にありそうもないことです)、自分で作成しようとする正当な理由はありません。

于 2013-01-24T00:53:06.607 に答える
110

これに関する実際の問題は、出力ヒストグラムが初期シードに大きく依存していることです。多くの場合、ほぼ均一な出力になりますが、多くの場合、明らかに不均一な出力になります。

phpの機能がいかに悪いかについてのこの記事rand()に触発されて、私はとを使用していくつかのランダム行列画像を作成QuickRandomSystem.Randomました。System.Randomこの実行は、シードが非常に均一である場合に、シードが悪い影響を与える可能性があることを示しています(この場合は低い数値を優先します) 。

QuickRandom

System.Random

さらに悪い

この画像を取得するときに初期化QuickRandomすると、次のようになります。new QuickRandom(0.01, 1.03)

コード

using System;
using System.Drawing;
using System.Drawing.Imaging;

namespace QuickRandomTest
{
    public class QuickRandom
    {
        private double prevNum;
        private readonly double magicNumber;

        private static readonly Random rand = new Random();

        public QuickRandom(double seed1, double seed2)
        {
            if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
            prevNum = seed1;
            if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
            magicNumber = seed2;
        }

        public QuickRandom()
            : this(rand.NextDouble(), rand.NextDouble() * 10)
        {
        }

        public double Random()
        {
            return prevNum = (prevNum * magicNumber) % 1;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random();
            var qrand = new QuickRandom();
            int w = 600;
            int h = 600;
            CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png);
            CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png);
        }

        private static Image CreateMatrix(int width, int height, Func<double> f)
        {
            var bitmap = new Bitmap(width, height);
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    var c = (int) (f()*255);
                    bitmap.SetPixel(x, y, Color.FromArgb(c,c,c));
                }
            }

            return bitmap;
        }
    }
}
于 2013-01-25T17:03:19.357 に答える
37

乱数ジェネレーターの問題の1つは、「隠された状態」がないことです。最後の呼び出しで返された乱数がわかっている場合は、1つしかないため、時間の終わりまで送信するすべての乱数がわかります。可能な次の結果など。

考慮すべきもう1つのことは、乱数ジェネレーターの「期間」です。明らかに、doubleの仮数部分に等しい有限状態サイズでは、ループする前に最大2^52の値しか返すことができません。しかし、それが最良の場合です-期間1、2、3、4 ...のループがないことを証明できますか?存在する場合、そのような場合、RNGはひどい退化した動作をします。

さらに、乱数の生成は、すべての開始点に対して均一に分布しますか?そうでない場合は、RNGにバイアスがかかります。さらに悪いことに、開始シードに応じてさまざまな方法でバイアスがかかります。

これらすべての質問に答えることができれば、すばらしいです。できない場合は、ほとんどの人が車輪の再発明を行わず、実績のある乱数ジェネレーターを使用しない理由をご存知でしょう;)

(ちなみに、良い格言は次のとおりです。最速のコードは実行されないコードです。世界で最速のrandom()を作成できますが、あまりランダムでない場合は良くありません)

于 2013-01-24T00:54:40.383 に答える
36

PRNGを開発するときに私がいつも行った一般的なテストの1つは、次のことでした。

  1. 出力をchar値に変換します
  2. chars値をファイルに書き込む
  3. ファイルを圧縮する

これにより、約1〜20メガバイトのシーケンスに対して「十分に優れた」PRNGであるアイデアをすばやく繰り返すことができました。また、半単語の状態を持つ「十分に良い」PRNGは、サイクルポイントを見る目の能力をすぐに超える可能性があるため、単に目で調べるよりも優れたトップダウン画像を提供しました。

もし私が本当にうるさいのなら、私は良いアルゴリズムを取り、それらに対してDIEHARD / NISTテストを実行して、より多くの洞察を得てから、戻ってさらに微調整するかもしれません。

頻度分析とは対照的に、圧縮テストの利点は、簡単に適切な分布を構築できることです。0〜255の値のすべての文字を含む256の長さのブロックを出力し、これを100,000回実行するだけです。ただし、このシーケンスのサイクルの長さは256です。

歪んだ分布は、たとえわずかなマージンであっても、圧縮アルゴリズムによってピックアップする必要があります。特に、処理するのに十分な(たとえば、1メガバイトの)シーケンスを指定する場合はそうです。一部の文字、バイグラム、またはnグラムがより頻繁に発生する場合、圧縮アルゴリズムは、この分布スキューを、より短いコードワードで頻繁に発生するコードにエンコードでき、圧縮のデルタを取得します。

ほとんどの圧縮アルゴリズムは高速であり、実装を必要としないため(OSには実装が必要なため)、圧縮テストは、開発中のPRNGの合格/不合格をすばやく評価するのに非常に便利です。

あなたの実験で頑張ってください!

ああ、私はあなたのコードの次の小さなmodを使用して、上記のrngでこのテストを実行しました:

import java.io.*;

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        FileOutputStream fout = new FileOutputStream("qr20M.bin");

        for (int i = 0; i < 20000000; i ++) {
            fout.write((char)(qr.random()*256));
        }
    }
}

結果は次のとおりです。

Cris-Mac-Book-2:rt cris$ zip -9 qr20M.zip qr20M.bin2
adding: qr20M.bin2 (deflated 16%)
Cris-Mac-Book-2:rt cris$ ls -al
total 104400
drwxr-xr-x   8 cris  staff       272 Jan 25 05:09 .
drwxr-xr-x+ 48 cris  staff      1632 Jan 25 05:04 ..
-rw-r--r--   1 cris  staff      1243 Jan 25 04:54 QuickRandom.class
-rw-r--r--   1 cris  staff       883 Jan 25 05:04 QuickRandom.java
-rw-r--r--   1 cris  staff  16717260 Jan 25 04:55 qr20M.bin.gz
-rw-r--r--   1 cris  staff  20000000 Jan 25 05:07 qr20M.bin2
-rw-r--r--   1 cris  staff  16717402 Jan 25 05:09 qr20M.zip

出力ファイルをまったく圧縮できなかった場合、PRNGは適切だと思います。正直なところ、私はあなたのPRNGがそれほどうまくいくとは思いませんでした。このような単純な構造では、20メガバイトの16%だけがかなり印象的です。しかし、私はまだそれを失敗だと考えています。

于 2013-01-24T21:12:21.047 に答える
33

実装できる最速のランダムジェネレーターは次のとおりです。

ここに画像の説明を入力してください

XD、冗談は別として、ここで述べられていることすべてに加えて、乱数のテストは「難しい作業」[1]であり、疑似乱数の特定のプロパティをチェックするいくつかのテストがあります。それらの多くはここにあります:http ://www.random.org/analysis/#2005

ランダムジェネレータの「品質」を評価する簡単な方法の1つは、古いカイ2乗検定です。

static double chisquare(int numberCount, int maxRandomNumber) {
    long[] f = new long[maxRandomNumber];
    for (long i = 0; i < numberCount; i++) {
        f[randomint(maxRandomNumber)]++;
    }

    long t = 0;
    for (int i = 0; i < maxRandomNumber; i++) {
        t += f[i] * f[i];
    }
    return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
}

引用[1]

カイ二乗検定の考え方は、生成された数値が合理的に分散しているかどうかを確認することです。rよりも小さいN個の正の数を生成する場合、各値の約N / r個の数が得られると予想されます。しかし---そしてこれが問題の本質です---すべての値の発生頻度は完全に同じであってはなりません:それはランダムではありません!

単純に、各値の発生頻度の2乗の合計を計算し、予想される頻度でスケーリングしてから、シーケンスのサイズを差し引きます。この数値、「χ²統計」は、数学的に次のように表すことができます。

カイ二乗式

χ²統計がrに近い場合、数値はランダムです。それが遠すぎる場合、彼らはそうではありません。「近い」と「遠い」の概念は、より正確に定義できます。統計をランダムシーケンスのプロパティにどのように関連付けるかを正確に示すテーブルが存在します。実行している単純なテストの場合、統計は2√r以内である必要があります

この理論と次のコードを使用します。

abstract class RandomFunction {
    public abstract int randomint(int range); 
}

public class test {
    static QuickRandom qr = new QuickRandom();

    static double chisquare(int numberCount, int maxRandomNumber, RandomFunction function) {
        long[] f = new long[maxRandomNumber];
        for (long i = 0; i < numberCount; i++) {
            f[function.randomint(maxRandomNumber)]++;
        }

        long t = 0;
        for (int i = 0; i < maxRandomNumber; i++) {
            t += f[i] * f[i];
        }
        return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
    }

    public static void main(String[] args) {
        final int ITERATION_COUNT = 1000;
        final int N = 5000000;
        final int R = 100000;

        double total = 0.0;
        RandomFunction qrRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (qr.random() * range);
            }
        }; 
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, qrRandomInt);
        }
        System.out.printf("Ave Chi2 for QR: %f \n", total / ITERATION_COUNT);        

        total = 0.0;
        RandomFunction mathRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (Math.random() * range);
            }
        };         
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, mathRandomInt);
        }
        System.out.printf("Ave Chi2 for Math.random: %f \n", total / ITERATION_COUNT);
    }
}

次の結果が得られました。

Ave Chi2 for QR: 108965,078640
Ave Chi2 for Math.random: 99988,629040

QuickRandomの場合、これはrから遠く離れています (の外側 r ± 2 * sqrt(r)

そうは言っても、QuickRandomは高速である可能性がありますが、(別の回答で述べられているように)乱数ジェネレーターとしては適切ではありません。


[1] SEDGEWICK ROBERT、Algorithms in C、Addinson Wesley Publishing Company、1990年、516〜518ページ

于 2013-01-29T02:25:33.763 に答える
14

結果を評価するために、JavaScriptでアルゴリズムの簡単なモックアップをまとめました。0から99までの100,000のランダムな整数を生成し、各整数のインスタンスを追跡します。

私が最初に気付くのは、あなたは高い数よりも低い数を得る可能性が高いということです。seed1これは、高い場合とseed2低い場合に最もよく見られます。いくつかの例では、私は3つの数字しか得られませんでした。

せいぜい、あなたのアルゴリズムはいくらかの改良を必要とします。

于 2013-01-24T01:13:55.620 に答える
8

Math.Random()関数がオペレーティングシステムを呼び出して時刻を取得する場合、それを関数と比較することはできません。あなたの関数はPRNGですが、その関数は実際の乱数を目指しています。リンゴとオレンジ。

PRNGは高速である可能性がありますが、繰り返す前に長い期間を達成するのに十分な状態情報がありません(また、そのロジックは、その多くの状態情報で可能な期間を達成するのに十分なほど洗練されていません)。

期間は、PRNGが繰り返されるまでのシーケンスの長さです。これは、PRNGマシンが過去の状態と同じ状態に状態遷移するとすぐに発生します。そこから、その状態で始まった遷移を繰り返します。PRNGのもう1つの問題は、一意のシーケンスの数が少ないことと、繰り返される特定のシーケンスでの収束の縮退です。望ましくないパターンも存在する可能性があります。たとえば、数値が10進数で出力される場合、PRNGはかなりランダムに見えるが、2進数の値を調べると、ビット4が各呼び出しで0と1の間で単純に切り替わっていることを示しているとします。おっと!

メルセンヌツイスターと他のアルゴリズムを見てください。期間の長さとCPUサイクルのバランスをとる方法があります。基本的なアプローチの1つ(メルセンヌツイスターで使用)は、状態ベクトルを循環することです。つまり、数値が生成されているときは、状態全体に基づくのではなく、数ビット演算の対象となる状態配列からの数ワードに基づいています。ただし、各ステップで、アルゴリズムも配列内を移動し、コンテンツを少しずつスクランブリングします。

于 2013-01-24T06:20:00.607 に答える
7

Random複数のスレッドから単一のインスタンスにアクセスしない限り、思いついたユースケースで乱数生成のパフォーマンスが問題になる可能性はほとんどありません(でRandomあるためsynchronized)。

ただし、それが実際に当てはまり、大量の乱数が高速で必要な場合、ソリューションの信頼性は非常に低くなります。良い結果が得られる場合もあれば、(初期設定に基づいて)ひどい結果が得られる場合もあります。

クラスが提供するのと同じ数値がRandom必要な場合は、より高速に、そこでの同期を取り除くことができます。

public class QuickRandom {

    private long seed;

    private static final long MULTIPLIER = 0x5DEECE66DL;
    private static final long ADDEND = 0xBL;
    private static final long MASK = (1L << 48) - 1;

    public QuickRandom() {
        this((8682522807148012L * 181783497276652981L) ^ System.nanoTime());
    }

    public QuickRandom(long seed) {
        this.seed = (seed ^ MULTIPLIER) & MASK;
    }

    public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27)) / (double)(1L << 53);
    }

    private int next(int bits) {
        seed = (seed * MULTIPLIER + ADDEND) & MASK;
        return (int)(seed >>> (48 - bits));
    }

}

java.util.Randomコードを取得して同期を削除しただけで、Oracle HotSpotJVM7u9の元のパフォーマンスの2倍のパフォーマンスが得られました。それでもあなたのより遅いですQuickRandomが、それははるかに一貫した結果をもたらします。正確には、同じseed値とシングルスレッドアプリケーションの場合、元のクラスと同じ疑似乱数が得られます。Random


java.util.Randomこのコードは、 GNUGPLv2でライセンスされているOpenJDK7uの現在のコードに基づいています


10か月後に編集:

Random同期されていないインスタンスを取得するために、上記のコードを使用する必要がないことを発見しました。JDKにも1つあります!

Java7のThreadLocalRandomクラスを見てください。その中のコードは、上記の私のコードとほとんど同じです。Randomこのクラスは、乱数をすばやく生成するのに適した、ローカルスレッドで分離されたバージョンです。seed私が考えることができる唯一の欠点は、手動で設定できないことです。

使用例:

Random random = ThreadLocalRandom.current();
于 2013-01-28T14:07:03.550 に答える
7

そこには多くの疑似乱数ジェネレータがあります。たとえば、KnuthのranarrayMersenneツイスター、またはLFSRジェネレーターを探します。クヌースの記念碑的な「半数値アルゴリズム」は、領域を分析し、いくつかの線形合同法を提案します(実装が簡単で、高速です)。

java.util.Randomただし、またはに固執することをお勧めしますMath.random。これらは高速で、少なくとも時折使用する場合は問題ありません(つまり、ゲームなど)。ディストリビューション(モンテカルロプログラムまたは遺伝的アルゴリズム)に夢中になっている場合は、その実装を確認し(ソースはどこかにあります)、オペレーティングシステムまたはrandom.orgから真に乱数をシードします。 。セキュリティが重要なアプリケーションでこれが必要な場合は、自分で掘り下げる必要があります。そして、その場合のように、ビットが欠落している色付きの正方形がここに噴出していることを信じるべきではないので、ここで黙ります。

于 2013-01-24T13:17:40.930 に答える
3

「ランダム」とは、数値を取得することだけではありません。あなたが持っているのは疑似ランダムです。

疑似ランダムが目的に十分適している場合は、確かにそれははるかに高速です(XOR +ビットシフトはあなたが持っているものよりも高速になります)

ロルフ

編集:

OK、この答えに急いでいた後、あなたのコードがより速い本当の理由に答えさせてください:

Math.Random()のJavaDocから

このメソッドは適切に同期されているため、複数のスレッドで正しく使用できます。ただし、多くのスレッドが高速で疑似乱数を生成する必要がある場合は、各スレッドが独自の疑似乱数ジェネレーターを持つようにするための競合を減らすことができます。

これが、コードが高速である理由である可能性があります。

于 2013-01-24T00:44:32.797 に答える
3

java.util.Randomはそれほど違いはなく、Knuthによって記述された基本的なLCGです。ただし、主に2つの主な利点/相違点があります。

  • スレッドセーフ-各更新はCASであり、単純な書き込みよりもコストがかかり、ブランチが必要です(完全に予測されたシングルスレッドであっても)。CPUによっては、大きな違いが生じる可能性があります。
  • 非公開の内部状態-これは重要なことです。乱数が予測できないようにします。

その下には、java.util.Randomで「ランダム」整数を生成するメインルーチンがあります。


  protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
          oldseed = seed.get();
          nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

AtomicLongと非公開の状態を削除すると(つまり、のすべてのビットを使用してlong)、2倍の乗算/モジュロよりも高いパフォーマンスが得られます。

最後の注意:Math.random単純なテスト以外には使用しないでください。競合が発生しやすく、同時に呼び出しているスレッドが2つでもあると、パフォーマンスが低下します。それのほとんど知られていない歴史的特徴の1つは、JavaでのCASの導入です-悪名高いベンチマークを打ち負かすために(最初にIBMが組み込みを介して、次にSunが「JavaからのCAS」を作成しました)

于 2013-01-25T00:52:51.173 に答える
0

これは、ゲームで使用するランダム関数です。それはかなり速く、そして良い(十分な)分布を持っています。

public class FastRandom {

    public static int randSeed;

      public static final int random()
      {
        // this makes a 'nod' to being potentially called from multiple threads
        int seed = randSeed;

        seed    *= 1103515245;
        seed    += 12345;
        randSeed = seed;
        return seed;
      }

      public static final int random(int range)
      {
        return ((random()>>>15) * range) >>> 17;
      }

      public static final boolean randomBoolean()
      {
         return random() > 0;
      }

       public static final float randomFloat()
       {
         return (random()>>>8) * (1.f/(1<<24));
       }

       public static final double randomDouble() {
           return (random()>>>8) * (1.0/(1<<24));
       }
}
于 2014-06-05T13:24:17.960 に答える