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

2023-08-28 20:44:04 289

前言

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

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

初次解答

我一开始想到的办法是

生成一个足够大的ID池（其实就是需要多少就生成多少）
对ID池中的数字进行随机排序
依次消费ID池中的数字

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

初遇梅森旋转算法

后面咨询了网友后得知了一个高效的随机数算法：梅森旋转（MersenneTwister/MT）。通过搜索资料得知：

梅森旋转算法（Mersennetwister）是一个伪随机数发生算法。由松本真和西村拓士在1997年开发，基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数，修正了古典随机数发生算法的很多缺陷。
最为广泛使用MersenneTwister的一种变体是MT19937，可以产生32位整数序列。

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

MT19937算法实现

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

importjava.util.Random;

/**
*MT19937的Java实现
*/
publicclassMTRandomextendsRandom{

//ConstantsusedintheoriginalCimplementation
privatefinalstaticintUPPER_MASK=0x80000000;
privatefinalstaticintLOWER_MASK=0x7fffffff;

privatefinalstaticintN=624;
privatefinalstaticintM=397;
privatefinalstaticintMAGIC[]={0x0,0x9908b0df};
privatefinalstaticintMAGIC_FACTOR1=1812433253;
privatefinalstaticintMAGIC_FACTOR2=1664525;
privatefinalstaticintMAGIC_FACTOR3=1566083941;
privatefinalstaticintMAGIC_MASK1=0x9d2c5680;
privatefinalstaticintMAGIC_MASK2=0xefc60000;
privatefinalstaticintMAGIC_SEED=19650218;
privatefinalstaticlongDEFAULT_SEED=5489L;

//Internalstate
privatetransientint[]mt;
privatetransientintmti;
privatetransientbooleancompat=false;

//TemporarybufferusedduringsetSeed(long)
privatetransientint[]ibuf;

/**
*ThedefaultconstructorforaninstanceofMTRandom.Thisinvokes
*theno-argumentconstructorforjava.util.Randomwhichwillresult
*intheclassbeinginitialisedwithaseedvalueobtainedbycalling
*System.currentTimeMillis().
*/
publicMTRandom(){}

/**
*Thisversionoftheconstructorcanbeusedtoimplementidentical
*behaviourtotheoriginalCcodeversionofthisalgorithmincluding
*exactlyreplicatingthecasewheretheseedvaluehadnotbeenset
*priortocallinggenrand_int32.
*
*Ifthecompatibilityflagissettotrue,thenthealgorithmwillbe
*seededwiththesamedefaultvalueaswasusedintheoriginalC
*code.FurthermorethesetSeed()method,whichmusttakea64bit
*longvalue,willbelimitedtousingonlythelower32bitsofthe
*seedtofacilitateseamlessmigrationofexistingCcodeintoJava
*whereidenticalbehaviourisrequired.
*

*Whilstusefulforensuringbackwardscompatibility,itisadvised
*thatthisfeaturenotbeusedunlessspecificallyrequired,dueto
*thereductioninstrengthoftheseedvalue.
*
*@paramcompatibleCompatibilityflagforreplicatingoriginal
*behaviour.
*/
publicMTRandom(booleancompatible){
super(0L);
compat=compatible;
setSeed(compat?DEFAULT_SEED:System.currentTimeMillis());
}

/**
*Thisversionoftheconstructorsimplyinitialisestheclasswith
*thegiven64bitseedvalue.Forabetterrandomnumbersequence
*thisseedvalueshouldcontainasmuchentropyaspossible.
*
*@paramseedTheseedvaluewithwhichtoinitialisethisclass.
*/
publicMTRandom(longseed){
super(seed);
}

/**
*Thisversionoftheconstructorinitialisestheclasswiththe
*givenbytearray.Allthedatawillbeusedtoinitialisethis
*instance.
*
*@parambufThenon-emptybytearrayofseedinformation.
*@throwsNullPointerExceptionifthebufferisnull.
*@throwsIllegalArgumentExceptionifthebufferhaszerolength.
*/
publicMTRandom(byte[]buf){
super(0L);
setSeed(buf);
}

/**
*Thisversionoftheconstructorinitialisestheclasswiththe
*givenintegerarray.Allthedatawillbeusedtoinitialise
*thisinstance.
*
*@parambufThenon-emptyintegerarrayofseedinformation.
*@throwsNullPointerExceptionifthebufferisnull.
*@throwsIllegalArgumentExceptionifthebufferhaszerolength.
*/
publicMTRandom(int[]buf){
super(0L);
setSeed(buf);
}

//Initializesmt[N]withasimpleintegerseed.Thismethodis
//requiredaspartoftheMersenneTwisteralgorithmbutneed
//notbemadepublic.
privatefinalvoidsetSeed(intseed){

//Annoyingruntimecheckforinitialisationofinternaldata
//causedbyjava.util.RandominvokingsetSeed()duringinit.
//Thisisunavoidablebecausenofieldsinourinstancewill
//havebeeninitialisedatthispoint,notevenifthecode
//wereplacedatthedeclarationofthemembervariable.
if(mt==null)mt=newint[N];

//----BeginMersenneTwisterAlgorithm----
mt[0]=seed;
for(mti=1;mti>>30))+mti);
}
//----EndMersenneTwisterAlgorithm----
}

