From ddf7171911e117aa7ad4b0f9ded4f0c3a4ca0fec Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Wed, 27 Jun 2018 01:08:31 -0700 Subject: bpo-24567: Random subnormal.diff (#7954) Handle subnormal weights for choices() --- Lib/random.py | 4 +++- Lib/test/test_random.py | 8 ++++++++ Misc/NEWS.d/next/Library/2018-06-27-00-31-30.bpo-24567.FuePyY.rst | 2 ++ 3 files changed, 13 insertions(+), 1 deletion(-) create mode 100644 Misc/NEWS.d/next/Library/2018-06-27-00-31-30.bpo-24567.FuePyY.rst diff --git a/Lib/random.py b/Lib/random.py index 1e0dcc8..1006908 100644 --- a/Lib/random.py +++ b/Lib/random.py @@ -383,7 +383,9 @@ class Random(_random.Random): raise ValueError('The number of weights does not match the population') bisect = _bisect.bisect total = cum_weights[-1] - return [population[bisect(cum_weights, random() * total)] for i in range(k)] + hi = len(cum_weights) - 1 + return [population[bisect(cum_weights, random() * total, 0, hi)] + for i in range(k)] ## -------------------- real-valued distributions ------------------- diff --git a/Lib/test/test_random.py b/Lib/test/test_random.py index e7ef68b..38fd8a9 100644 --- a/Lib/test/test_random.py +++ b/Lib/test/test_random.py @@ -227,6 +227,14 @@ class TestBasicOps: with self.assertRaises(IndexError): choices([], cum_weights=[], k=5) + def test_choices_subnormal(self): + # Subnormal weights would occassionally trigger an IndexError + # in choices() when the value returned by random() was large + # enough to make `random() * total` round up to the total. + # See https://bugs.python.org/msg275594 for more detail. + choices = self.gen.choices + choices(population=[1, 2], weights=[1e-323, 1e-323], k=5000) + def test_gauss(self): # Ensure that the seed() method initializes all the hidden state. In # particular, through 2.2.1 it failed to reset a piece of state used diff --git a/Misc/NEWS.d/next/Library/2018-06-27-00-31-30.bpo-24567.FuePyY.rst b/Misc/NEWS.d/next/Library/2018-06-27-00-31-30.bpo-24567.FuePyY.rst new file mode 100644 index 0000000..d496f2b --- /dev/null +++ b/Misc/NEWS.d/next/Library/2018-06-27-00-31-30.bpo-24567.FuePyY.rst @@ -0,0 +1,2 @@ +Improve random.choices() to handle subnormal input weights that could +occasionally trigger an IndexError. -- cgit v0.12