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 
require "shellwords"
require "open3"
 
module Backup

Building safe shell commands in Ruby

shell-out subprocess command-injection
Intermediate 7 steps
ruby 
class UserAgentParser
  BROWSERS = [
    [/Edg\/([\d.]+)/, "Edge"],
    [/OPR\/([\d.]+)/, "Opera"],

Parsing user-agent strings in Ruby

regex pattern-matching lookup-tables
Intermediate 8 steps
ruby 
class LogAggregator
  BUCKET_FORMAT = "%Y-%m-%dT%H:%M"
 
  def initialize(entries)

Bucketing log entries by the minute in Ruby

aggregation hashing enumerable
Intermediate 5 steps
ruby 
class WeeklySignupsReport
  DEFAULT_WEEKS = 12
 
  def initialize(weeks: DEFAULT_WEEKS, source: User.all)

Building a weekly signups report in Rails

service object aggregation group by
Intermediate 7 steps
ruby 
class ApplicationController < ActionController::Base
  EXPERIMENTS = {
    checkout_button_color: %w[control blue green],
    onboarding_flow: %w[control streamlined]

How A/B test cohorts are assigned in Rails

a-b-testing cookies hashing
Intermediate 8 steps
ruby 
class SnippetHighlighter
  CONTEXT_RADIUS = 60
  MAX_TERMS = 8
 

Building search-result snippets in Ruby

regular-expressions text-processing search
Intermediate 9 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