Java实现高效随机数算法的示例代码

网友投稿 234 2023-01-13


Java实现高效随机数算法的示例代码

前言

事情起源于一位网友分享了一个有趣的面试题:

生成由六位数字组成的ID,要求随机数字,不排重,不可自增,且数字不重复。ID总数为几十万。

初次解答

我一开始想到的办法是

生成一个足够大的ID池(其实就是需要多少就生成多少)

对ID池中的数字进行随机排序

依次消费ID池中的数字

可惜这个方法十分浪费空间,且性能很差。

初遇梅森旋转算法

后面咨询了网友后得知了一个高效的随机数算法:梅森旋转(Mersenne Twister/MT)。通过搜索资料得知:

梅森旋转算法(Mersenne twister)是一个伪随机数发生算法。由松本真和西村拓士在1997年开发,基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数,修正了古典随机数发生算法的很多缺陷。

最为广泛使用Mersenne Twister的一种变体是MT19937,可以产生32位整数序列。

PS:此算法依然无法完美解决面试题,但是也算学到了新知识

MT19937算法实现

后面通过Google,找到了一个高效的MT19937的java版本代码。原代码链接为http://math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVA/MTRandom.java

import java.util.Random;

/**

* MT19937的Java实现

*/

public class MTRandom extends Random {

// Constants used in the original C implehttp://mentation

private final static int UPPER_MASK = 0x80000000;

private final static int LOWER_MASK = 0x7fffffff;

private final static int N = 624;

private final static int M = 397;

private final static int MAGIC[] = { 0x0, 0x9908b0df };

private final static int MAGIC_FACTOR1 = 1812433253;

private final static int MAGIC_FACTOR2 = 1664525;

private final static int MAGIC_FACTOR3 = 1566083941;

private final static int MAGIC_MASK1 = 0x9d2c5680;

private final static int MAGIC_MASK2 = 0xefc60000;

private final static int MAGIC_SEED = 19650218;

private final static long DEFAULT_SEED = 5489L;

// Internal state

private transient int[] mt;

private transient int mti;

private transient boolean compat = false;

// Temporary buffer used during setSeed(long)

private transient int[] ibuf;

/**

* The default constructor for an instance of MTRandom. This invokes

* the no-argument constructor for java.util.Random which will result

* in the class being initialised with a seed value obtained by calling

* System.currentTimeMillis().

*/

public MTRandom() { }

/**

* This version of the constructor can be used to implement identical

* behaviour to the original C code version of this algorithm including

* exactly replicating the case where the seed value had not been set

* prior to calling genrand_int32.

*

* If the chttp://ompatibility flag is set to true, then the algorithm will be

* seeded with the same default value as was used in the original C

* code. Furthermore the setSeed() method, which must take a 64 bit

* long value, will be limited to using only the lower 32 bits of the

* seed to facilitate seamless migration of existing C code into Java

* where identical behaviour is required.

*

* Whilst useful for ensuring backwards compatibility, it is advised

* that this feature not be used unless specifically required, due to

* the reduction in strength of the seed value.

*

* @param compatible Compatibility flag for replicating original

* behaviour.

*/

public MTRandom(boolean compatible) {

super(0L);

compat = compatible;

setSeed(compat?DEFAULT_SEED:System.currentTimeMillis());

}

/**

* This version of the constructor simply initialises the class with

* the given 64 bit seed value. For a better random number sequence

* this seed value should contain as much entropy as possible.

*

* @param seed The seed value with which to initialise this class.

*/

public MTRandom(long seed) {

super(seed);

}

/**

* This version of the constructor initialises the class with the

* given byte array. All the data will be used to initialise this

* instance.

*

* @param buf The non-empty byte array of seed information.

* @throws NullPointerException if the buffer is null.

* @throws IllegalArgumentException if the buffer has zero length.

*/

public MTRandom(byte[] buf) {

super(0L);

setSeed(buf);

}

/**

* This version of the constructor initialises the class with the

* given integer array. All the data will be used to initialise

* this instance.

*

* @param buf The non-empty integer array of seed information.

* @throws NullPointerException if the buffer is null.

* @throws IllegalArgumentException if the buffer has zero length.

*/

public MTRandom(int[] buf) {

super(0L);

setSeed(buf);

}

// Initializes mt[N] with a simple integer seed. This method is

// required as part of the Mersenne Twister algorithm but need

// not be made public.

private final void setSeed(int seed) {

// Annoying runtime check for initialisation of internal data

// caused by java.util.Random invoking setSeed() during init.

// This is unavoidable because no fields in our instance will

// have been initialised at this point, not even if the code

// were placed at the declaration of the member variable.

if (mt == null) mt = new int[N];

// ---- Begin Mersenne Twister Algorithm ----

mt[0] = seed;

for (mti = 1; mti < N; mti++) {

mt[mti] = (MAGIC_FACTOR1 * (mt[mti-1] ^ (mt[mti-1] >>> 30)) + mti);

}

// ---- End Mersenne Twister Algorithm ----

}

/**

* This method resets the state of this instance using the 64

* bits of seed data provided. Note that if the same seed data

* is passed to two different instances of MTRandom (both of

* which share the same compatibility state) then the sequence

* of numbers generated by both instances will be identical.

*

* If this instance was initialised in 'compatibility' mode then

* this method will only use the lower 32 bits of any seed value

* passed in and will match the behaviour of the original C code

* exactly with respect to state initialisation.

*

* @param seed The 64 bit value used to initialise the random

* number generator state.

*/

public final synchronized void setSeed(long seed) {

if (compat) {

setSeed((int)seed);

} else {

// Annoying runtime check for initialisation of internal data

// caused by java.util.Random invoking setSeed() during init.

// This is unavoidable because no fields in our instance will

// have been initialised at this point, not even if the code

// were placed at the declaration of the member variable.

if (ibuf == null) ibuf = new int[2];

ibuf[0] = (int)seed;

ibuf[1] = (int)(seed >>> 32);

setSeed(ibuf);

}

}

/**

* This method resets the state of this instance using the byte

* array of seed data provided. Note that calling this method

* is equivalent to calling "setSeed(pack(buf))" and in particular

* will result in a new integer array being generated during the

* call. If you wish to retain this seed data to allow the pseudo

* random sequence to be restarted then it would be more efficient

* to use the "pack()" method to convert it into an integer array

* first and then use that to re-seed the instance. The behaviour

* of the class will be the same in both cases but it will be more

* efficient.

*

* @param buf The non-empty byte array of seed information.

* @throws NullPointerException if the buffer is null.

* @throws IllegalArgumentException if the buffer has zero length.

*/

public final void setSeed(byte[] buf) {

setSeed(pack(buf));

}

/**

* This method resets the state of this instance using the integer

* array of seed data provided. This is the canonical way of

* resetting the pseudo random number sequence.

*

* @param buf The non-empty integer array of seed information.

* @throws NullPointerException if the buffer is null.

* @throws IllegalArgumentException if the buffer has zero length.

*/

public final synchronized void setSeed(int[] buf) {

int length = buf.length;

if (length == 0) throw new IllegalArgumentException("Seed buffer may not be empty");

// ---- Begin Mersenne Twister Algorithm ----

int i = 1, j = 0, k = (N > length ? N : length);

setSeed(MAGIC_SEED);

for (; k > 0; k--) {

mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * MAGIC_FACTOR2)) + buf[j] + j;

i++; j++;

if (i >= N) { mt[0] = mt[N-1]; i = 1; }

if (j >= length) j = 0;

}

