Build an alias table from non-negative weights. Weights do not need to sum to 1 — they are normalized internally. Zero-weight items are never selected. All weights must be non-negative. Returns `None` if weights are empty or all zero.
(weights: &[f64])
| 33 | /// |
| 34 | /// Returns `None` if weights are empty or all zero. |
| 35 | pub fn new(weights: &[f64]) -> Option<Self> { |
| 36 | let n = weights.len(); |
| 37 | if n == 0 { |
| 38 | return None; |
| 39 | } |
| 40 | |
| 41 | let total: f64 = weights.iter().sum(); |
| 42 | if total <= 0.0 { |
| 43 | return None; |
| 44 | } |
| 45 | |
| 46 | // Normalize so that each probability is scaled to n * (w_i / total). |
| 47 | let scale = n as f64 / total; |
| 48 | let mut scaled: Vec<f64> = weights.iter().map(|w| w * scale).collect(); |
| 49 | |
| 50 | let mut prob = vec![0.0f64; n]; |
| 51 | let mut alias = vec![0usize; n]; |
| 52 | |
| 53 | // Partition into small (< 1) and large (>= 1) groups. |
| 54 | let mut small: Vec<usize> = Vec::new(); |
| 55 | let mut large: Vec<usize> = Vec::new(); |
| 56 | |
| 57 | for (i, &s) in scaled.iter().enumerate() { |
| 58 | if s < 1.0 { |
| 59 | small.push(i); |
| 60 | } else { |
| 61 | large.push(i); |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | // Vose's algorithm: pair small items with large items. |
| 66 | while let (Some(s), Some(&l)) = (small.pop(), large.last()) { |
| 67 | prob[s] = scaled[s]; |
| 68 | alias[s] = l; |
| 69 | scaled[l] -= 1.0 - scaled[s]; |
| 70 | |
| 71 | if scaled[l] < 1.0 { |
| 72 | large.pop(); |
| 73 | small.push(l); |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | // Remaining items get probability 1.0 (numerical precision cleanup). |
| 78 | for &l in &large { |
| 79 | prob[l] = 1.0; |
| 80 | } |
| 81 | for &s in &small { |
| 82 | prob[s] = 1.0; |
| 83 | } |
| 84 | |
| 85 | Some(Self { prob, alias, n }) |
| 86 | } |
| 87 | |
| 88 | /// Sample one index (O(1) per call). |
| 89 | pub fn sample(&self, rng: &mut SeedableRng) -> usize { |