重み付きランダム抽出の実装

# 目的
* 重み付きの復元抽出・非復元抽出はほとんど実装例があまりなかったため、実装してみました。


# 出来ること・出来ないこと
## 出来ること
* 標本抽出の要素は総称型で、どんな要素でもWelcome
* 非復元・復元抽出のいずれにも対応

## 出来ないこと
* 今の実装では重みは小数第三位までしか対応していない。
    * 改良したとしても、重みの粒度を細かくするとパフォーマンスが低下する。

# 実装
## 母集団を表すクラス（Population.java）
```java:Population.java
public class Population<T> {
	private final ArrayList<T> population;
	private final Random rand = new Random();
	private static final BigDecimal ORDER_SHIFT = new BigDecimal(1000);

	private Population(ArrayList<T> population) {
		this.population = population;
	}

	public static <T> Population<T> of(Map<T, BigDecimal> pattern) {
		ArrayList<T> population = new ArrayList<>(1000);
		for(Map.Entry<T, BigDecimal> entry : pattern.entrySet()){
			for(int i = 0, j = entry.getValue().multiply(ORDER_SHIFT).intValueExact(); i < j; i++) {
				population.add(entry.getKey());
			}
		}

		Collections.shuffle(population);

		return new Population<T>(population);
	}

	// 非復元抽出
	public T samplingWithoutReplacement() {
		int index = rand.nextInt(population.size());
		T sample = population.get(index);
		population.removeAll(Collections.singleton(sample));
		/*
		 * 同義ですが、パフォーマンスが劣化したため不採用としました。
		 * （毎回ラムダ式を生成しているため当然か。。。）
		 * population.removeIf(element -> sample.equals(element))
		 */
		return sample;
	}

	// 復元抽出
	public T samplingWithReplacement() {
		int index = rand.nextInt(population.size());
		T sample = population.get(index);
		return sample;
	}
}
```

## 呼び出し側（Population.java）
```java:PopulationMain.java
public class PopulationMain {
	public static void main(String[] args) {
		Map<String, BigDecimal> pattern = new HashMap<String, BigDecimal>() {
			{
				put("A", new BigDecimal("0.300"));
				put("B", new BigDecimal("0.200"));
				put("C", new BigDecimal("0.100"));
				put("D", new BigDecimal("0.100"));
				put("E", new BigDecimal("0.100"));
				put("F", new BigDecimal("0.050"));
				put("G", new BigDecimal("0.050"));
				put("H", new BigDecimal("0.050"));
				put("I", new BigDecimal("0.050"));
			}
		};

		long start = System.currentTimeMillis();
		Population<String> population = Population.of(pattern);

		List<String> list1 = new ArrayList<>();
		for (int i = 0; i < 1000000; i++) {
			list1.add(population.samplingWithReplacement());
		}
		list1.stream()
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()))
				.forEach((k, v) -> System.out.println(k + ":" + v));

		List<String> list2 = new ArrayList<>();
		for (int i = 0; i < 100000; i++) {
			Population<String> tmpPopulation = Population.of(pattern);
			list2.add(tmpPopulation.samplingWithoutReplacement());
		}
		list2.stream()
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()))
				.forEach((k, v) -> System.out.println(k + ":" + v));

	}
}
```

# 実行結果
## 復元抽出
100万回のサンプリングを行いました。

| 標本 | 重み | 抽出数 |
|:-:|:-:|:-:|
| A | 0.300 | 299645 |
| B | 0.200 | 200083 |
| C | 0.100 | 100023 |
| D | 0.100 | 100277 |
| E | 0.100 | 99930 |
| F | 0.050 | 49842 |
| G | 0.050 | 50015 |
| H | 0.050 | 49981 |
| I | 0.050 | 50204 |

## 非復元抽出
ここまで書いておいてなんですが、非復元抽出を証明することって出来ますでしょうか。。。

# 所感
* 非復元抽出の証明こそ出来ていませんが、実現は出来ているはず。。。？
* 愚直な実装ですが、案外パフォーマンスも悪くなく、実用に堪えそうです。
* 母集団を表すコレクションはArrayListやLinkedList、EclipseCollectionsのFastListを試しましたが、ArrayListが一番高速でした。