Java implementation by weight random number

I. problem definition:

Q: there is an array, the values in these arrays have their own weight, how to design to effectively prioritize the weight of the high number??

Such as:

 The weight : 8  2  11  79

 The value returned by the weight : 0  1  2   3

Ii. Analysis of problems:

Idea 1: create an array array size for the weight and the size, such as the weight of value 0 is 8, then put 8 0 values, the weight of value 1 is 2, then put 2 1 values, and so on.
Then use a random number with a weight and size, generate a random number, you can. The disadvantage is that it takes up too much memory.

Idea 2:

The weights and the array w[I] store the weights and & NBSP of all the elements of the [0, I] element. Time complexity O(n) space complexity O(n)
Random [0,W[399]] to see which Wi the random number falls in, choose which   Time complexity O(longn)
So the total time complexity time complexity O(n) space complexity O(n)

Pseudo code:

Roulette is not a particularly good selection operator, but it is easy to implement.
First of all, it is important to understand that the crossover, mutation and other operators cannot control the direction of evolution, so the task of evolution falls on the selection operator.
If we understand this, we can do it easily.

Roulette, is the accumulation of probability to achieve, usually the fitness of the higher the probability of being selected.
If :fit is the fitness array, a total of m

for i=1 to m ' First sum 

sum=sum+fit(i)

next i

For i = 1 To n  ' n- How many individuals are going to be generated 

temp = temp + fit(i)

If rnd <= temp / sum Then

    The output  i  Is the result 

Exit Function

End If

Next i

Iii. Problem solving:

package datastruct;  

  

import java.util.HashMap;  

import java.util.Map;  

  

/** 

 Random number of weight:  

 Such as                The weight :8  2  11  79 

         The value returned by the weight :0  1  2   3 

@author ajian005 79331356@qq.com 

2014-2-16 21:12 

 Output results: {2.0=184128, 11.0=348551, 79.0=1308100, 8.0=159221} 

*/  

  

public class WeightRandomTest {  

    private static double[] weightArrays = {8.0,2.0,11.0,79.0};  //The index of the array is the value to be returned. The value of the array is the weight of the index of the array. < br / >
    public static void main(String[] args) {  

        WeightRandom weightRandom = new WeightRandom();  

        Map<Double, Integer> stat = new HashMap<Double, Integer>();  

        for (int i = 0; i < 2000000; i++) {  

            int weightValue = weightRandom.getWeightRandom(weightArrays);  

            if (weightValue < 0) {  

                continue;  

            }  

            System.out.println(" Random number returned by weight: " + weightValue);  

            if (stat.get(weightArrays[weightValue]) == null) {  

                stat.put(weightArrays[weightValue], 1);  

            } else {  

                stat.put(weightArrays[weightValue], stat.get(weightArrays[weightValue])+1);  

            }  

        }  

        System.out.println(stat);  

    }  

}  

  

class WeightRandom {  

    java.util.Random r = new java.util.Random();  

    private double weightArraySum(double [] weightArrays) {  

        double weightSum = 0;  

        for (double weightValue : weightArrays) {  

            weightSum += weightValue;  

        }  

        return weightSum;  

    }  

    public int getWeightRandom(double [] weightArrays) {  

        double weightSum = weightArraySum(weightArrays);  

        double stepWeightSum = 0;  

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

            stepWeightSum += weightArrays[i];  

            if (Math.random() <= stepWeightSum/weightSum) {  

                //System.out.println(i);  

                return i;  

            }  

        }  

        System.out.println(" Out of the mistake ");  

        return -1;  

    }     

}  

Iv. Summary

Russian roulette is all about accumulating probabilities

According to the weight of load scheduling