for (k = N-1; k > 0; k--) {

mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >>> 30)) * MAGIC_FACTOR3)) - i;

i++;

if (i >= N) { mt[0] = mt[N-1]; i = 1; }

}

mt[0] = UPPER_MASK; // MSB is 1; assuring non-zero initial array

// ---- End Mersenne Twister Algorithm ----

}

/**

* This method forms the basis for generating a pseudo random number

* sequence from this class. If given a value of 32, this method

* behaves identically to the genrand_int32 function in the original

* C code and ensures that using the standard nextInt() function

* (inherited from Random) we are able to replicate behaviour exactly.

*

* Note that where the number of bits requested is not equal to 32

* then bits will simply be masked out from the top of the returned

* integer value. That is to say that:

*

* mt.setSeed(12345);

* int foo = mt.nextInt(16) + (mt.nextInt(16) << 16);

* will not give the same result as

*

* mt.setSeed(12345);

* int foo = mt.nextInt(32);

*

* @param bits The number of significant bits desired in the output.

* @return The next value in the pseudo random sequence with the

* specified number of bits in the lower part of the integer.

*/

protected final synchronized int next(int bits) {

// ---- Begin Mersenne Twister Algorithm ----

int y, kk;

if (mti >= N) { // generate N words at one time

// In the original C implementation, mti is checked here

// to determine if initialisation has occurred; if not

// it initialises this instance with DEFAULT_SEED (5489).

// This is no longer necessary as initialisation of the

// Java instance must result in initialisation occurring

// Use the constructor MTRandom(true) to enable backwards

// compatible behaviour.

for (kk = 0; kk < N-M; kk++) {

y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);

mt[kk] = mt[kk+M] ^ (y >>> 1) ^ MAGIC[y & 0x1];

}

for (;kk < N-1; kk++) {

y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);

mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ MAGIC[y & 0x1];

}

