Add SliceRandom::choose_multiple_weighted, implementing weighted sampling without replacement #976

zrneely · 2020-05-11T05:11:53Z

This introduces two new methods, intended to close #596 :

SliceRandom::choose_multiple_weighted - similar to SliceRandom::choose_multiple, but without replacement and with weights.
index::sample_weighted - an analogue to index::sample which implements the actual logic.

This notably includes two different implementations of sample_weighted - one which uses an unstable, nightly-only feature of the standard library, "slice_partition_at_index", and one which uses only stable functionality. By my measurements, the performance improvement of using the unstable feature with very large slices is extremely significant (see below). I'm not sure what the right thing to do here is - the options seem to be:

Keep things the way they are, and remove the worse implementation if/when the unstable feature is stabilized. I'm not sure how this interacts with rustc version requirements.
Copy the unstable feature's logic into this crate. This has the downside that It's a significant amount of logic that arguably doesn't belong in rand, and it involves lots of use of unsafe.

Both implementations are based on Algorithm A described by Efraimidis and Spirakis in their paper on Weighted Random Sampling, available here. They differ in the way they implement step 2, "select the items with the largest keys".

Finally, one last thing I'm uncertain about is the behavior the algorithm should take when given invalid weights - negative values and NaN. The approach I've taken so far is to add a check that the result of the user-specified weight function is valid before computing with it, but the alternative is simply documenting that the behavior of the algorithm is not specified if the weights are invalid.

Here are some benchmarking results taken on Windows on a Ryzen 1700X:

> cargo +nightly bench -- sample_weighted

test misc_sample_weighted_indices_100_of_1M  ... bench:  86,739,580 ns/iter (+/- 3,530,996)
test misc_sample_weighted_indices_100_of_1k  ... bench:      92,856 ns/iter (+/- 1,179)
test misc_sample_weighted_indices_10_of_1k   ... bench:      84,986 ns/iter (+/- 1,144)
test misc_sample_weighted_indices_1_of_1k    ... bench:      83,997 ns/iter (+/- 1,771)
test misc_sample_weighted_indices_1k_of_1M   ... bench:  87,341,100 ns/iter (+/- 508,386)
test misc_sample_weighted_indices_200_of_1M  ... bench:  87,002,990 ns/iter (+/- 989,274)
test misc_sample_weighted_indices_400_of_1M  ... bench:  87,762,280 ns/iter (+/- 4,247,746)
test misc_sample_weighted_indices_600_of_1M  ... bench:  87,204,490 ns/iter (+/- 3,406,199)

> cargo +nightly bench --features="nightly" -- sample_weighted

test misc_sample_weighted_indices_100_of_1M  ... bench:  50,854,360 ns/iter (+/- 5,298,528)
test misc_sample_weighted_indices_100_of_1k  ... bench:      41,186 ns/iter (+/- 11,823)
test misc_sample_weighted_indices_10_of_1k   ... bench:      40,682 ns/iter (+/- 21,438)
test misc_sample_weighted_indices_1_of_1k    ... bench:      35,714 ns/iter (+/- 527)
test misc_sample_weighted_indices_1k_of_1M   ... bench:  50,370,600 ns/iter (+/- 4,227,278)
test misc_sample_weighted_indices_200_of_1M  ... bench:  49,976,930 ns/iter (+/- 4,569,493)
test misc_sample_weighted_indices_400_of_1M  ... bench:  49,964,680 ns/iter (+/- 5,318,092)
test misc_sample_weighted_indices_600_of_1M  ... bench:  50,865,190 ns/iter (+/- 4,911,017)

vks · 2020-05-11T13:29:18Z

Cargo.toml

@@ -23,7 +23,7 @@ appveyor = { repository = "rust-random/rand" }
 [features]
 # Meta-features:
 default = ["std", "std_rng"]
-nightly = ["simd_support"] # enables all features requiring nightly rust
+nightly = ["simd_support", "partition_at_index"] # enables all features requiring nightly rust


A simpler approach might be to just use the nightly feature instead of introducing a new one. This would have the advantage that we don't have to worry about dropping the feature in the future without breaking code.

My reasoning here is that this allows leaving the feature flag in place even once "slice_partition_at_index" stabilizes, which would allow supporting older rustc versions. I also see your point about dropping the feature being a breaking change, though...

Fair enough. I think we will likely just raise the minimum Rust version. @dhardy What do you think?

In general, it is not possible to reliably support old nightlies, and not very useful either. So removing a feature flag only usable on nightly compilers once that feature has stabilised is not an issue.

src/seq/index.rs

vks · 2020-05-11T13:53:06Z

The implementation looks good to me. I think the general docs in rand::seq could be updated to mention weighted sampling with and without replacement.

dhardy · 2020-05-29T09:46:21Z

src/lib.rs

@@ -50,6 +50,7 @@
 #![doc(test(attr(allow(unused_variables), deny(warnings))))]
 #![cfg_attr(not(feature = "std"), no_std)]
 #![cfg_attr(all(feature = "simd_support", feature = "nightly"), feature(stdsimd))]
+#![cfg_attr(all(feature = "partition_at_index", feature = "nightly"), feature(slice_partition_at_index))]


This however makes separate use of partition_at_index pointless — I think unlike simd_support we should not depend on nightly here. As a bonus, this makes it impossible to use partition_at_index on stable compilers.

