Micro-optimization for random.choices(). Convert range() to repeat().

[rhettinger]

Borrowing from the technique used in the timeit module, loop with repeat() instead of range() to avoid unnecessary creation and destruction of integer objects. Gives a modest speed-up (in the 5% range).

Patched:

$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=2)'
200000 loops, best of 11: 1.82 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
1000 loops, best of 11: 388 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
500 loops, best of 11: 390 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=2)'
200000 loops, best of 11: 1.43 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' 'choices(p, k=1000)'
1000 loops, best of 11: 255 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' 'choices(p, k=1000)'
1000 loops, best of 11: 255 usec per loop

Baseline:

$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=2)'
200000 loops, best of 11: 1.95 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
500 loops, best of 11: 398 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
500 loops, best of 11: 402 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=2)'
200000 loops, best of 11: 1.5 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=1000)'
1000 loops, best of 11: 271 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=1000)'
1000 loops, best of 11: 272 usec per loop

[rhettinger]

The above timings were on Clang. The following were run with GCC-8 and show a consistent 5% to 6% improvement.

Patched:

$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=2)'
200000 loops, best of 11: 1.27 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=2)'
200000 loops, best of 11: 1.68 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=1000)'
1000 loops, best of 11: 211 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
1000 loops, best of 11: 363 usec per loop

Baseline:

$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=2)'
200000 loops, best of 11: 1.34 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=2)'
200000 loops, best of 11: 1.79 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, k=1000)'
1000 loops, best of 11: 225 usec per loop
$ ./python.exe -m timeit -r11 -s 'from random import choices' -s'p=range(20)' -s'w=list(map(float, range(20)))' 'choices(p, cum_weights=w, k=1000)'
1000 loops, best of 11: 347 usec per loop

[tirkarthi]

Is repeat(None, k) with a for loop the fastest way to call a function k times in Python?

[rhettinger]

repeat(None, k) is the fastest way to create an iterator that loops k times.

Since the iterated action is doing more than just a function call, map() and list() won't be of any help in the loop body.

[pganssle]

LGTM. Given that itertools is already imported, it doesn't seem like there's an import-time cost, so I don't see any downsides.

[bedevere-bot]

@rhettinger: Please replace # with GH- in the commit message next time. Thanks!