Change `random.choice()` parameter from `Sequence` to `Collection`

Ideas
1

Currently, random.choice requires a sequence:

random.choice({1, 2, 3})  # TypeError: 'set' object is not subscriptable

Conversion of the argument to list or tuple works:

random.choice(list({1, 2, 3}))  # Okay

This is a bit of an inconvenience (I forget, see the error, and correct; wasted another 2 min ;-), and is wasteful for large collections.

A Sized Iterable parameter would suffice, a.k.a. a Collection (with Container):

def choice2[T](self, col: Collection[T]) -> T:
    """Choose a random element from a non-empty sized iterable."""

    # As an accommodation for NumPy, we don't use "if not col"
    # because bool(numpy.array()) raises a ValueError.
    if not len(col):
        raise IndexError('Cannot choose from an empty collection')

    # To allow e.g. set next to sequence, use islice instead of subscripting
    return next(itertools.islice(col, self._randbelow(len(col)), None))

choice2({1, 2, 3})  # Okay

The downside is that islice partially consumes the iterable, and therefore is slower than subscripting for sequences.
To prevent loss of performance on large sequences, and still gain performance on large sets, plus gain convenience of a more versatile choice, we need to try both:

def choice3[T](self, col: Collection[T]) -> T:
    """Choose a random element from a non-empty sized iterable."""

    # Avoiding to call len() multiple times, shaves ~4% from choice's runtime
    l = len(col)

    # As an accommodation for NumPy, we don't use "if not col"
    # because bool(numpy.array()) raises a ValueError.
    if not l:
        raise IndexError('Cannot choose from an empty collection')

    # By subscripting or islice, we need the same element number
    n = self._randbelow(l)
    try:
        # To keep the speed for sequence, use subscripting
        return col[n]
    except TypeError:
        # To allow e.g. set, use islice instead
        return next(itertools.islice(col, n, None))

choice3([1, 2, 3])  # Okay (and still fast for large sequences)
choice3({1, 2, 3})  # Okay (and faster than conversion to list for large sets)
2

If this O(n) behaviour is acceptable for you, I suggest using this in your own projects, rather than changing it. This would be a distinctly worse implementation for the common case where the argument is in fact a sequence, forfeiting the direct indexing that it currently can do.

And this version, while plausible, still adds unnecessary risks. It means that it might be fast but might be suddenly slow. Again, if this is what you want, you can use it in your own project, but I don’t think it’s right for the stdlib.

2 Likes
3

It can only be fast and suddenly slow if its argument changes from sequence to non-sequence collection (e.g. set). In the current version, such change means it might work and might suddenly fail.

Of course, I can change that in my own projects (although monkey patching random.py isn’t completely trivial by its use of bound methods). But currently choice() is less liberal in what it accepts than it needs to be.

1 Like
4

Currently it guarantees O(1) behaviour (assuming the object given doesn’t have pathological subscripting). If you need something more liberal, make your own choice function (as you’ve done).

1 Like
5

It was already discussed before. Search in old issues.

If you are fine with O(N), just convert the argument to list before passing to random.choice(). This is simpler and often faster. You can also cache the list.

2 Likes