[issue35980] Py3 BIF random.choices() is O(N**2) but I've written O(N) code for the same task

[Steven D'Aprano]

Steven D'Aprano <steve+python at pearwood.info> added the comment:

What's "BIF" mean? You use that term multiple times but I have never heard it before.

I'm sorry, I don't understand your code (and don't have time to study it in detail to decipher it). It would help if you factored out your new implementation of choices() into a separate function.

I see that your timing code it not reliable for timing individual function calls. You include your setup code that builds the input to choices() as well as the time it takes to print messages, so we can't really draw any reliable conclusions about the speed of choices() from your timings.

To give an analogy: you start the stopwatch at home. Climb into the shower and wash, get dressed, have breakfast, drive to work, park the car, buy a coffee at the shop next door, go to your office, greet your fellow co-workers, and finally stop the stopwatch. And then you say that the total time measured was the time it took you to drive to work alone.

Finally, I can't actually work out what part of your code is intended as a replacement for the choices() function. You should factor it out into a separate function, then time the two function calls:

    choices(dataset, weights)
    shawn_choices(dataset, weights)

alone (without timing the setup of the datasets, or the I/O, or any other irrelevant costs). You probably should use the timeit module for the actual timing.

As for the versions of Python, 3.6 and older are in "bug fix only" mode, so this will not apply to anything older than 3.7.

----------
nosy: +steven.daprano
versions:  -Python 3.4, Python 3.5, Python 3.6

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue35980>
_______________________________________