Issue 854: sample improvements by bbayles · Pull Request #855 · more-itertools/more-itertools

bbayles · 2024-06-11T14:39:49Z

This PR makes some changes to sample:

shuffle is called before returning the output
A note about differences from random.sample is added to the docstring
ValueError is raised for negative k values

Closes #854

rhettinger · 2024-06-11T19:32:16Z

more_itertools/more.py

    """Return a *k*-length list of elements chosen (without replacement)
-    from the *iterable*. Like :func:`random.sample`, but works on iterables
-    of unknown length.
+    from the *iterable*. Similar to :func:`random.sample`, but works on


Consider documenting that if the input iterable is sized k or smaller, more_itertools.sample() will return all of the input in shuffled order, possibly giving a result length smaller than k.

Alternatively, consider adding a strict option to raise an exception as random.sample() does. That would let the user decide whether it is an error to say, "choose 100 distinct notes on an 88-key piano."

That would be similar to what we did for batched() where only the user could know whether a short batch would be acceptable.

rhettinger · 2024-06-11T19:33:37Z

Overall, this looks like an excellent set of edits. Thank you.

rhettinger · 2024-06-12T03:26:13Z

Please also fix the bad variable name starting in sample() and flowing through to the two private functions.

- iterable = iter(iterable)
+ iterator = iter(iterable)

Both private functions ONLY work with iterators, not generic iterables because the take() step changes state by advancing the iterator and the subsequent enumeration relies on that state change.

bbayles · 2024-06-12T15:44:51Z

I added in the strict parameter — good idea.

I didn't change the input parameter names on the main function (don't want to break the theoretical person who's using it as a keyword), but did on the private functions.

rhettinger · 2024-06-12T23:16:24Z

Unless I'm missing something, the variable names inside the main function can be changed (leaving the user visible API unchanged). Something like this:

def _sample_unweighted(iterator, k, strict):
    ...

def _sample_weighted(iterator, k, weights, strict):
    ...

def sample(iterable, k, weights=None, strict=False):
    if k < 0:
        raise ValueError('k must be non-negative')
    if k == 0:
        return []

    iterator = iter(iterable)     # <-- CHANGE HERE
    if weights is None:
        return _sample_unweighted(iterator, k, strict)   # <-- CHANGE HERE
    else:
        weights = iter(weights)
        return _sample_weighted(iterator, k, weights, strict)   # <-- CHANGE HERE

Would it make sense to add stubs for the private functions to let a type checker verify that iterators are passed in?

def _sample_unweighted(
     iterator: Iterator[_T],
     k: int,
     strict: bool = ...,
 ) -> list[_T]: ...

def _sample_weighted(
     iterable: Iterator[_T],
     k: int,
     weights: Iterator[float] | None = ...,
     strict: bool = ...,
 ) -> list[_T]: ...

rhettinger · 2024-06-12T23:42:29Z

The explanation of the weights parameter seems way off, "The relative weight of each item determines the probability that it appears late in the permutation."

The wording in the Efraimidis paper is better, "In weighted random sampling (WRS) the items are weighted and the probability of each item to be selected is determined by its relative weight."

However even that only explains the probability of being added to the reservoir. From a users point of view, it misses an essential point: when an item with high weight is selected, the probabilities of the remaining items increase.

Ideally, there should be some wording that allows a user to predict this outcome:

>>> Counter(chain.from_iterable(more_itertools.sample('abc', 2, [98, 1, 1]) for i in range(100_000)))
Counter({'a': 99978, 'c': 50136, 'b': 49886})

bbayles · 2024-06-13T00:10:24Z

I'm open to suggestions on how much detail is appropriate. I could link to the papers, perhaps?

rhettinger · 2024-06-13T00:28:29Z

The papers are a difficult read. They only explain the algorithm and don't elaborate on the goal.

Some documentation edit does need to be made because the current sentence is just wrong. There is no notion of "appearing late in the permutation".

Maybe this:

Weighted selections are made without replacement. After an element is selected, it is removed from the pool and the relative weights of the other elements increase. The final result is shuffled so that weights only affect the probability of selection but not the position in the final permutation.

bbayles · 2024-06-13T15:19:11Z

Thanks - I incorporated your suggestions. Wikipedia has descriptions of both algorithms, which I've linked for those who are interested in more detail.

more_itertools/more.py

Issue 854: sample improvements

6675c74

bbayles mentioned this pull request Jun 11, 2024

Issues with sample() #854

Closed

rhettinger reviewed Jun 11, 2024

View reviewed changes

Add strict parameter

2ab70dc

bbayles added 2 commits June 13, 2024 10:12

More sample docstring changes

dc7a36a

Type hints for sample helpers

72bae80

Don't un-heapify

c0b8476

rhettinger reviewed Jun 13, 2024

View reviewed changes

more_itertools/more.py Outdated Show resolved Hide resolved

bbayles added 2 commits June 14, 2024 09:18

Avoid extra heappop steps

cc6f680

Drop unused import

cbb0518

bbayles merged commit d06de20 into master Jun 14, 2024

bbayles deleted the sample-docs branch June 14, 2024 14:24

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Issue 854: sample improvements#855

Issue 854: sample improvements#855
bbayles merged 7 commits intomasterfrom
sample-docs

bbayles commented Jun 11, 2024

Uh oh!

rhettinger Jun 11, 2024 •

edited

Loading

Uh oh!

rhettinger commented Jun 11, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

bbayles commented Jun 12, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

bbayles commented Jun 13, 2024

Uh oh!

rhettinger commented Jun 13, 2024

Uh oh!

bbayles commented Jun 13, 2024

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

bbayles commented Jun 11, 2024

Uh oh!

rhettinger Jun 11, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rhettinger commented Jun 11, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

bbayles commented Jun 12, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

rhettinger commented Jun 12, 2024

Uh oh!

bbayles commented Jun 13, 2024

Uh oh!

rhettinger commented Jun 13, 2024

Uh oh!

bbayles commented Jun 13, 2024

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

rhettinger Jun 11, 2024 •

edited

Loading