隨機
本節,我們來討論隨機,隨機是計算機程序中一個非常常見的需求,比如說:
我們首先來介紹Java中對隨機的支持,同時介紹其實現原理,然後我們針對一些實際場景,包括洗牌、搶紅包、搖號、隨機高強度密碼、帶權重的隨機選擇等,討論如何應用隨機。
先來看如何使用最基本的隨機。
Math.random
Java中,對隨機最基本的支持是Math類中的靜態方法random,它生成一個0到1的隨機數,類型為double,包括0但不包括1,比如,隨機生成並輸出3個數:
for(int i=0;i<3;i++){ System.out.println(Math.random()); }
我的電腦上的一次運行,輸出為:
0.4784896133823269 0.03012515628333423 0.7921024363953197
每次運行,輸出都不一樣。
Math.random()是如何實現的呢?我們來看相關代碼:
private static Random randomNumberGenerator; private static synchronized Random initRNG() { Random rnd = randomNumberGenerator; return (rnd == null) ? (randomNumberGenerator = new Random()) : rnd; } public static double random() { Random rnd = randomNumberGenerator; if (rnd == null) rnd = initRNG(); return rnd.nextDouble(); }
內部它使用了一個Random類型的靜態變量randomNumberGenerator,調用random()就是調用該變量的nextDouble()方法,這個Random變量只有在第一次使用的時候才創建。
下面我們來看這個Random類,它位於包java.util下。
Random
基本用法
Random類提供了更為豐富的隨機方法,它的方法不是靜態方法,使用Random,先要創建一個Random實例,看個例子:
Random rnd = new Random(); System.out.println(rnd.nextInt()); System.out.println(rnd.nextInt(100));
我的電腦上的一次運行,輸出為:
-1516612608 23
nextInt()產生一個隨機的int,可能為正數,也可能為負數,nextInt(100)產生一個隨機int,范圍是0到100,包括0不包括100。
除了nextInt,還有一些別的方法。
隨機生成一個long
public long nextLong()
隨機生成一個boolean
public boolean nextBoolean()
產生隨機字節
public void nextBytes(byte[] bytes)
隨機產生的字節放入提供的byte數組bytes,字節個數就是bytes的長度。
產生隨機浮點數,從0到1,包括0不包括1
public float nextFloat() public double nextDouble()
設置種子
除了默認構造方法,Random類還有一個構造方法,可以接受一個long類型的種子參數:
public Random(long seed)
種子決定了隨機產生的序列,種子相同,產生的隨機數序列就是相同的。看個例子:
Random rnd = new Random(20160824); for(int i=0;i<5;i++){ System.out.print(rnd.nextInt(100)+" "); }
種子為20160824,產生5個0到100的隨機數,輸出為:
69 13 13 94 50
這個程序無論執行多少遍,在哪執行,輸出結果都是相同的。
除了在構造方法中指定種子,Random類還有一個setter實例方法:
synchronized public void setSeed(long seed)
其效果與在構造方法中指定種子是一樣的。
為什麼要指定種子呢?指定種子還是真正的隨機嗎?
指定種子是為了實現可重復的隨機。比如用於模擬測試程序中,模擬要求隨機,但測試要求可重復。在北京購車搖號程序中,種子也是指定的,後面我們還會介紹。
種子到底扮演了什麼角色呢?隨機到底是如何產生的呢?讓我們看下隨機的基本原理。
隨機的基本原理
Random產生的隨機數不是真正的隨機數,相反,它產生的隨機數一般稱之為偽隨機數,真正的隨機數比較難以產生,計算機程序中的隨機數一般都是偽隨機數。
偽隨機數都是基於一個種子數的,然後每需要一個隨機數,都是對當前種子進行一些數學運算,得到一個數,基於這個數得到需要的隨機數和新的種子。
數學運算是固定的,所以種子確定後,產生的隨機數序列就是確定的,確定的數字序列當然不是真正的隨機數,但種子不同,序列就不同,每個序列中數字的分布也都是比較隨機和均勻的,所以稱之為偽隨機數。
Random的默認構造方法中沒有傳遞種子,它會自動生成一個種子,這個種子數是一個真正的隨機數,代碼如下:
private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L); public Random() { this(seedUniquifier() ^ System.nanoTime()); } private static long seedUniquifier() { for (;;) { long current = seedUniquifier.get(); long next = current * 181783497276652981L; if (seedUniquifier.compareAndSet(current, next)) return next; } }
種子是seedUniquifier() 與System.nanoTime()按位異或的結果,System.nanoTime()返回一個更高精度(納秒)的當前時間,seedUniquifier()裡面的代碼涉及一些多線程相關的知識,我們後續章節再介紹,簡單的說,就是返回當前seedUniquifier(current)與一個常數181783497276652981L相乘的結果(next),然後,將seedUniquifier設置為next,使用循環和compareAndSet都是為了確保在多線程的環境下不會有兩次調用返回相同的值,保證隨機性。
有了種子數之後,其他數是怎麼生成的呢?我們來看一些代碼:
public int nextInt() { return next(32); } public long nextLong() { return ((long)(next(32)) << 32) + next(32); } public float nextFloat() { return next(24) / ((float)(1 << 24)); } public boolean nextBoolean() { return next(1) != 0; }
它們都調用了next(int bits),生成指定位數的隨機數,我們來看下它的代碼:
private static final long multiplier = 0x5DEECE66DL; private static final long addend = 0xBL; private static final long mask = (1L << 48) - 1; 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;
舊的種子(oldseed)乘以一個數(multiplier),加上一個數addend,然後取低48位作為結果(mask相與)。
為什麼采用這個方法?這個方法為什麼可以產生隨機數?這個方法的名稱叫線性同余隨機數生成器(linear congruential pseudorandom number generator),描述在《計算機程序設計藝術》一書中。隨機的理論是一個比較復雜的話題,超出了本文的范疇,我們就不討論了。
我們需要知道的基本原理是,隨機數基於一個種子,種子固定,隨機數序列就固定,默認構造方法中,種子是一個真正的隨機數。
理解了隨機的基本概念和原理,我們來看一些應用場景,從產生隨機密碼開始。
隨機密碼
在給用戶生成賬號時,經常需要給用戶生成一個默認隨機密碼,然後通過郵件或短信發給用戶,作為初次登錄使用。
我們假定密碼是6位數字,代碼很簡單,如下所示:
public static String randomPassword(){ char[] chars = new char[6]; Random rnd = new Random(); for(int i=0; i<6; i++){ chars[i] = (char)('0'+rnd.nextInt(10)); } return new String(chars); }
代碼很簡單,就不解釋了。如果要求是8位密碼,字符可能有大寫字母、小寫字母、數字和特殊符號組成,代碼可能為:
private static final String SPECIAL_CHARS = "!@#$%^&*_=+-/"; private static char nextChar(Random rnd){ switch(rnd.nextInt(4)){ case 0: return (char)('a'+rnd.nextInt(26)); case 1: return (char)('A'+rnd.nextInt(26)); case 2: return (char)('0'+rnd.nextInt(10)); default: return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length())); } } public static String randomPassword(){ char[] chars = new char[8]; Random rnd = new Random(); for(int i=0; i<8; i++){ chars[i] = nextChar(rnd); } return new String(chars); }
這個代碼,對每個字符,先隨機選類型,然後在給定類型中隨機選字符。在我的電腦上,一次的隨機運行結果是:
8Ctp2S4H
這個結果不含特殊字符,很多環境對密碼復雜度有要求,比如說,至少要含一個大寫字母、一個小寫字母、一個特殊符號、一個數字。以上的代碼滿足不了這個要求,怎麼滿足呢?一種可能的代碼是:
private static int nextIndex(char[] chars, Random rnd){ int index = rnd.nextInt(chars.length); while(chars[index]!=0){ index = rnd.nextInt(chars.length); } return index; } private static char nextSpecialChar(Random rnd){ return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length())); } private static char nextUpperlLetter(Random rnd){ return (char)('A'+rnd.nextInt(26)); } private static char nextLowerLetter(Random rnd){ return (char)('a'+rnd.nextInt(26)); } private static char nextNumLetter(Random rnd){ return (char)('0'+rnd.nextInt(10)); } public static String randomPassword(){ char[] chars = new char[8]; Random rnd = new Random(); chars[nextIndex(chars, rnd)] = nextSpecialChar(rnd); chars[nextIndex(chars, rnd)] = nextUpperlLetter(rnd); chars[nextIndex(chars, rnd)] = nextLowerLetter(rnd); chars[nextIndex(chars, rnd)] = nextNumLetter(rnd); for(int i=0; i<8; i++){ if(chars[i]==0){ chars[i] = nextChar(rnd); } } return new String(chars); }
nextIndex隨機生成一個未賦值的位置,程序先隨機生成四個不同類型的字符,放到隨機位置上,然後給未賦值的其他位置隨機生成字符。
洗牌
一種常見的隨機場景是洗牌,就是將一個數組或序列隨機重新排列,我們以一個整數數組為例來看,怎麼隨機重排呢?我們直接看代碼:
private static void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void shuffle(int[] arr){ Random rnd = new Random(); for(int i=arr.length; i>1; i--) { swap(arr, i-1, rnd.nextInt(i)); } }
shuffle這個方法就能將參數數組arr隨機重排,來看使用它的代碼:
int[] arr = new int[13]; for(int i=0; i<arr.length; i++){ arr[i] = i; } shuffle(arr); System.out.println(Arrays.toString(arr));
調用shuffle前,arr是排好序的,調用後,一次調用的輸出為:
[3, 8, 11, 10, 7, 9, 4, 1, 6, 12, 5, 0, 2]
已經隨機重新排序了。
shuffle的基本思路是什麼呢?從後往前,逐個給每個數組位置重新賦值,值是從剩下的元素中隨機挑選的。在如下關鍵語句中,
swap(arr, i-1, rnd.nextInt(i));
i-1表示當前要賦值的位置,rnd.nextInt(i)表示從剩下的元素中隨機挑選。
帶權重的隨機選擇
實際場景中,經常要從多個選項中隨機選擇一個,不過,不同選項經常有不同的權重。
比如說,給用戶隨機獎勵,三種面額,1元、5元和10元,權重分別為70, 20和10。這個怎麼實現呢?
實現的基本思路是,使用概率中的累計概率分布。
以上面的例子來說,計算每個選項的累計概率值,首先計算總的權重,這裡正好是100,每個選項的概率是70%,20%和10%,累計概率則分別是70%,90%和100%。
有了累計概率,則隨機選擇的過程是,使用nextDouble()生成一個0到1的隨機數,然後使用二分查找,看其落入那個區間,如果小於等於70%則選擇第一個選項,70%和90%之間選第二個,90%以上選第三個,如下圖示所示:
下面來看代碼,我們使用一個類Pair表示選項和權重,代碼為:
class Pair { Object item; int weight; public Pair(Object item, int weight){ this.item = item; this.weight = weight; } public Object getItem() { return item; } public int getWeight() { return weight; } }
我們使用一個類WeightRandom表示帶權重的選擇,代碼為:
public class WeightRandom { private Pair[] options; private double[] cumulativeProbabilities; private Random rnd; public WeightRandom(Pair[] options){ this.options = options; this.rnd = new Random(); prepare(); } private void prepare(){ int weights = 0; for(Pair pair : options){ weights += pair.getWeight(); } cumulativeProbabilities = new double[options.length]; int sum = 0; for (int i = 0; i<options.length; i++) { sum += options[i].getWeight(); cumulativeProbabilities[i] = sum / (double)weights; } } public Object nextItem(){ double randomValue = rnd.nextDouble(); int index = Arrays.binarySearch(cumulativeProbabilities, randomValue); if (index < 0) { index = -index-1; } return options[index].getItem(); } }
其中,prepare方法計算每個選項的累計概率,保存在數組cumulativeProbabilities中,nextItem()根據權重隨機選擇一個,具體就是,首先生成一個0到1的數,然後使用二分查找,以前介紹過,如果沒找到,返回結果是-(插入點)-1,所以-index-1就是插入點,插入點的位置就對應選項的索引。
回到上面的例子,隨機選擇10次,代碼為:
Pair[] options = new Pair[]{ new Pair("1元",7), new Pair("2元", 2), new Pair("10元", 1) }; WeightRandom rnd = new WeightRandom(options); for(int i=0; i<10; i++){ System.out.print(rnd.nextItem()+" "); }
在一次運行中,輸出正好符合預期,具體為:
1元 1元 1元 2元 1元 10元 1元 2元 1元 1元
不過,需要說明的,由於隨機,每次執行結果比例不一定正好相等。
搶紅包算法
我們都知道,微信可以搶紅包,紅包有一個總金額和總數量,領的時候隨機分配金額,金額是怎麼隨機分配的呢?微信具體是怎麼做的,我們並不能確切的知道,根據一些公開資料,思路可能如下。
維護一個剩余總金額和總數量,分配時,如果數量等於1,直接返回總金額,如果大於1,則計算平均值,並設定隨機最大值為平均值的兩倍,然後取一個隨機值,如果隨機值小於0.01,則為0.01,這個隨機值就是下一個的紅包金額。
我們來看代碼,為計算方便,金額我們用整數表示,以分為單位。
public class RandomRedPacket { private int leftMoney; private int leftNum; private Random rnd; public RandomRedPacket(int total, int num){ this.leftMoney = total; this.leftNum = num; this.rnd = new Random(); } public synchronized int nextMoney(){ if(this.leftNum<=0){ throw new IllegalStateException("搶光了"); } if(this.leftNum==1){ return this.leftMoney; } double max = this.leftMoney/this.leftNum*2d; int money = (int)(rnd.nextDouble()*max); money = Math.max(1, money); this.leftMoney -= money; this.leftNum --; return money; } }
代碼比較簡單,就不解釋了。我們來看一個使用的例子,總金額為10元,10個紅包,代碼如下:
RandomRedPacket redPacket = new RandomRedPacket(1000, 10); for(int i=0; i<10; i++){ System.out.print(redPacket.nextMoney()+" "); }
一次輸出為:
136 48 90 151 36 178 92 18 122 129
如果是這個算法,那先搶好,還是後搶好呢?先搶肯定搶不到特別大的,不過,後搶也不一定會,這要看前面搶的金額,剩下的多就有可能搶到大的,剩下的少就不可能有大的。
北京購車搖號算法
我們來看下影響很多人的北京購車搖號,它的算法是怎樣的呢?根據公開資料,它的算法大概是這樣的。
編號是事先確定的,種子數是當場公證隨機生成的,公開的,隨機算法是公開透明的,任何人都可以根據公開的種子數和編號驗證中簽的編號。
一些說明
需要說明的是,Random類是線程安全的,也就是說,多個線程可以同時使用一個Random實例對象,不過,如果並發性很高,會產生競爭,這時,可以考慮使用多線程庫中的ThreadLocalRandom類。
另外,Java類庫中還有一個隨機類SecureRandom,以產生安全性更高、隨機性更強的隨機數,用於安全加密等領域。
這兩個類本文就不介紹了。
小結
本節介紹了隨機,介紹了Java中對隨機的支持Math.random()以及Random類,介紹了其使用和實現原理,同時,我們介紹了隨機的一些應用場景,包括隨機密碼、洗牌、帶權重的隨機選擇、微信搶紅包和北京購車搖號。
至此,關於一些基本常用類的介紹,我們就告一段落了,回顧一下,我們深入剖析了各種包裝類、String、StringBuilder、Arrays、日期和時間、Joda-Time以及隨機,這些都是日常程序中經常用到的功能。
之前章節中,我們經常提到泛型這一概念,是時候具體討論一下了。
----------------
未完待續,查看最新文章,敬請關注微信公眾號“老馬說編程”(掃描下方二維碼),從入門到高級,深入淺出,老馬和你一起探索Java編程及計算機技術的本質。用心寫作,原創文章,保留所有版權。