/**
*Thismethodresetsthestateofthisinstanceusingthe64
*bitsofseeddataprovided.Notethatifthesameseeddata
*ispassedtotwodifferentinstancesofMTRandom(bothof
*whichsharethesamecompatibilitystate)thenthesequence
*ofnumbersgeneratedbybothinstanceswillbeidentical.
*

*Ifthisinstancewasinitialisedin'compatibility'modethen
*thismethodwillonlyusethelower32bitsofanyseedvalue
*passedinandwillmatchthebehaviouroftheoriginalCcode
*exactlywithrespecttostateinitialisation.
*
*@paramseedThe64bitvalueusedtoinitialisetherandom
*numbergeneratorstate.
*/
publicfinalsynchronizedvoidsetSeed(longseed){
if(compat){
setSeed((int)seed);
}else{

//Annoyingruntimecheckforinitialisationofinternaldata
//causedbyjava.util.RandominvokingsetSeed()duringinit.
//Thisisunavoidablebecausenofieldsinourinstancewill
//havebeeninitialisedatthispoint,notevenifthecode
//wereplacedatthedeclarationofthemembervariable.
if(ibuf==null)ibuf=newint[2];

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

/**
*Thismethodresetsthestateofthisinstanceusingthebyte
*arrayofseeddataprovided.Notethatcallingthismethod
*isequivalenttocalling"setSeed(pack(buf))"andinparticular
*willresultinanewintegerarraybeinggeneratedduringthe
*call.Ifyouwishtoretainthisseeddatatoallowthepseudo
*randomsequencetoberestartedthenitwouldbemoreefficient
*tousethe"pack()"methodtoconvertitintoanintegerarray
*firstandthenusethattore-seedtheinstance.Thebehaviour
*oftheclasswillbethesameinbothcasesbutitwillbemore
*efficient.
*
*@parambufThenon-emptybytearrayofseedinformation.
*@throwsNullPointerExceptionifthebufferisnull.
*@throwsIllegalArgumentExceptionifthebufferhaszerolength.
*/
publicfinalvoidsetSeed(byte[]buf){
setSeed(pack(buf));
}

/**
*Thismethodresetsthestateofthisinstanceusingtheinteger
*arrayofseeddataprovided.Thisisthecanonicalwayof
*resettingthepseudorandomnumbersequence.
*
*@parambufThenon-emptyintegerarrayofseedinformation.
*@throwsNullPointerExceptionifthebufferisnull.
*@throwsIllegalArgumentExceptionifthebufferhaszerolength.
*/
publicfinalsynchronizedvoidsetSeed(int[]buf){
intlength=buf.length;
if(length==0)thrownewIllegalArgumentException("Seedbuffermaynotbeempty");
//----BeginMersenneTwisterAlgorithm----
inti=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;//MSBis1;assuringnon-zeroinitialarray
//----EndMersenneTwisterAlgorithm----
}

/**
*Thismethodformsthebasisforgeneratingapseudorandomnumber
*sequencefromthisclass.Ifgivenavalueof32,thismethod
*behavesidenticallytothegenrand_int32functionintheoriginal
*CcodeandensuresthatusingthestandardnextInt()function
*(inheritedfromRandom)weareabletoreplicatebehaviourexactly.
*

*Notethatwherethenumberofbitsrequestedisnotequalto32
*thenbitswillsimplybemaskedoutfromthetopofthereturned
*integervalue.Thatistosaythat:
*
*mt.setSeed(12345);
*intfoo=mt.nextInt(16)+(mt.nextInt(16)<<16);
*willnotgivethesameresultas
**mt.setSeed(12345);
*intfoo=mt.nextInt(32);
*
*@parambitsThenumberofsignificantbitsdesiredintheoutput.
*@returnThenextvalueinthepseudorandomsequencewiththe
*specifiednumberofbitsinthelowerpartoftheinteger.
*/
protectedfinalsynchronizedintnext(intbits){
//----BeginMersenneTwisterAlgorithm----
inty,kk;
if(mti>=N){//generateNwordsatonetime

//IntheoriginalCimplementation,mtiischeckedhere
//todetermineifinitialisationhasoccurred;ifnot
//itinitialisesthisinstancewithDEFAULT_SEED(5489).
//Thisisnolongernecessaryasinitialisationofthe
//Javainstancemustresultininitialisationoccurring
//UsetheconstructorMTRandom(true)toenablebackwards
//compatiblebehaviour.

for(kk=0;kk>>1)^MAGIC[y&0x1];
}
for(;kk>>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);
//----EndMersenneTwisterAlgorithm----
return(y>>>(32-bits));
}

//Thisisafairlyobscurelittlecodesectiontopacka
//byte[]intoanint[]inlittleendianordering.

/**
*Thissimplyutilitymethodcanbeusedincaseswhereabyte
*arrayofseeddataistobeusedtorepeatedlyre-seedthe
*randomnumbersequence.Bypackingthebytearrayintoan
*integerarrayfirst,usingthismethod,andtheninvoking
*setSeed()withthat;itremovestheneedtore-packthebyte
*arrayeachtimesetSeed()iscalled.
*
*Ifthelengthofthebytearrayisnotamultipleof4then
*itisimplicitlypaddedwithzerosasnecessary.Forexample:
*
byte[]{0x01,0x02,0x03,0x04,0x05,0x06}
*becomes
*int[]{0x04030201,0x00000605}
*
*Notethatthismethodwillnotcomplainifthegivenbytearray
*isemptyandwillproduceanemptyintegerarray,butthe
*setSeed()methodwillthrowanexceptioniftheemptyinteger
*arrayispassedtoit.
*
*@parambufThenon-nullbytearraytobepacked.
*@returnAnon-nullintegerarrayofthepackedbytes.
*@throwsNullPointerExceptionifthegivenbytearrayisnull.
*/
publicstaticint[]pack(byte[]buf){
intk,blen=buf.length,ilen=((buf.length+3)>>>2);
int[]ibuf=newint[ilen];
for(intn=0;nblen)m=blen;
for(k=buf[--m]&0xff;(m&0x3)!=0;k=(k<<8)|buf[--m]&0xff);
ibuf[n]=k;
}
returnibuf;
}
}

测试

测试代码

//MT19937的Java实现
MTRandommtRandom=newMTRandom();
Mapmap=newHashMap<>();
//循环次数
inttimes=1000000;
longstartTime=System.currentTimeMillis();
for(inti=0;i
测试结果



times:1000000

num:999886

proportion:0.999886

time:374



以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

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

热门推荐

随机推荐