sansreplace: a novel O(k log k) sampling-without-replacement algorithm with zero extra memory
burny_tech · x · 2026-10-13
Developer ciphergoth has open-sourced sansreplace, featuring "Cardchoose," an algorithm he says he found eight years ago and believes is still novel: fairly sample k distinct integers below n using only the output vector — no hash set, no extra memory, O(k log k).
The innovation is a step that deliberately favors duplicates, then removes them via a sort-plus-offset mapping, eliminating auxiliary data structures. The repo ships Python, C++, and Rust implementations, algorithm write-ups, prior-art notes, and benchmark results, under Apache-2.0.
More from Research
- Learned optimizers without 4,000 TPU months: new work claims general-purpose trained optimizers are finally practical — burkov · 2026-10-13
- Natura-1: 50B-param MoE robot foundation model pretrained on 1M hours of egocentric human video — heyshrutimishra · 2026-10-13
- Graph theorist spends 20 hours on OpenAI Math Dump, finds solutions to his decade-old conjectures — burny_tech · 2026-10-13
- tszzl predicts mechinterp progress in coming months unlike anything in years — tszzl · 2026-10-13
- Free ML Workshop on the Math Discord Server Covers ML, Deep Learning and Graphs — zeroalephzeta · 2026-10-13
- New Paper Explains Mamba-3's State Rotations as Underdamped Second-Order Dynamics — tri_dao · 2026-10-13