I still don't understand what the advantage of a separate partition_at_index is.

dhardy · 2020-05-29T09:47:06Z

src/seq/index.rs

-#[cfg(feature = "alloc")] use core::slice;
+#[cfg(feature = "alloc")]
+use core::slice;

 #[cfg(all(feature = "alloc", not(feature = "std")))]
 use crate::alloc::vec::{self, Vec};
-#[cfg(feature = "std")] use std::vec;
+#[cfg(feature = "std")]
+use std::vec;
 // BTreeMap is not as fast in tests, but better than nothing.
 #[cfg(all(feature = "alloc", not(feature = "std")))]
 use crate::alloc::collections::BTreeSet;
-#[cfg(feature = "std")] use std::collections::HashSet;
+#[cfg(feature = "std")]
+use std::collections::HashSet;


Leave the reformatting out please.

dhardy

Thanks for the PR! The paper (the full one, not what you linked) seems a good source (though I don't follow the integral{CDF × PDF} step).

dhardy · 2020-05-29T10:03:39Z

src/seq/index.rs

+        if length == 0 {
+            return Ok(IndexVec::USize(Vec::new()));
+        }


Better, if amount == 0. And this should be pushed up to the top of the method.

dhardy · 2020-05-29T10:06:21Z

src/seq/index.rs

+        fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
+            self.key
+                .partial_cmp(&other.key)
+                .or(Some(core::cmp::Ordering::Less))


Why include this line? To avoid panic in Ord::cmp? Does it have some benefit? Because it's technically wrong, and means NaN values could have arbitrary sort position (some sorting algs might not even terminate). Better just to allow a panic IMO.

dhardy · 2020-05-29T10:09:28Z

src/seq/index.rs

+        let mut candidates = Vec::with_capacity(length);
+        for index in 0..length {
+            let weight = weight(index).into();
+            if weight < 0.0 || weight.is_nan() {


I prefer !(weight >= 0.0), though it is equivalent.

dhardy · 2020-05-29T10:22:34Z

src/seq/index.rs

+pub fn sample_weighted<R, F, X>(
+    rng: &mut R, length: usize, weight: F, amount: usize,
+) -> Result<IndexVec, WeightedError>
+where
+    R: Rng + ?Sized,
+    F: Fn(usize) -> X,
+    X: Into<f64>,
+{


This implementation looks correct, but it may use a lot of memory without good cause. Suggestions:

If we know length <= u32::MAX, then use u32 instead of usize. I guess in this case we can't since a million entries can be evaluated in under a tenth of a second. It may or may not be worth testing and implementing multiple paths. (IndexVec is like it is for performance reasons.)

An implementation of the A-Res variant should compare well on performance I think (though still O(n)). An implementation of A-ExpJ variant should be the best option for length >> amount. It may be nice having both and selecting which to use with a heuristic, or it may be that A-ExpJ is fast enough to always be a good choice.

zrneely added 5 commits May 10, 2020 19:47

Add choose_multiple_weighted, tests, and benchmarks

aeeae49

Merge branch 'master' of github.com:rust-random/rand

45fa908

Mark new tests with the correct feature flags

efbab50

Fix feature flags and use core for nostd compatibility

f255bb9

Don't use rustc features newer than 1.32

4501873

vks reviewed May 11, 2020

View reviewed changes

src/seq/index.rs Outdated Show resolved Hide resolved

vks reviewed May 11, 2020

View reviewed changes

src/seq/index.rs Outdated Show resolved Hide resolved

Don't use IntoIter when unnecessary and fix complexity documentation

4f76aff

dhardy reviewed May 29, 2020

View reviewed changes

vks mentioned this pull request Aug 4, 2020

Re: weighted sampling without replacement #1013

Merged

vks closed this in #1013 Aug 27, 2020

CAD97 mentioned this pull request Dec 21, 2020

Update rand requirement from 0.7 to 0.8 bevyengine/bevy#1114

Merged

sync-by-unito bot mentioned this pull request Dec 21, 2020

Bump rand from 0.7.3 to 0.8.0 AleoHQ/leo#510

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add SliceRandom::choose_multiple_weighted, implementing weighted sampling without replacement #976

Add SliceRandom::choose_multiple_weighted, implementing weighted sampling without replacement #976

zrneely commented May 11, 2020

vks May 11, 2020

zrneely May 11, 2020

vks May 11, 2020

dhardy May 29, 2020 •

edited

vks commented May 11, 2020

dhardy May 29, 2020

vks Aug 4, 2020

dhardy May 29, 2020 •

edited

dhardy left a comment

dhardy May 29, 2020

dhardy May 29, 2020

dhardy May 29, 2020

dhardy May 29, 2020

Add SliceRandom::choose_multiple_weighted, implementing weighted sampling without replacement #976

Add SliceRandom::choose_multiple_weighted, implementing weighted sampling without replacement #976

Conversation

zrneely commented May 11, 2020

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dhardy May 29, 2020 • edited

Choose a reason for hiding this comment

vks commented May 11, 2020

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dhardy May 29, 2020 • edited

Choose a reason for hiding this comment

dhardy left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dhardy May 29, 2020 •

edited

dhardy May 29, 2020 •

edited