Java는 가중치 기준 랜덤 수 구현

1. 문제 정의:
다음 수조가 있습니다. 이 수조의 값은 모두 자신의 무게가 있습니다. 어떻게 설계해야 효율적으로 무게가 높은 수를 우선적으로 추출할 수 있습니까?
예:

 : 8  2  11  79

 : 0  1  2   3

2. 문제 분석:
사고방식1: 수조의 수조 크기가 권중과 크기인 것을 만듭니다. 예를 들어 값 0의 권중은 8이고 8개의 0값을 넣으며 값 1의 권중은 2이고 2개의 1값을 넣고 순서대로 유추합니다.
그리고 권중과 크기의 랜덤 수로 랜덤 수를 만들면 됩니다.단점은 메모리를 너무 많이 차지해야 한다.
생각 2:
권중과 수조 w[i]는 [0, i] 원소의 모든 원소의 권중과 시간 복잡도 O(n) 공간 복잡도 O(n)를 저장한다
랜덤[0, W[399]] 랜덤 수가 어느 와이어에 있는지 보고 시간 복잡도 O(longn)
그래서 총 시간 복잡도 시간 복잡도 O (n) 공간 복잡도 O (n)
위조 코드:
룰렛은 결코 특별히 좋은 선택 산수는 아니지만, 실현하기 쉽다.
우선 교차, 변이 등 산자가 진화 방향을 통제할 수 없기 때문에 진화의 중임은 산자를 선택하는 데 있다는 것을 알아야 한다.
만약 이 점을 알았다면 처리하기 쉬웠을 것이다.
룰렛은 확률을 축적하여 실현하는 것으로 통상적으로 적응도가 큰 것은 선택될 확률이 비교적 높다.
가령:fit는 적응도 그룹으로 모두 m개

for i=1 to m ' 

sum=sum+fit(i)

next i

For i = 1 To n ‘n- 

temp = temp + fit(i)

If rnd <= temp / sum Then

     i  

Exit Function

End If

Next i

3. 문제 해결:

package datastruct;  

  

import java.util.HashMap;  

import java.util.Map;  

  

/** 

 ： 

                :8  2  11  79 

         :0  1  2   3 

@author ajian005 [email protected] 

2014-2-16 21:12 

 ：{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};  //  ，   

    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(" ：" + 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(" ");  

        return -1;  

    }     

}  

4. 요약:
러시아 룰렛은 확률을 쌓아서 하는 거예요.
권중 부하 스케줄링 등