random.SystemRandom().randint() inefficient

[Chris Angelico]

On Thu, 28 Jul 2022 at 05:36, Cecil Westerhof via Python-list
<python-list at python.org> wrote:
>
> Roel Schroeven <roel at roelschroeven.net> writes:
>
> > Cecil Westerhof via Python-list schreef op 27/07/2022 om 17:43:
> >> "Michael F. Stemper" <michael.stemper at gmail.com> writes:
> >>
> >> > This is orthogonal to your question, but might be of some use to you:
> >> >
> >> > The combination of using len(to_try) as an argument to randint() and
> >> > saving the output to a variable named "index" suggests that you might
> >> > be setting up to select a random element from to_try, as in:
> >> >   something = to_try[index]
> >> >
> >> > If that is the case, you might want to consider using random.choice() instead:
> >> >
> >> >   >>> from random import choice
> >> >   >>> to_try = [2,3,5,7,11,13,"seventeen",19]
> >> >   >>> choice(to_try)
> >> >   2
> >> >   >>> choice(to_try)
> >> >   'seventeen'
> >> >   >>> choice(to_try)
> >> >   13
> >> >   >>> choice(to_try)
> >> >   5
> >> >   >>>
> >>
> >> Yes, I try to select a random element, but it has also to be removed,
> >> because an element should not be used more as once.
> >> This is the code I use:
> >>      # index = randbelow(len(to_try))
> >>      index = randrange(len(to_try))
> >>      found = permutation[to_try.pop(index)]
> > Do you know in advance how many items you'll need, or maybe an upper
> > limit on the amount? In that case it might be more efficient to use
> > random.sample(to_try, k=nr_items_needed).
>
> Something else to try. :-)
> And yes: I will be using half of the list.
>

A perfect job for random.sample() then, if that's *exactly* half the list.

But if you don't know for sure how many you'll need, an easy way to
make it more efficient would be to take the n'th element, then move
the last element down to the n'th position, and finally pop off the
last element. That way, you only ever pop the last element away. The
list will get reordered arbitrarily while you do this, but if the only
purpose of it is to remove elements from random consideration, that
won't be a problem.

ChrisA