y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);

mt[N-1] = mt[M-1] ^ (y >>> 1) ^ MAGIC[y & 0x1];

mti = 0;

}

y = mt[mti++];

// Tempering

y ^= (y >>> 11);

y ^= (y << 7) & MAGIC_MASK1;

y ^= (y << 15) & MAGIC_MASK2;

y ^= (y >>> 18);

// ---- End Mersenne Twister Algorithm ----

return (y >>> (32-bits));

}

// This is a fairly obscure little code section to pack a

// byte[] into an int[] in little endian ordering.

/**

* This simply utility method can be used in cases where a byte

* array of seed data is to be used to repeatedly re-seed the

* random number sequence. By packing the byte array into an

* integer array first, using this method, and then invoking

* setSeed() with that; it removes the need to re-pack the byte

* array each time setSeed() is called.

*

* If the length of the byte array is not a multiple of 4 then

* it is implicitly padded with zeros as necessary. For example:

*

* becomes

*

*

* Note that this method will not complain if the given byte array

* is empty and will produce an empty integer array, but the

* setSeed() method will throw an exception if the empty integer

* array is passed to it.

*

* @param buf The non-null byte array to be packed.

* @return A non-null integer array of the packed bytes.

* @throws NullPointerException if the given byte array is null.

*/

public static int[] pack(byte[] buf) {

int k, blen = buf.length, ilen = ((buf.length+3) >>> 2);

int[] ibuf = new int[ilen];

for (int n = 0; n < ilen; n++) {

int m = (n+1) << 2;

if (m > blen) m = blen;

for (k = buf[--m]&0xff; (m & 0x3) != 0; k = (k << 8) | buf[--m]&0xff);

ibuf[n] = k;

}

return ibuf;

}

}

测试

测试代码

// MT19937的Java实现

MTRandom mtRandom=new MTRandom();

Map map=new HashMap<>();

//循环次数

int times=1000000;

long startTime=System.currentTimeMillis();

for(int i=0;i

//使用Map去重

map.put(mtRandom.next(32),0);

}

//打印循环次数

System.out.println("times:"+times);

//打印Map的个数

System.out.println("num:"+map.size());

//打印非重复比率

System.out.println("proportion:"+map.size()/(double)times);

//花费的时间(单位为毫秒)

System.out.println("time:"+(System.currentTimeMillis()-startTime));

测试结果

times:1000000

num:999886

proportion:0.999886

time:374

//使用Map去重

map.put(mtRandom.next(32),0);

}

//打印循环次数

System.out.println("times:"+times);

//打印Map的个数

System.out.println("num:"+map.size());

//打印非重复比率

System.out.println("proportion:"+map.size()/(double)times);

//花费的时间(单位为毫秒)

System.out.println("time:"+(System.currentTimeMillis()-startTime));

测试结果

times:1000000

num:999886

proportion:0.999886

time:374


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:高级数据结构及应用之使用bitmap进行字符串去重的方法实例
下一篇:利用枚举法求直方图中最大矩形面积的方法实例
相关文章

 发表评论

暂时没有评论,来抢沙发吧~