快捷導(dǎo)航

Java權(quán)重隨機(jī)的實(shí)現(xiàn)方法

更新時(shí)間：2015年01月13日 09:28:56 投稿：shichen2014

這篇文章主要介紹了Java權(quán)重隨機(jī)的實(shí)現(xiàn)方法,實(shí)例分析了權(quán)重隨機(jī)算法的原理與完整實(shí)現(xiàn)方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了Java權(quán)重隨機(jī)的實(shí)現(xiàn)方法。分享給大家供大家參考。具體分析如下：

權(quán)重隨機(jī)在項(xiàng)目中經(jīng)常用到，所以我把它抽象到一個(gè)工具類中。

一般實(shí)現(xiàn)隨機(jī)權(quán)重有兩種方式：

1. 使用一個(gè)數(shù)組存放權(quán)重對(duì)應(yīng)的實(shí)際目標(biāo)，比如A的權(quán)重是2，B的權(quán)重是3，那么數(shù)組長(zhǎng)度為5，數(shù)組前兩個(gè)存放A，后三個(gè)存放B。

然后隨機(jī)一個(gè)[0-數(shù)據(jù)長(zhǎng)度)的數(shù)字，直接取數(shù)組對(duì)應(yīng)下標(biāo)的值就可以了。

優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，算法高效，實(shí)現(xiàn)簡(jiǎn)單

缺點(diǎn)：當(dāng)權(quán)重值比較大同時(shí)數(shù)據(jù)又比較多的時(shí)候，會(huì)浪費(fèi)內(nèi)存

2. 使用區(qū)間算法，從前到后依次疊加權(quán)重，然后隨機(jī)一個(gè)[1-權(quán)重和]的數(shù)字，再用隨機(jī)的權(quán)重依次減去每個(gè)元素的權(quán)重，當(dāng)?shù)谝粋€(gè)小于等于0的元素就是我們找元素

這里實(shí)現(xiàn)可以借用Arrays的binarySearch方法。

完整實(shí)例代碼點(diǎn)擊此處本站下載。

貼一下代碼：

WeightMeta.java：

復(fù)制代碼代碼如下:

/** 

 * 建議使用RandomUtil類創(chuàng)建RandomMeta對(duì)象 

 * @author wxf on 14-5-5. 

 */  

public class WeightMeta<T> {  

    private final Random ran = new Random();  

    private final T[] nodes;  

    private final int[] weights;  

    private final int maxW;  

    public WeightMeta(T[] nodes, int[] weights) {  

        this.nodes = nodes;  

        this.weights = weights;  

        this.maxW = weights[weights.length - 1];  

    }  

    /** 

     * 該方法返回權(quán)重隨機(jī)對(duì)象 

     * @return 

     */  

    public T random() {  

        int index = Arrays.binarySearch(weights, ran.nextInt(maxW) + 1);  

        if (index < 0) {  

            index = -1 - index;  

        }  

        return nodes[index];  

    }  

    public T random(int ranInt) {  

        if (ranInt > maxW) {  

            ranInt = maxW;  

        } else if(ranInt < 0){  

            ranInt = 1;  

        } else {  

            ranInt ++;  

        }  

        int index = Arrays.binarySearch(weights, ranInt);  

        if (index < 0) {  

            index = -1 - index;  

        }  

        return nodes[index];  

    }  

    @Override  

    public String toString() {  

        StringBuilder l1 = new StringBuilder();  

        StringBuilder l2 = new StringBuilder("[random]\t");  

        StringBuilder l3 = new StringBuilder("[node]\t\t");  

        l1.append(this.getClass().getName()).append(":").append(this.hashCode()).append(":\n").append("[index]\t\t");  

        for (int i = 0; i < weights.length; i++) {  

            l1.append(i).append("\t");  

            l2.append(weights[i]).append("\t");  

            l3.append(nodes[i]).append("\t");  

        }  

        l1.append("\n");  

        l2.append("\n");  

        l3.append("\n");  

        return l1.append(l2).append(l3).toString();  

    }  

}

RandomUtil.java：

復(fù)制代碼代碼如下:

/** 

 * 隨機(jī)工具類 

 * 

 * 使用權(quán)重的集合Map構(gòu)建隨機(jī)元數(shù)據(jù)對(duì)象 

 * 

 * 比如： 

 * 我們有3個(gè)url地址，他們的權(quán)重分別為1,2,3現(xiàn)在我們利用RandomUtil來根據(jù)權(quán)重隨機(jī)獲取url： 

 * 

 * <p><blockquote><pre> 

 * 

 * map.put(url1, 1); 

 * map.put(url2, 2); 

 * map.put(url3, 3); 

 * RandomMeta<String, Integer> md = RandomUtil.buildWeightMeta(map); 

 * String weightRandomUrl = md.random(); 

 * 

 * </pre></blockquote><p> 

 * 

 * @author wxf on 14-5-5. 

 */  

public class RandomUtil {  

    public static <T> WeightMeta<T> buildWeightMeta(final Map<T, Integer> weightMap) {  

        final int size = weightMap.size();  

        Object[] nodes = new Object[size];  

        int[] weights = new int[size];  

        int index = 0;  

        int weightAdder = 0;  

        for (Map.Entry<T, Integer> each : weightMap.entrySet()) {  

            nodes[index] = each.getKey();  

            weights[index++] = (weightAdder = weightAdder + each.getValue());  

        }  

        return new WeightMeta<T>((T[]) nodes, weights);  

    }  

}