rust 39 lines · 7 steps

Weighted random sampling in Rust

A generic struct picks items in proportion to their weights using cumulative sums and a binary search.

Explained by highlit
Intermediate weighted-sampling generics binary-search cumulative-sum randomness
1use rand::Rng;
2 
3#[derive(Debug)]
4pub struct WeightedChoice<T> {
5 items: Vec<T>,
6 cumulative: Vec<f64>,
7 total: f64,
8}
9 
10impl<T> WeightedChoice<T> {
11 pub fn new(entries: impl IntoIterator<Item = (T, f64)>) -> Option<Self> {
12 let mut items = Vec::new();
13 let mut cumulative = Vec::new();
14 let mut total = 0.0;
15 
16 for (item, weight) in entries {
17 if weight <= 0.0 || !weight.is_finite() {
18 continue;
19 }
20 total += weight;
21 items.push(item);
22 cumulative.push(total);
23 }
24 
25 if items.is_empty() {
26 return None;
27 }
28 
29 Some(Self { items, cumulative, total })
30 }
31 
32 pub fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> &T {
33 let target = rng.gen_range(0.0..self.total);
34 let idx = self
35 .cumulative
36 .partition_point(|&c| c <= target);
37 &self.items[idx]
38 }
39}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Storing a running cumulative sum turns proportional sampling into a single binary search.
  2. 2Validating weights at construction time keeps the sampling hot path branch-free and correct.
  3. 3Returning Option from a constructor cleanly signals when no valid input was provided.

Related explainers

rust 
use serde::Deserialize;
 
#[derive(Debug, Deserialize)]
#[serde(untagged)]

Parsing flexible JSON shapes with serde

deserialization enums json
Intermediate 6 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
rust 
use axum::{
    extract::{Path, State},
    response::sse::{Event, KeepAlive, Sse},
};

Streaming import progress with SSE in Axum

server-sent-events streams watch-channel
Advanced 7 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Weighted random sampling in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code