別名演算法 Alias Method

 題目

每個伺服器支援不同的 TPM (transaction per minute)

當 request 來的時候, 系統需要馬上根據 TPM 的能力隨機找到一個適合的 server.

雖然稱為 "隨機", 但還是需要有 TPM 作為權重.

解法

別名演算法（Alias Method）是一種有效率地進行加權隨機選擇的演算法，尤其適用於當元素的權重分布固定，且需要頻繁進行選擇的情況。這種演算法特別適合於情況如抽選伺服器或其他資源分配的任務中，因為它能在O(1)時間內完成選擇，使得運算效率極高。

別名演算法的核心概念：

1. 正規化與縮放：

首先，將每個元素（如伺服器）的TPM值（或任何其他量度）轉換為概率值，並根據元素總數進行縮放。例如，如果有三個伺服器，其TPM值分別為100、200和300，則總TPM為600。每個伺服器的概率值將被計算為其TPM除以總TPM，然後乘以元素總數（在這個例子中是3）。

2. 創建概率和別名表：

使用兩個陣列，一個存儲概率（probability），另一個存儲別名（alias）。概率陣列中的每個索引對應一個伺服器，值表示直接選擇該伺服器的概率。如果這個概率小於1，則需要一個別名來調整概率使之平衡。

利用兩個臨時陣列，一個用於存儲概率小於1的索引（small），另一個用於存儲概率大於1的索引（large）。從large陣列中取元素來補充small陣列中的元素，直到所有元素的概率都調整到1。

3. 選擇過程：

在選擇過程中，首先隨機生成一個索引，然後檢查這個索引處的概率是否足以直接選擇。如果隨機數大於該概率值，則使用存儲在別名陣列中該索引處的值作為替代選擇。

實現的優勢：

別名演算法的主要優點是其選擇步驟的時間複雜度為O(1)，非常適合需要快速響應的應用場景。初始化過程雖然較為複雜，但只需要在數據更新或初始設定時執行一次，之後的每次選擇都極為迅速。

使用場景：

這種演算法適用於任何需要加權隨機選擇的場景，如網絡服務的負載平衡，廣告投放，遊戲中的隨機事件生成等場合，特別是當選擇操作的頻率遠高於權重更新的頻率時，別名演算法顯得尤為有用。

程式

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Server {
    String name;
    Long tpm;

    public Server(String name, Long tpm) {
        this.name = name;
        this.tpm = tpm;
    }
}

public class ServerSelector {
    private List servers;
    private Random random = new Random();
    private int[] alias;
    private double[] probability;

    public ServerSelector(List servers) {
        this.servers = servers;
        initializeAliasTable();
    }

    private void initializeAliasTable() {
        int n = servers.size();
        double[] normalizedProbabilities = new double[n];
        List small = new ArrayList<>();
        List large = new ArrayList<>();
        long totalTPM = servers.stream().mapToLong(server -> server.tpm).sum();

        // Normalize probabilities and scale them by the number of servers
        for (int i = 0; i < n; i++) {
            normalizedProbabilities[i] = (double) servers.get(i).tpm / totalTPM * n;
            if (normalizedProbabilities[i] < 1.0) {
                small.add(i);
            } else {
                large.add(i);
            }
        }

        probability = new double[n];
        alias = new int[n];

        // Balance small and large lists to create probability and alias arrays
        while (!small.isEmpty() && !large.isEmpty()) {
            int less = small.remove(small.size() - 1);
            int more = large.remove(large.size() - 1);

            probability[less] = normalizedProbabilities[less];
            alias[less] = more;

            normalizedProbabilities[more] += normalizedProbabilities[less] - 1.0;
            if (normalizedProbabilities[more] < 1.0) {
                small.add(more);
            } else if (normalizedProbabilities[more] > 1.0) {
                large.add(more);
            }
        }

        // Ensure all remaining probabilities are set to 1
        for (int index : large) {
            probability[index] = 1.0;
        }
        for (int index : small) {
            probability[index] = 1.0;
        }
    }

    public Server selectServer() {
        int index = random.nextInt(servers.size());
        boolean useAlias = random.nextDouble() > probability[index];
        return servers.get(useAlias ? alias[index] : index);
    }
}