4

クラスjava.util.Randomを使用する場合、メソッドnextInt（）をN回呼び出すことで得られる値を、はるかに効率的な方法で（具体的にはO（1）で）取得するにはどうすればよいですか？

たとえば、特定のシード値を使用してRandomオブジェクトを作成し、100,000番目の「nextInt（）値」（つまり、メソッドnextInt（）を100,000回呼び出した後に取得した値）を高速に取得したい場合、私はそれをすることができますか？

簡単にするために、JDKのバージョン1.7.06を想定します。これは、クラスRandomの一部のプライベートフィールドの正確な値を知る必要がある場合があるためです。そして、と言えば、ランダムな値の計算に関連する次のフィールドが見つかりました。

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

ランダム性について少し調べたところ、線形合同法を使用してランダム値が取得されることがわかりました。アルゴリズムを実行する実際のメソッドは、メソッドnext（int）です。

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));
}

アルゴリズムに関連する行は、次のシード値を取得する行です。

nextseed = (oldseed * multiplier + addend) & mask;

それで、より具体的には、この式を一般化して「n番目の次のシード」値を取得する方法はありますか？ここでは、それを取得した後、変数「ビット」を32にすることでn番目のint値を取得できると想定しています（メソッドnextInt（）は単にnext（32）を呼び出し、結果を返します）。

前もって感謝します

PS：おそらく、これはmathexchangeに適した質問ですか？

4

2 に答える 2

5

あなたはO(log N)時間内にそれを行うことができます。から始めて、今のところモジュラス（2 48s(0) ）を無視すると、（との省略形としてとを使用して）次のことがわかります。mamultiplieraddend

s(1) = s(0) * m + a
s(2) = s(1) * m + a = s(0) * m² + (m + 1) * a
s(3) = s(2) * m + a = s(0) * m³ + (m² + m + 1) * a
...
s(N) = s(0) * m^N + (m^(N-1) + ... + m + 1) * a

これで、2乗を繰り返すことによるべき乗剰余によりm^N (mod 2^48)、段階的に簡単に計算できます。O(log N)

他の部分はもう少し複雑です。今のところ再びモジュラスを無視すると、幾何学的な合計は次のようになります。

(m^N - 1) / (m - 1)

このモジュロ2^48の計算を少し重要なものにしているのは、モジュロm - 1と互いに素ではないということです。しかし、

m = 0x5DEECE66DL

の最大公約数m-1とモジュラスは4であり(m-1)/4、モジュラ逆invモジュロを持ち2^48ます。させて

c = (m^N - 1) (mod 4*2^48)

それで

(c / 4) * inv ≡ (m^N - 1) / (m - 1) (mod 2^48)

それで

  • 計算するM ≡ m^N (mod 2^50)
  • 計算するinv

取得する

s(N) ≡ s(0)*M + ((M - 1)/4)*inv*a (mod 2^48)
于 2013-01-31T00:23:23.423 に答える
2

私はダニエル・フィッシャーからの答えを受け入れました。それは正しく、一般的な解決策を示しているからです。ダニエルの答えを使用して、式の基本的な実装を示すJavaコードを使用した具体的な例を示します（クラスBigIntegerを広範囲に使用したため、最適ではない可能性がありますが、実際にメソッドnextInt（ ）N回）：

import java.math.BigInteger;
import java.util.Random;


public class RandomNthNextInt {

    // copied from java.util.Random =========================
    private static final long   multiplier  = 0x5DEECE66DL;
    private static final long   addend      = 0xBL;
    private static final long   mask        = (1L << 48) - 1;


    private static long initialScramble(long seed) {

        return (seed ^ multiplier) & mask;
    }

    private static int getNextInt(long nextSeed) {

        return (int)(nextSeed >>> (48 - 32));
    }
    // ======================================================

    private static final BigInteger mod = BigInteger.valueOf(mask + 1L);
    private static final BigInteger inv = BigInteger.valueOf((multiplier - 1L) / 4L).modInverse(mod);


    /**
     * Returns the value obtained after calling the method {@link Random#nextInt()} {@code n} times from a
     * {@link Random} object initialized with the {@code seed} value.
     * <p>
     * This method does not actually create any {@code Random} instance, instead it applies a direct formula which
     * calculates the expected value in a more efficient way (close to O(log N)).
     * 
     * @param seed
     *            The initial seed value of the supposed {@code Random} object
     * @param n
     *            The index (starting at 1) of the "nextInt() value"
     * @return the nth "nextInt() value" of a {@code Random} object initialized with the given seed value
     * @throws IllegalArgumentException
     *             If {@code n} is not positive
     */
    public static long getNthNextInt(long seed, long n) {

        if (n < 1L) {
            throw new IllegalArgumentException("n must be positive");
        }

        final BigInteger seedZero = BigInteger.valueOf(initialScramble(seed));
        final BigInteger nthSeed = calculateNthSeed(seedZero, n);

        return getNextInt(nthSeed.longValue());
    }

    private static BigInteger calculateNthSeed(BigInteger seed0, long n) {

        final BigInteger largeM = calculateLargeM(n);
        final BigInteger largeMmin1div4 = largeM.subtract(BigInteger.ONE).divide(BigInteger.valueOf(4L));

        return seed0.multiply(largeM).add(largeMmin1div4.multiply(inv).multiply(BigInteger.valueOf(addend))).mod(mod);
    }

    private static BigInteger calculateLargeM(long n) {

        return BigInteger.valueOf(multiplier).modPow(BigInteger.valueOf(n), BigInteger.valueOf(1L << 50));
    }

    // =========================== Testing stuff ======================================

    public static void main(String[] args) {

        final long n = 100000L; // change this to test other values
        final long seed = 1L; // change this to test other values

        System.out.println(n + "th nextInt (formula) = " + getNthNextInt(seed, n));
        System.out.println(n + "th nextInt (slow)    = " + getNthNextIntSlow(seed, n));
    }

    private static int getNthNextIntSlow(long seed, long n) {

        if (n < 1L) {
            throw new IllegalArgumentException("n must be positive");
        }

        final Random rand = new Random(seed);
        for (long eL = 0; eL < (n - 1); eL++) {
            rand.nextInt();
        }
        return rand.nextInt();
    }
}

注：最初のシード値を取得するために使用されるメソッドinitialScramble（long）に注意してください。これは、特定のシードを使用してインスタンスを初期化するときのクラスRandomの動作です。

于 2013-01-31T02:51:45.747 に答える