[issue41131] Augment random.choices() with the alias method

Tim Peters added the comment: Oh yes - I understood the intent of the code. It's as good an approach to living with floating-point slop in this context as I've seen. It's not obviously broken. But neither is it obviously correct, and after a few minutes I didn't see a clear path to rigoro

[issue41131] Augment random.choices() with the alias method

Raymond Hettinger added the comment: FWIW, I paid close attention to rounding. The reason for the "while small and large" is that the loop stops making aliases unless we have both something at or below 0.5 and something known to be above 0.5. If we end up with only two bins slightly above

[issue41131] Augment random.choices() with the alias method

Raymond Hettinger added the comment: Okay, thank you for looking! -- resolution: -> wont fix stage: -> resolved status: open -> closed ___ Python tracker ___ ___

[issue41131] Augment random.choices() with the alias method

Tim Peters added the comment: I'm not clear on that the alias method is valuable here. Because of the preprocessing expense, it cries out for a class instead: an object that can retain the preprocessed tables, be saved to disk (pickled), restored later, and used repeatedly to make O(1) selec

[issue41131] Augment random.choices() with the alias method

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49270/choices_proposal.py ___ Python tracker ___ ___ Python-bugs-list

[issue41131] Augment random.choices() with the alias method

Change by Raymond Hettinger : Removed file: https://bugs.python.org/file49267/choices_proposal.py ___ Python tracker ___ ___ Python-bugs-lis

[issue41131] Augment random.choices() with the alias method

Change by Raymond Hettinger : Removed file: https://bugs.python.org/file49268/choices_binomial.py ___ Python tracker ___ ___ Python-bugs-lis

[issue41131] Augment random.choices() with the alias method

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49269/choices_binomial.py ___ Python tracker ___ ___ Python-bugs-list

[issue41131] Augment random.choices() with the alias method

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49268/choices_binomial.py ___ Python tracker ___ ___ Python-bugs-list

[issue41131] Augment random.choices() with the alias method

Raymond Hettinger added the comment: I also looked at another method using binomial variates but couldn't get it to run faster than the alias method: def choices(population, weights, *, k=1): r = 1.0 n = k selections = [] for elem, p in zip(population, weig

[issue41131] Augment random.choices() with the alias method

New submission from Raymond Hettinger : For n unequal weights and k selections, sample selection with the inverse-cdf method is O(k log₂ n). Using the alias method, it improves to O(k). The proportionally constants also favor the alias method so that if the set up times were the same, the al