ruby 38 lines · 7 steps

Weighted random sampling with binary search

A cumulative-weight table plus binary search picks keys proportional to their weight in logarithmic time.

Explained by highlit
Intermediate weighted-sampling binary-search cumulative-sum probability composition
1class WeightedSampler
2 def initialize(weights)
3 @entries = weights.to_a
4 @total = @entries.sum { |_, w| w }
5 raise ArgumentError, "weights must sum to a positive value" unless @total > 0
6 
7 @cumulative = []
8 running = 0.0
9 @entries.each do |key, weight|
10 running += weight
11 @cumulative << [key, running]
12 end
13 end
14 
15 def sample(rng = Random)
16 target = rng.rand * @total
17 index = @cumulative.bsearch_index { |_, ceiling| ceiling > target }
18 @cumulative[index || -1].first
19 end
20 
21 def sample_n(count, rng = Random)
22 Array.new(count) { sample(rng) }
23 end
24end
25 
26class WorkDistributor
27 def initialize(workers)
28 @sampler = WeightedSampler.new(workers.transform_values { |w| w.fetch(:capacity) })
29 @workers = workers
30 end
31 
32 def dispatch(jobs)
33 jobs.group_by { |_| @sampler.sample }.each do |worker_id, batch|
34 queue = @workers.dig(worker_id, :queue)
35 queue.push_bulk(batch)
36 end
37 end
38end
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Precomputing a cumulative sum turns weighted selection into a single ordered lookup.
  2. 2Binary search over a monotonic ceiling array makes each sample O(log n) instead of O(n).
  3. 3Wrapping the sampler behind a distributor keeps the probability math separate from the work-dispatch logic.

Related explainers

ruby 
class Order
  class InvalidTransition < StandardError; end
 
  TRANSITIONS = {

A state machine for order transitions in Ruby

state-machine data-driven error-handling
Intermediate 8 steps
rust 
use std::cmp::Ordering;
 
pub struct PrefixIndex {
    entries: Vec<String>,

Prefix search with binary partitioning in Rust

binary-search sorting case-insensitive
Intermediate 7 steps
ruby 
class CreateOrderItems < ActiveRecord::Migration[7.1]
  def change
    create_table :order_items do |t|
      t.references :order, null: false, foreign_key: { on_delete: :cascade }

Enforcing order-item integrity in Rails

migrations foreign-keys validations
Intermediate 7 steps
ruby 
class Registration < ApplicationRecord
  belongs_to :event
 
  validates :email, presence: true, format: { with: URI::MailTo::EMAIL_REGEXP }

Validating registrations in Rails

validations i18n error-handling
Intermediate 8 steps
ruby 
class ApacheLogParser
  LINE_PATTERN = /\A(?<ip>\S+)\s\S+\s\S+\s\[(?<time>[^\]]+)\]\s"(?<method>[A-Z]+)\s(?<path>\S+)\s(?<protocol>[^"]+)"\s(?<status>\d{3})\s(?<bytes>\d+|-)/
 
  TIME_FORMAT = "%d/%b/%Y:%H:%M:%S %z"

Parsing Apache logs with named captures

regex named-captures parsing
Intermediate 6 steps
ruby 
require "csv"
 
def parse_transaction_row(line)
  fields = CSV.parse_line(line, headers: false, skip_blanks: true)

Parsing one CSV transaction row in Ruby

parsing type-coercion error-handling
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

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