Description
The NonReplacementWeightedSampler class implements a random sampler where the probability of selecting an item is proportional to its weight, and every item is sampled exactly once (without repetition or replacement). In other words, each sample attempt returns a unique item.
Key Features ✨
- Weighted Random Sampling 🏋️♀️: Sampling items with proportional probability to their weight.
- No Replacement: Every item is sampled exactly once. In other words, each sample attempt returns a unique item.
- Efficiency ⚙️: Amortized O(log(n)) time and O(1) space per sample, making this class suitable for performance-critical applications with large item sets and high sampling frequency. In the worst case, both time and space complexity are O(n) during a restructure operation, which can occur at most O(log(n)) times.
- Comprehensive documentation 📚: The class is thoroughly documented, enabling IDEs to provide helpful tooltips that enhance the coding experience.
- Tests 🧪: Fully covered by comprehensive unit tests, including stress tests with randomized weights and a large number of samples. Specifically, the tests validate that sampling all n items has a complexity of O(nlogn). Practical benchmarks show that sampling n items typically requires C * nlog(n) operations, with C generally ranging between 8 and 9.
- No external runtime dependencies: Only development dependencies are used.
- ES2020 Compatibility: The
tsconfigtarget is set to ES2020, ensuring compatibility with ES2020 environments. - TypeScript support.