Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Re: weighted sampling without replacement #1013

Merged
merged 11 commits into from Aug 27, 2020

Conversation

vks
Copy link
Collaborator

@vks vks commented Aug 4, 2020

This includes and closes #976.

@dhardy I tried to address your feedback from #976.

@vks
Copy link
Collaborator Author

vks commented Aug 4, 2020

Hmm, this does not quite work as intended, this test fails:

   #[test]
    fn test_sample_weighted() {
        let seed_rng = crate::test::rng;
        let v = sample_weighted(&mut seed_rng(423), 10, |i| i as f64, 5).unwrap();
        match v {
            IndexVec::U32(_) => {},
            IndexVec::USize(_) => panic!("expected `IndexVec::U32`"),
        }
    }

@vks
Copy link
Collaborator Author

vks commented Aug 5, 2020

Should be fixed now.

Copy link
Member

@dhardy dhardy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ach, sorry I left this so long.

I see no action regarding my last comment, but frankly don't think this is necessary just to get this merged. Might be worth making a note somewhere?

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.

src/seq/index.rs Outdated Show resolved Hide resolved
Copy link
Member

@dhardy dhardy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Trusting that there are no breaking changes to the algorithm since #976, I'll approve this.

@vks
Copy link
Collaborator Author

vks commented Aug 27, 2020

Trusting that there are no breaking changes to the algorithm since #976, I'll approve this.

You can look at the commits to see that I kept the original ones and did not modify the algorithm.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants