輪盤算法的小改進

網上看到很多用輪盤算法，都是采用的如下圖的模式，

1.随機出N個個體的值，

2.周遊統計sum

3.double類型存儲單個機率。

4.合計機率。

但個人覺得其實完全沒必要這麼計算，一方面double類型的轉換要花時間，另一方面多次周遊感覺不大好。

故試作了另一種輪盤算法，思路是取消機率分算，直接用sum值來對比。

對比了一下兩種計算，新算法快了幾十倍，有興趣的可以驗證一下，下面是運作截圖與測試代碼。

import java.util.Arrays;

public class RotaryDemo {
	public static void main(String[] args) {
		select1();
		System.out.println();
		select2();
	}

	/**
	 * 第一種算法，對應累計機率确定選擇是哪個，由于機率大的擁有數值大，故被選擇機率大
	 */
	private static void select1() {
		long t1 = System.nanoTime();
		int arr[] = new int[10];// 單個數值
		double p[] = new double[10];// 計算機率
		double p_sum[] = new double[10];// 累計機率，對應輪盤值
		int sum = 0;
		for (int i = 0; i < 10; i++) {
			arr[i] = (int) (Math.random() * 100);
			sum += arr[i];
		}
		p[0] = 1.0 * arr[0] / sum;
		p_sum[0] = p[0];
		for (int i = 1; i < arr.length; i++) {
			p[i] = 1.0 * arr[i] / sum;
			p_sum[i] = p_sum[i - 1] + p[i];
		}
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(p));
		System.out.println(Arrays.toString(p_sum));
		double r = Math.random();
		for (int i = 0; i < p_sum.length; i++) {
			if (p_sum[i] > r) {
				t1 = System.nanoTime() - t1;
				System.out.println("選中第" + i + "個，機率為" + p_sum[i] + "，抽獎随機機率為：" + r + "費時：" + t1);
				break;
			}
		}
	}

	/**
	 * 第二種算法，不算機率，隻求合計，得出累計值
	 */
	private static void select2() {
		long t1 = System.nanoTime();
		int arr[] = new int[10];// 單個數值
		int p_sum[] = new int[10];
		int sum = 0;
		for (int i = 0; i < 10; i++) {
			arr[i] = (int) (Math.random() * 100);
			if (i == 0) {
				p_sum[i] = arr[i];
			} else {
				p_sum[i] = p_sum[i - 1] + arr[i];
			}
			sum += arr[i];
		}
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(p_sum));
		double r = Math.random();
		int m = (int) (r * sum);
		for (int i = 0; i < p_sum.length; i++) {
			if (p_sum[i] > m) {
				t1 = System.nanoTime() - t1;
				System.out.println("選中：" + i + "個，機率為" + (arr[i] * 1.0 / sum) + "，抽獎随機機率為：" + r + "費時：" + t1);
				break;
			}
		}
	}