程式扎記: [ Java 文章收集 ] Java 產生不重覆亂數

標籤

2012年11月26日 星期一

[ Java 文章收集 ] Java 產生不重覆亂數

來源自 這裡 
Preface: 
這邊要產生不重覆亂數的方法,下面是三種方式,只要是暴力法都很慢,速度是O(n^2). Java要產生亂數很簡單,只要呼叫 Random 類別就可以了,不過如果想要不重覆的亂數,有一些小方法可以用,這裡提供三種方法. 

暴力比對法: 
這個 GenerateDuplicateRan 方法會接收一個整數,表示你要取得亂數的範圍,丟進去100表示你要取0~99之間的亂數: 
  1. public static int[] GenerateNonDuplicateRan1(int range)  
  2. {  
  3.     Random rand = new Random();  
  4.     int rdm[] = new int[range];  
  5.     List holeList = new ArrayList();  
  6.     for(int i=0; i
  7.       
  8.     for(int i=0; i
  9.     {  
  10.         int pv=-1;  
  11.         do{  
  12.             pv = (int)(rand.nextDouble()*range);                  
  13.         }while(!holeList.remove(Integer.valueOf(pv)));  
  14.         rdm[i] = pv;  
  15.     }  
  16.     return rdm;  
  17. }  
這個方法接收一個整數,表示你要取得亂數的最大範圍,呼叫 GenerateDuplicateRan(100) 則會回傳一個長度100的整數陣列,裡面就是0~99不重覆的整數。寫的方式很直覺,第一個for loop跑100次,每塞一個值就會去比對之前在陣列中的數字,如果相同就移除。缺點就是要產生大量亂數的時候很慢,因為有兩層for loop,速度是n^2,如果只是要少量亂數的人可以參考. 

Collection移出法: 
第二種方法就快多了,尤其在產生大量亂數的時候更為明顯。分成三個部分來解釋. 
1. 產生一個ArrayList,並且利用for loop塞值進去,你想要產生0~99的亂數,就丟100進去,他就會依序把0~99塞到ArrayList裡面. 
2. 用Collection的remove method,隨機的取index,並且移出,直到 ArrayList 的size = 0。因為本來在ArrayList裡面的數字就沒有重複(用for loop塞的),所以隨機取出的值也不會重複! 
3. 最後一個部份就是去呼叫上面的方法並且宣告一個array來接收上面產生的亂數 
函數 GenerateNonDuplicateRan2 代碼如下: 
  1. public static int[] GenerateNonDuplicateRan2(int range)  
  2. {  
  3.     Random rand = new Random();  
  4.     int rdm[] = new int[range];  
  5.     List holeList = new ArrayList();  
  6.     for(int i=0; i
  7.     int cnt=0;  
  8.     while(holeList.size()>0)  
  9.     {  
  10.         int pv = holeList.remove(rand.nextInt(holeList.size()));  
  11.         rdm[cnt++] = pv;  
  12.     }  
  13.     return rdm;  
  14. }  
HashSet 的暴力比較法: 
另一種方式是使用 HashSet unique element 的特性, 每次產生一個 random 的整數去比對 HashSet 是否已經看過, 否則就從新產生一個 random 的整數; 如果沒看過, 便將該整數加到 HashSet 與 返回的 整數陣列中: 
  1. public static int[] GenerateNonDuplicateRan3(int range)  
  2. {  
  3.     int rdm[] = new int[range];  
  4.     Random rand = new Random();  
  5.     HashSet set = new HashSet();  
  6.     for(int i=0; i
  7.     {  
  8.         int pv = -1;  
  9.         do  
  10.         {  
  11.             pv = rand.nextInt(range);  
  12.         }while(!set.add(pv));  
  13.         rdm[i] = pv;  
  14.     }  
  15.     return rdm;  
  16. }  
測試代碼: 
底下是三種方法的使用代碼: 
  1. public static void main(String args[])  
  2. {  
  3.     int range = 1000;  
  4.     long st = System.currentTimeMillis();  
  5.     int[] rdm = Rdm.GenerateNonDuplicateRan1(range);  
  6.     System.out.printf("\t[Info] GenerateNonDuplicateRan1 with Range=%d:\n", range);  
  7.     long ut = System.currentTimeMillis()-st;  
  8.     for(int i:rdm) System.out.printf("%d ", i);  
  9.     System.out.println();  
  10.     System.out.printf("\t[Info] Spending time=%d ms(%d)!\n\n", ut, rdm.length);  
  11.       
  12.     st = System.currentTimeMillis();  
  13.     rdm = Rdm.GenerateNonDuplicateRan2(range);  
  14.     System.out.printf("\t[Info] GenerateNonDuplicateRan2 with Range=%d:\n", range);  
  15.     ut = System.currentTimeMillis()-st;  
  16.     for(int i:rdm) System.out.printf("%d ", i);  
  17.     System.out.println();  
  18.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
  19.       
  20.     st = System.currentTimeMillis();  
  21.     rdm = Rdm.GenerateNonDuplicateRan3(range);  
  22.     System.out.printf("\t[Info] GenerateNonDuplicateRan3 with Range=%d:\n", range);  
  23.     ut = System.currentTimeMillis()-st;  
  24.     for(int i:rdm) System.out.printf("%d ", i);  
  25.     System.out.println();  
  26.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
  27.       
  28. }  
執行結果如下: 
[Info] GenerateNonDuplicateRan1 with Range=1000:
864 435 238 ...
[Info] Spending time=38 ms(1000)!

[Info] GenerateNonDuplicateRan2 with Range=1000:
406 821 595 ...
[Info] Spending time=
1 ms!(1000)

[Info] GenerateNonDuplicateRan3 with Range=1000:
152 959 751 ...
[Info] Spending time=5 ms!(1000)

可以看的出來第二種方法最快!

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!