Alias Method: 가중치 랜덤 선택을 전처리 O(n), 추출 O(1)로 바꾸기

column = uniformInteger(0, n)
coin   = uniformDouble(0, 1)
 
if coin < probability[column]
    return column
else
    return alias[column]

scaled[0] = 1 / 6 * 3 = 0.5
scaled[1] = 3 / 6 * 3 = 1.5
scaled[2] = 2 / 6 * 3 = 1.0

small = [0]
large = [1]
완성   = [2]

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.random.RandomGenerator;
 
public final class AliasTable {
    private final double[] probability;
    private final int[] alias;
 
    public AliasTable(double[] weights) {
        validate(weights);
 
        int size = weights.length;
        probability = new double[size];
        alias = new int[size];
 
        double sum = Arrays.stream(weights).sum();
        double[] scaled = Arrays.stream(weights)
            .map(weight -> weight / sum * size)
            .toArray();
 
        Deque<Integer> small = new ArrayDeque<>();
        Deque<Integer> large = new ArrayDeque<>();
 
        for (int i = 0; i < size; i++) {
            if (scaled[i] < 1.0) {
                small.add(i);
            } else {
                large.add(i);
            }
        }
 
        while (!small.isEmpty() && !large.isEmpty()) {
            int less = small.removeLast();
            int more = large.removeLast();
 
            probability[less] = scaled[less];
            alias[less] = more;
            scaled[more] = scaled[more] + scaled[less] - 1.0;
 
            if (scaled[more] < 1.0) {
                small.add(more);
            } else {
                large.add(more);
            }
        }
 
        while (!small.isEmpty()) {
            probability[small.removeLast()] = 1.0;
        }
        while (!large.isEmpty()) {
            probability[large.removeLast()] = 1.0;
        }
    }
 
    private static void validate(double[] weights) {
        if (weights == null || weights.length == 0) {
            throw new IllegalArgumentException("weights must not be empty");
        }
 
        double sum = 0.0;
        for (double weight : weights) {
            if (!Double.isFinite(weight) || weight < 0.0) {
                throw new IllegalArgumentException("weights must be finite and non-negative");
            }
            sum += weight;
        }
        if (!Double.isFinite(sum) || sum <= 0.0) {
            throw new IllegalArgumentException("weight sum must be finite and positive");
        }
    }
 
    public int sample(RandomGenerator random) {
        int column = random.nextInt(probability.length);
        return random.nextDouble() < probability[column]
            ? column
            : alias[column];
    }
}