java random.nextInt的坑

下面的代碼

Random random = new Random();
Integer code = random.nextInt(len);

很簡單的兩句代碼，需要注意兩點(diǎn)

第一：nextInt的取值是[0,n) ，不包括n。如果是隨機(jī)list，直接傳list的size，不用擔(dān)心下標(biāo)越界。

api說明：

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive)

第二個(gè)：nextInt在數(shù)據(jù)量小的時(shí)候，重復(fù)概率比較高。比如現(xiàn)在有一個(gè)大小為6的list，我希望隨機(jī)顯示4條且不重復(fù)。正確的做法是每次得到隨機(jī)數(shù)后，移除下標(biāo)對(duì)于的對(duì)象。這樣即使random重復(fù)了也沒關(guān)系，因?yàn)橄聵?biāo)對(duì)應(yīng)數(shù)據(jù)移除后，同樣的下標(biāo)對(duì)應(yīng)的對(duì)象是不一樣的。

千萬別像我之前的做法，遍歷list，然后隨機(jī)取到下標(biāo)后，再去重。這樣有時(shí)能得到4個(gè)，有時(shí)得不到。比如下標(biāo)會(huì)出現(xiàn) 5,1,1,1，2,1.這樣的話，最終list只會(huì)有三個(gè)。

之前一直沒有懷疑是這段代碼的問題，懷疑接口不穩(wěn)定或者是數(shù)據(jù)不完整之類的。查日志還一直在看接口傳遞參數(shù)和返回參數(shù)，結(jié)果是因?yàn)閷?duì)nextInt理解不深刻，在我印象中感覺randomInt是隨機(jī)數(shù)且不重復(fù)的，不過事實(shí)證明我想多了。

java random.nextInt()不隨機(jī)性

最近在研究算法，也寫一些小程序，其中有一個(gè)是《算法導(dǎo)論》中的習(xí)題：描述RANDOM(a, b)過程的一種實(shí)現(xiàn)，它只調(diào)用RANDOM(0, 1)，作為a和b的函數(shù)，你的程序的期望時(shí)間運(yùn)行時(shí)間是多少？

這個(gè)題在網(wǎng)上已經(jīng)有很多人給出了答案

我也自己寫了一個(gè)算法，不過本文的主題不是針對(duì)這個(gè)問題，而是RANDOM(0, 1)的實(shí)現(xiàn)方法。我剛開始使用的是random.nextInt(0, 1)來取隨機(jī)的0和1，也測(cè)試了其“隨機(jī)性”，代碼如下：

 //用Random.nextInt(2)獲取0,1隨機(jī)數(shù)
 //獲取概率均為0.5，但不隨機(jī)
 public int randomBase0() {
  Random r = new Random();
  return r.nextInt(2);
 }

用for循環(huán)10000萬次，得到的0和1大致相當(dāng)，可以得出獲得0和1的概率為0.5。但之后我就遇到了麻煩，我寫了一個(gè)方法去實(shí)現(xiàn)RANDOM(a, b)，例如RANDOM(0, 3)，得到的結(jié)果是：

0有8335個(gè)

1有825個(gè)

2有42個(gè)

3有798個(gè)

我的算法是

將b-a+1擴(kuò)展到2的最小冪級(jí)數(shù)，如果是個(gè)數(shù)為5，則取8（2^3），如果為16，則取16（2^4），然后用分治算法獲取a與b之間的數(shù)，其中需要將大于b的數(shù)去除掉，重新獲取。

我原本以為我寫RANDOM(a, b)的算法錯(cuò)了。后來又寫了一個(gè)算法，是網(wǎng)上很多人使用的算法，是將隨機(jī)產(chǎn)生的0和1拼成2進(jìn)制數(shù)，然后轉(zhuǎn)換為十進(jìn)制數(shù)，在一個(gè)區(qū)間內(nèi)在有效，超過這個(gè)區(qū)間則排除重取。

用這個(gè)算法得到的結(jié)果與第一種算法結(jié)果相同。我只好把第二種算法的二進(jìn)制數(shù)打印出來查找原因，發(fā)現(xiàn)一個(gè)問題，就是0或1連續(xù)出現(xiàn)的概率要比0和1交叉出現(xiàn)的概率大，我想既然是隨機(jī)產(chǎn)生0和1，那這兩個(gè)生成的概率應(yīng)該相同才對(duì)。

因此我得出結(jié)論，使用Random.nextInt(0, 1)獲取隨機(jī)數(shù)的概率并不隨機(jī)，原因是其生成連續(xù)相同0或1的概率與生成交叉0和1的概率不等，并且前者大于后者，盡管單獨(dú)獲取0和1的個(gè)數(shù)比相當(dāng)，換句話說，用這種方法獲取0和1的事件不獨(dú)立。

驗(yàn)證如下

 //檢測(cè)Random.nextInt(2)，連續(xù)獲取兩位0和1隨機(jī)數(shù)
 public int randomBaseS() {
  String s = new String(new StringBuffer().append(getBoolean()).append(getBoolean()));
  
  if("00".equals(s)){
   return 0;
  }else if("01".equals(s)){
   return 1;
  }else if("10".equals(s)){
   return 2;
  }else{
   return 3;
  }
 }
 //獲取隨機(jī)數(shù)二進(jìn)制字符串
 public String getBoolean(){
  return new String(new Integer(randomBase0()).toString());
 }

使用for循環(huán)10000次，得到的計(jì)數(shù)結(jié)果如下：

"00"有4145個(gè)

"01"有928個(gè)

"10"有905個(gè)

"11"有4022個(gè)

那哪種算法能滿足要求呢？如下：

 //用Math.random()獲取0,1隨機(jī)數(shù)
 //獲取概率均為0.5，且隨機(jī)
 public int randomBase() {
  return Math.random()>0.5?1:0;
 }

以上面的方法為基礎(chǔ)，用for循環(huán)獲取[0, 3]之間的整數(shù)，得到的結(jié)果如下：

0有2525個(gè)

1有2551個(gè)

2有2433個(gè)

3有2491個(gè)

滿足要求，哈哈！

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論