TODO
  • Inicializace:
    • vytvoř pole Alias a Prob o velikosti n
    • vytvoř dva seznamy Small a Large
    • vynásob každou pravděpodobnost n
    • pro každou tuto vynásobenou pravděpodobnost p:
      • pokud je pravděpodobnost p(i) menší než 1, vlož prvek na indexu i do seznamu Small, jinak do seznamu Large
    • dokud nejsou oba seznamy prázdné:
      • vyber první prvek ze seznamu Small a označ jej jako s
      • vyber první prvek ze seznamu Large a označ jej jako g
      • nastav Prob[s]=p(s)
      • nastav Alias[s]=g
      • nastav p(g)=p(g)+p(s)-1 (trik pro dosažení lepší numerické stability)
      • pokud p(g) je menší než 1, přidej g do seznamu Small, jinak do seznamu Large
    • dokud není seznam Large prázdný:
      • vyber první prvek ze seznamu Large a označ jej jako g
      • nastav Prob[g]=1
    • dokud není seznam Small prázdný:
      • vyber první prvek ze seznamu Small a označ jej jako s
      • nastav Prob[s]=1
  • Generování náhodného čísla:
    • vyber náhodný řádek i v rabulce Prob
    • vygeneruj náhodné číslo r v rozsahu 0-1
    • pokud je číslo r menší než pravděpodobnost na řádku Prob[i], vrať i, jinak Alias[i]
package random;

/**
 * @see http://www.keithschwarz.com/darts-dice-coins/
 */
public class WalkerVoseAliasSelection {
    private int n;
    private double[] probabilities;
    private int[] alias;

    public void initialize(double[] weights) {
        n = weights.length;
        probabilities = new double[n];
        alias = new int[n];

        final double[] P = new double[n];
        final int[] smallIndices = new int[n];
        final int[] largeIndices = new int[n];

        // normalize probabilities

        double totalWeight = 0;
        for (final double weight : weights) {
            totalWeight += weight;
        }
        for (int i = 0; i < n; i++) {
            P[i] = weights[i] * n / totalWeight;
        }

        int numSmall = 0;
        int numLarge = 0;

        for (int i = n - 1; i >= 0; i--) {
            if (P[i] < 1) {
                smallIndices[numSmall++] = i;
            } else {
                largeIndices[numLarge++] = i;
            }
        }

        while (numSmall > 0 && numLarge > 0) {
            final int a = smallIndices[--numSmall];
            final int g = largeIndices[--numLarge];
            probabilities[a] = P[a];
            alias[a] = g;
            P[g] = P[g] + P[a] - 1;
            if (P[g] < 1) {
                smallIndices[numSmall++] = g;
            } else {
                largeIndices[numLarge++] = g;
            }
        }

        while (numLarge > 0) {
            probabilities[largeIndices[--numLarge]] = 1;
        }
        while (numSmall > 0) {
            probabilities[smallIndices[--numSmall]] = 1;
        }
    }

    public int sample() {
        if (probabilities.length == 0) {
            return -1;
        }
        final int col = (int) (Math.random() * n);
        if (Math.random() < probabilities[col]) {
            return col;
        } else {
            return alias[col];
        }
    }
}

Zdrojový kód Pokrytí testy

Reference