Documentation
¶
Overview ¶
Package sampler 提供一系列高效能的加權抽樣演算法與工具。
本檔案 (weightitem.go) 定義了加權排序與抽樣所需的內部輔助結構。
設計目的：
- 提供一個輕量的容器，封裝原始索引 (Index) 與計算後的隨機分數 (Score)。
- 支援 WeightedShuffle 與 WeightedReservoirSample 中的排序與堆積操作。
結構說明：
- weightItem: 基本單元。
- weightHeap: 實作 heap.Interface 的 Max-Heap，用於K抽樣的動態維護。
注意：如果某個weights中某一個weight = 0 ，則在WeightedShuffle當中會被排到最後，但K抽樣則永不入選
Index ¶
- func Shuffle[T any](c *core.Core, src []T)
- func WeightedSample(c *core.Core, weights []int, k int) []int
- func WeightedShuffle(c *core.Core, weights []int) []int
- func WeightedShuffleWithFilter(c *core.Core, weights []int) []int
- type AliasTable
- type AliasTableF64
- type Floaters
- type Integers
- type LUT
- type Numbers
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Shuffle ¶
Shuffle 使用 Fisher-Yates (亦稱 Knuth Shuffle) 演算法 對泛型切片進行「就地 (In-place)」隨機重排。
演算法特性：
公平性 (Unbiased)： 此算法保證所有可能的 N! 種排列組合出現的機率是嚴格相等的 (1/N!)。 這解決了傳統 "Naive Shuffle" (每個位置都隨機跟任意位置交換) 導致的機率偏差問題。
效能 (High Performance)： - 時間複雜度：O(N)，只需要對陣列進行一次線性掃描。 - 空間複雜度：O(1)，直接在原記憶體位置交換，實現零配置 (Zero Allocation)。
使用場景：
適用於任何需要公平洗牌的邏輯，如撲克牌洗牌、滾輪符號隨機排列、抽獎池打亂等。
func WeightedSample ¶
WeightedSample 加權不放回抽樣 - 只取前 K 個 (Weighted Reservoir Sampling)
演算法：Efraimidis-Spirakis Algorithm A-Res
核心邏輯：
維護一個容量為 K 的「領獎台」(Reservoir)，裡面存放著目前分數最小的 K 個元素。 使用 Max-Heap 來實作這個領獎台，讓我們能以 O(1) 找到這 K 個人裡面「分數最大」(最該被淘汰) 的人。
處理流程：
- 遍歷所有元素，權重 < 0 Panic，權重 == 0 跳過。
- 維護一個大小不超過 K 的 Heap。
- 最終從 Heap 彈出結果。
相比 WeightedShuffle 的優勢：
- 空間複雜度僅為 O(K)：不需要分配 N 大小的記憶體，對 GC 極度友善 (當 N=10000, K=3 時差異巨大)。
- 時間複雜度為 O(N log K)：當 K << N 時，比全排序快得多。
適用場景：選取少量項目，且容易抽不到。
func WeightedShuffle ¶
WeightedShuffle 加權不放回抽樣 - 全排列 (Weighted Shuffle without Replacement)
演算法：Efraimidis-Spirakis Algorithm A-ExpJ 參考文獻：2006, "Weighted random sampling with a reservoir"
核心邏輯：
- 為每個元素 i 生成一個特徵分數 $k_i = U_i^(1/w_i)$。 為了數值穩定與效能，實作上使用 Log 轉換： $Score_i = -ln(U_i) / w_i$。 其中 $-ln(U_i)$ 即為標準指數分佈 (ExpFloat64)。
- 權重 $w_i$ 越大，分母越大，分數 $Score_i$ 越小。
- 將所有元素按 Score 由小到大排序。
- 排序後的順序即為加權隨機排列的結果。
特殊處理：
- 權重 < 0：Panic (視為錯誤)。
- 權重 == 0：分數設為 +Inf，這保證它們會被排在列表的最後面。
適用場景：
- 需要取得完整的隨機排列（如：洗牌、滾輪條生成）。
- 抽取的數量 K 接近總數 N。
複雜度：
- 時間：O(N log N) (瓶頸在排序)
- 空間：O(N) (需要存儲所有元素的分數)
func WeightedShuffleWithFilter ¶
WeightedShuffleWithFilter 加權不放回抽樣 - 全排列但過濾零權重
這是 WeightedShuffle 的變體，專門用於需要「排除無法選中項目」的場景。
行為差異：
- WeightedShuffle: 回傳長度 N，權重為 0 者排在最後。
- WeightedShuffleWithFilter: 回傳長度 M (M <= N)，僅包含權重 > 0 的項目。
適用場景：
- 抽樣結果不應包含無效項目（例如：只列出有中獎的獎項順序）。
Types ¶
type AliasTable ¶
type AliasTable struct {
Prob []int `json:"prob"`
Aliases []int `json:"aliases"`
Size int `json:"size"`
Total int `json:"total"`
}
AliasTable 是 Vose Alias Method 的一種 O(1) 加權抽樣結構，適用於從離散分布中快速抽樣。 此版本為「整數版本」，使用整數 scaling 來避免浮點數計算中的精度問題與誤差累積。
結構欄位說明： - Prob: 存放每個元素的「調整後機率」，整數形式，經過 scaling。 - Aliases: 別名索引，用於處理機率不足的元素，指向補足機率的元素。 - Size: 欄位數量，即元素數量。 - Total: 權重總和，用於 scaling 與抽樣判斷。
演算法原理：
- 將任意離散分佈轉換為均勻分佈的組合。
- 每個槽位 (Bucket) 只存放「自己」和「別名 (Alias)」兩個選項。
- 抽樣時先選槽位，再根據機率決定是自己還是別名。
特性：
- 建表時間：O(N)，線性時間。
- 抽樣時間：O(1)，穩定且高效。 *固定作2次IntN亂數*
- 空間複雜度：O(N)，與選項數量成正比，**與權重總和無關**。
適用場景：
- 權重總和非常大 (如 > 100,000) 或權重差異懸殊。
- 選項數量較多。
- 需要穩定的記憶體開銷 (不會因為企劃調整權重數值而暴增記憶體)。
實作細節：
- 採用全整數運算 (Integer Scaling)，避免浮點數精度誤差 (0.999... != 1.0)。
- 內建溢位檢查 (Safe Multiply)，確保在大數權重下安全運作。
func BuildAliasTable ¶
func BuildAliasTable(weights []int) *AliasTable
BuildAliasTable 根據輸入的權重(weights)建立 AliasTable。
輸入 weights 說明： - weights 為任意非負整數權重陣列，不需事先正規化。 - 權重可為零，但全部為零會 panic。
處理流程說明：
- 計算 total 為所有權重之和，若有負權重或 total == 0 則 panic。 - 檢查 weights 長度與 total 相乘是否會溢位，避免 int64 overflow。 - 使用兩個 bucket：small 與 large，分別存放 scaled 權重小於 total 及大於等於 total 的索引。 - 透過 small 與 large 兩桶交互調整 prob 與 aliases，完成 alias table 建立。
演算法流程條列： 1) 將每個權重 w 乘以 n（元素數量）做整數 scaling，得到 prob。 2) 分類索引到 small 或 large，依 prob[i] 與 total 比較。 3) 從 small 和 large 各取一個元素 s, l，將 l 指派為 s 的 alias，並調整 l 的 prob。 4) 重複直到 small 或 large 空。 5) 返回建好的 AliasTable 結構。
func (*AliasTable) Pick ¶
func (at *AliasTable) Pick(c *core.Core) int
Pick 從 AliasTable 中抽取一個索引，若表為空則回傳 -1。
抽樣步驟說明：
1) 使用 c.IntN(Size) 隨機選擇一個欄位 idx。
2) 使用 c.IntN(Total) 隨機投票，判斷是否直接選擇 idx，或使用其 alias。
3) 判斷條件為 IntN(Total) < Prob[idx]，此為整數版的機率比較。
數學推導簡述：
- Prob[idx] = weight[idx] * Size，為整數 scaling 後的機率值。
- 浮點版本為 U < p[idx]，U 為 [0,1) 均勻隨機數，p[idx] 為機率。
- 將 U 與 p[idx] 放大為整數比較，避免浮點誤差。
此方法完全用整數運算，不經過 float64 浮點計算，避免原演算法的誤差累積，確保抽樣正確性。
type AliasTableF64 ¶ added in v0.5.3
type AliasTableF64 struct {
Prob []float64 `json:"prob"`
Aliases []int `json:"aliases"`
Size int `json:"size"`
}
func BuildAliasTableF64 ¶ added in v0.5.3
func BuildAliasTableF64(weights []float64) *AliasTableF64
type Integers ¶
type Integers interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}
Integers 定義所有底層實現為整數型別的集合
type LUT ¶
type LUT []int
Look-Up Table (LUT) 加權抽樣
LUT 是「以空間換取時間」的加權抽樣： 建表時直接展開所有權重，抽樣時只做一次 IntN
LUT 的時間/空間特性：
建表時間 O(sum(weights))，抽樣 O(1)。
記憶體消耗與權重總和成正比，sum(weights) 很大時不建議使用。
構建函數: BuildLookUpTable(src []Integers) LUT
舉例 :
三個物品，對應權重分別為[3,5,0]
i.e. 權重總和為 8
抽到第一個物品(idx = 0)的機率為 3/8 抽到第二個物品的機率為 5/8 抽到第三個物品的機率為 0/8
LUT 轉換展開 -> [0,0,0,1,1,1,1,1] 這樣只要從Slice當中直接取一個值，就符合抽樣
建議使用情境：
- LUT：權重總和（acc）較小、元素數量不大，且需要非常快速的抽樣時使用。
- AliasTable：權重總和可能很大、需要穩定 O(1) 抽樣且避免巨大切片時，優先選用 AliasTable。
基本判斷原則： 總和在 100_000 以下建議使用LUT，超過則建議AliasTable
Source Files