random.sample should support iterators

[thomasahle]

BPO	37682
Nosy	@rhettinger, @mdickinson, @serhiy-storchaka

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2019-07-26.09:25:43.143>
created_at = <Date 2019-07-25.17:03:28.457>
labels = ['type-feature', 'library', '3.9']
title = 'random.sample should support iterators'
updated_at = <Date 2019-07-26.09:25:43.138>
user = 'https://bugs.python.org/thomasahle'

bugs.python.org fields:

activity = <Date 2019-07-26.09:25:43.138>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2019-07-26.09:25:43.143>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2019-07-25.17:03:28.457>
creator = 'thomasahle'
dependencies = []
files = []
hgrepos = []
issue_num = 37682
keywords = []
message_count = 6.0
messages = ['348445', '348446', '348447', '348466', '348474', '348486']
nosy_count = 4.0
nosy_names = ['rhettinger', 'mark.dickinson', 'thomasahle', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue37682'
versions = ['Python 3.9']

[thomasahle]

Given a generator f() we can use random.sample(list(f()), 10) to get a uniform sample of the values generated.
This is fine, and fast, as long as list(f()) easily fits in memory.
However, if it doesn't, one has to implement the reservoir sampling algorithm as a pure python function, which is much slower, and not so easy.

It seems that having a fast reservoir sampling implementation in random.sample to use for iterators would be both useful and make the API more predictable.

Currently when passing an iterator random.sample throws TypeError: Population must be a sequence or set..
This is inconsistent with most of the standard library which accepts lists and iterators transparently.

I apologize if this enhancement has already been discussed.
I wasn't able to find it.
If wanted, I can write up a pull request.
I believe questions like this: https://stackoverflow.com/questions/12581437/python-random-sample-with-a-generator-iterable-iterator makes it clear that such functionality is wanted and non-obvious.

[serhiy-storchaka]

FYI, random.sample() (as most of other functions in the random module) is implemented in pure Python.

[serhiy-storchaka]

Possible implementation:

from itertools import islice as _islice

def reservoir_sample(self, population, k):
    if k < 0:
        raise ValueError("Sample is negative")
    it = iter(population)
    result = list(_islice(it, k))
    if len(result) < k:
        raise ValueError("Sample larger than population")
    self.shuffle(result)
    randbelow = self._randbelow
    for i, x in enumerate(it, k+1):
        j = randbelow(i)
        if j < k:
            result[j] = x
    return result

[rhettinger]

ISTM that if a generator produces so much data that it is infeasible to fit in memory, then it will also take a long time to loop over it and generate a random value for each entry.

FWIW, every time we've looked at reservoir sampling it has been less performant than what we have now. The calls to randbelow() are the slowest part, so doing more calls makes the overall performance worse. Also, doing more calls eats more entropy.

In general, it is okay for functions to accept only sequences if they exploit indexing in some way. For example, the current approach works great with sample(range(100_000_000_000), k=50). We really don't have to make everything accept all iterators. Besides, it is trivially easy to call list() if needed.

Overall, I'm -1 on redesigning the sampling algorithm to accommodate non-sequence iterators. AFAICT, it isn't important at all and as Serhiy pointed out, writing your own reservoir sampling is easy do. Lastly, the standard library doesn't try to be all things to all people, it is okay to leave many things for external packages -- we mostly provide a baseline of tools that cover common use cases and defer the rest to the Python ecosystem.

[serhiy-storchaka]

ISTM that if a generator produces so much data that it is infeasible to fit in memory, then it will also take a long time to loop over it and generate a random value for each entry.

Good point!

$ ./python -m timeit -s 'from random import sample as s' 's(range(10**6), 50)'
10000 loops, best of 5: 25.6 usec per loop
$ ./python -m timeit -s 'from random import sample as s' 's(list(range(10**6)), 50)'
10 loops, best of 5: 31.5 msec per loop
$ ./python -m timeit -s 'from random import reservoir_sample as s' 's(range(10**6), 50)'
1 loop, best of 5: 328 msec per loop

$ ./python -m timeit -s 'from random import sample as s' 's(range(10**8), 50)'
10000 loops, best of 5: 26.9 usec per loop
$ ./python -m timeit -s 'from random import sample as s' 's(list(range(10**8)), 50)'
1 loop, best of 5: 3.41 sec per loop
$ ./python -m timeit -s 'from random import reservoir_sample as s' 's(range(10**8), 50)'
1 loop, best of 5: 36.5 sec per loop

It is possible that a generator produces not so much data, but every item takes much memory so the total size does not fit in memory. But I suppose that the generation time of larger items will be proportionally larger, so reservoir_sample() will be just as slow.

[rhettinger]

Thomas, thank you for the suggestion but I think we should decline. The API for sample() is consistent with choice(), choices() and shuffle(). For the most part the sequence based API has worked out well.