作者zanyking (遙遠的旅人)
看板java
標題[討論] 一個作弊用的骰子(最終版)
時間Mon Apr 10 13:46:33 2006
上次那個問題的物件導向版。
支援大數(long)運算。
實做執行期修改權值。updateWeight()方法。
有興趣的大大們玩玩吧。
____________________________<<程式碼>>____________________________________
package dice;
import java.util.Random;
import java.util.TreeMap;
/**
*
* @author IANTSAI <br>
* 系統：int 32 bits, long 64 bits <br>
* 多緒：這不是一個thread safe的物件，請小心。<br>
* 用途：一個可以作弊的骰子。<br>
* 修改.移植：可以的話，把weightArr、AWArr也換成不定型態，在其他語言，例如C++
、C#中可以考慮<br>
* 修改.移植.實做：weight、AccumulateWeight必須實做 operator(+,+=,-,-=,>,<)
* 修改.移植.建議：weight extends int ,AccumulateWeight extends long
* @param <T>
*/
public class WeightRandom<T>
{
/**
*
* @param args
*/
public static void main(String[] args)
{
String[] valueArr = new String[]{"1點","2點","3點","4點","5點","6點"};
int[] weightArr = new int[]{100,100,100,100,100,10000};
WeightRandom<String> cheatDice = new WeightRandom<String>();
cheatDice.init(valueArr,weightArr);
doTest(cheatDice);
cheatDice.updateWeight(5,100);
doTest(cheatDice);
}
public static void doTest(WeightRandom<String> cheatDice)
{
int loop = 1000000;
TreeMap<String,Integer> map = new TreeMap<String,Integer>();
long start = System.currentTimeMillis();
for(int i=0;i<loop;i++)
{
String diceValue = cheatDice.randValue();
if(map.containsKey(diceValue))
map.put(diceValue,map.get(diceValue)+1);
else map.put(diceValue,1);
}
long end = System.currentTimeMillis();
for(String ent : map.keySet())
System.out.println(ent+" : "+map.get(ent)+" 次");
System.out.println();
System.out.println("總共骰了 "+loop+" 次");
System.out.println("花費時間: "+(float)(end-start)/1000+" 秒.");
}
private T[] valueArr;
private int[] weightArr;
private long[] AWArr;
/**
* 初始化 值陣(valueArr) 與 權陣(weightArr)
* @param _valueArr 值陣 不可為null, 必須與weightArr等長
* @param _weightArr 權陣 不可為null, 必須與valueArr等長, 元素不可為負數 ,
* 所有元素的總和不可 == 0
*/
public void init(T[]_valueArr,int[]_weightArr)
{
if(_valueArr==null||_weightArr==null||
_valueArr.length!=_weightArr.length)
throw new IllegalArgumentException("different arg length!!!");
this.valueArr = _valueArr;
this.weightArr = _weightArr;
this.AWArr = createAccumulateWeightArray(_weightArr);
}
/**
* 更新累進權陣
* @return
*/
public long[] createAccumulateWeightArray(int[] _weightArr)
{
int size = _weightArr.length;
long[] _AWArr = new long[size];
long temp=0;
for(int i=0;i<size;i++)
{
if(_weightArr[i] < 0)
throw new IllegalArgumentException("Weight can not < 0!!!");
temp+=_weightArr[i];
_AWArr[i]=temp;
}
if(temp == 0)
throw new IllegalArgumentException("weight Sigma is ZERO!!!");
return _AWArr;
}
/**
* 執行期更新權重矩陣參數，連帶更新AWArr
* @param index
* @param value
*/
public void updateWeight(int index, int value)
{
if(index < weightArr.length)
{
int def = value - this.weightArr[index];
this.weightArr[index] = value;
for(int i=index,j=AWArr.length;i<j;i++)
AWArr[i] += def;
}
else throw new IndexOutOfBoundsException("index="+index);
}
/**
* 依據權重，亂數回傳一個valueArr裡的元素。
* @return
*/
public T randValue()
{
//java api 裡沒找到(我懶)，所以自己做
long dice = RandUtil.nextLong(AWArr[AWArr.length-1])+1;
//自己作來玩的。
int index =
LeftAreaFinder.bineryLeftAreaSearch( dice,this.AWArr);
return valueArr[index];
}
}//end of class
/**
*
* @author IANTSAI
*判斷是否落在左區域範圍(右極限)內，如果Key大於最後一個右極限，回傳
-arr.length
*/
class LeftAreaFinder
{
private LeftAreaFinder(){}
/**
* 使用BinarySearch尋找是否落在左區域範圍(右極限)內<br>
* ，如果Key大於最後一個右極限，回傳 -arr.length
* @param key
* @return
*/
public static int bineryLeftAreaSearch(long key,long[]arr)
{
int low_of = 0;
int up_of = arr.length-1;
if(key>arr[up_of])return -arr.length;
while (low_of <= up_of)
{
int middle = (low_of + up_of) >> 1;
long midLeft = arr[middle];
if(key < midLeft) up_of = middle-1;
else if(key > midLeft)low_of = middle+1;
else return middle;
}
return low_of;
}
/**
* 使用sequenceSearch判斷是否落在左區域範圍(右極限)內，<br>
* 如果Key大於最後一個右極限，回傳 -arr.length
* @param key
* @return
*/
public static int sequenceLeftAreaSearch(long key,long[]arr)
{
for(int i=0,j=arr.length;i<j;i++)if(key < arr[i])return i;
return -arr.length;
}
}//end of class
/**
* 實做長整數的nexLong方法
* @author IANTSAI
*
*/
class RandUtil
{
private static final int INT32_MAX = 1 << 30;//int 的32位元系統極值
private RandUtil(){}
/**
* 亂數產生一個在(0~max-1)之間的long 值。
* @param max
* @return
*/
public static long nextLong(long max)
{
Random rand = new Random();
long randValue;
if(max < INT32_MAX)randValue = rand.nextInt((int)max);
else randValue = Math.abs(rand.nextLong()) % max;
return randValue;
}
}
________________________________<<程式碼結束>>_______________________________
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.248.27.110
※ 編輯: zanyking 來自: 60.248.27.110 (04/10 13:46)