Skip to content

Commit 59521cd

Browse files
Zac-HDjebob
andcommitted
Fix average_size calculation
Co-Authored-By: Robert Howlett <[email protected]>
1 parent 12ba178 commit 59521cd

8 files changed

Lines changed: 78 additions & 6 deletions

File tree

‎AUTHORS.rst‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,6 +115,7 @@ their individual contributions.
115115
* `Pierre-Jean Campigotto <https://github.com/PJCampi>`_
116116
* `Przemek Konopko <https://github.com/soutys>`_
117117
* `Richard Boulton <https://www.github.com/rboulton>`_ ([email protected])
118+
* `Robert Howlett <https://github.com/jebob>`_
118119
* `Robert Knight <https://github.com/robertknight>`_ ([email protected])
119120
* `Rónán Carrigan <https://www.github.com/rcarriga>`_ ([email protected])
120121
* `Ruben Opdebeeck <https://github.com/ROpdebee>`_

‎hypothesis-python/RELEASE.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
RELEASE_TYPE: patch
2+
3+
This release fixes some internal calculations related to collection sizes (:issue:`3143`).

‎hypothesis-python/src/hypothesis/extra/array_api.py‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -347,7 +347,10 @@ def do_draw(self, data):
347347
# sqrt isn't chosen for any particularly principled reason. It
348348
# just grows reasonably quickly but sublinearly, and for small
349349
# arrays it represents a decent fraction of the array size.
350-
average_size=math.sqrt(self.array_size),
350+
average_size=min(
351+
0.9 * self.array_size, # ensure small arrays sometimes use fill
352+
max(10, math.sqrt(self.array_size)), # ...but *only* sometimes
353+
),
351354
)
352355

353356
assigned = set()

‎hypothesis-python/src/hypothesis/extra/numpy.py‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -255,7 +255,10 @@ def do_draw(self, data):
255255
# sqrt isn't chosen for any particularly principled reason. It
256256
# just grows reasonably quickly but sublinearly, and for small
257257
# arrays it represents a decent fraction of the array size.
258-
average_size=math.sqrt(self.array_size),
258+
average_size=min(
259+
0.9 * self.array_size, # ensure small arrays sometimes use fill
260+
max(10, math.sqrt(self.array_size)), # ...but *only* sometimes
261+
),
259262
)
260263

261264
needs_fill = np.full(self.array_size, True)
@@ -312,7 +315,7 @@ def do_draw(self, data):
312315
if mismatch.any():
313316
raise InvalidArgument(
314317
"Array elements %r cannot be represented as dtype %r - instead "
315-
"they becomes %r. Use a more precise strategy, e.g. without "
318+
"they become %r. Use a more precise strategy, e.g. without "
316319
"trailing null bytes, as this will be an error future versions."
317320
% (result[mismatch], self.dtype, out[mismatch])
318321
)

‎hypothesis-python/src/hypothesis/internal/conjecture/utils.py‎

Lines changed: 40 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
import math
2020
import sys
2121
from collections import OrderedDict, abc
22+
from functools import lru_cache
2223

2324
from hypothesis.errors import InvalidArgument
2425
from hypothesis.internal.compat import floor, int_from_bytes
@@ -390,7 +391,7 @@ def __init__(self, data, min_size, max_size, average_size):
390391
self.min_size = min_size
391392
self.max_size = max_size
392393
self.data = data
393-
self.stopping_value = 1 - 1.0 / (1 + average_size)
394+
self.p_continue = _calc_p_continue(average_size - min_size, max_size - min_size)
394395
self.count = 0
395396
self.rejections = 0
396397
self.drawn = False
@@ -418,7 +419,7 @@ def more(self):
418419
elif self.count >= self.max_size:
419420
forced_result = False
420421
should_continue = biased_coin(
421-
self.data, self.stopping_value, forced=forced_result
422+
self.data, self.p_continue, forced=forced_result
422423
)
423424

424425
if should_continue:
@@ -442,3 +443,40 @@ def reject(self):
442443
self.data.mark_invalid()
443444
else:
444445
self.force_stop = True
446+
447+
448+
@lru_cache()
449+
def _calc_p_continue(desired_avg, max_size):
450+
"""Return the p_continue which will generate the desired average size."""
451+
if desired_avg == max_size:
452+
return 1.0
453+
p_continue = 1 - 1.0 / (1 + desired_avg)
454+
if p_continue == 0 or max_size == float("inf"):
455+
assert 0 <= p_continue < 1, p_continue
456+
return p_continue
457+
# For small max_size, the infinite-series p_continue is a poor approximation,
458+
# and while we can't solve the polynomial a few rounds of iteration quickly
459+
# gets us a good approximate solution in almost all cases (sometimes exact!).
460+
while _p_continue_to_avg(p_continue, max_size) > desired_avg:
461+
# This is impossible over the reals, but *can* happen with floats.
462+
p_continue -= 0.0001
463+
# Let's binary-search our way to a better estimate! We tried fancier options
464+
# like gradient descent, but this is numerically stable and works better.
465+
hi = 1.0
466+
while desired_avg - _p_continue_to_avg(p_continue, max_size) > 0.01:
467+
assert p_continue < hi
468+
mid = (p_continue + hi) / 2
469+
if _p_continue_to_avg(mid, max_size) <= desired_avg:
470+
p_continue = mid
471+
else:
472+
hi = mid
473+
assert 0 < p_continue < 1
474+
assert _p_continue_to_avg(p_continue, max_size) <= desired_avg
475+
return p_continue
476+
477+
478+
def _p_continue_to_avg(p_continue, max_size):
479+
"""Return the average_size generated by this p_continue and max_size."""
480+
if p_continue >= 1:
481+
return max_size
482+
return (1.0 / (1 - p_continue) - 1) * (1 - p_continue ** max_size)

‎hypothesis-python/src/hypothesis/provisional.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -119,7 +119,7 @@ def do_draw(self, data):
119119
# with a max of 255, that leaves 3 characters for a TLD.
120120
# Allowing any more subdomains would not leave enough
121121
# characters for even the shortest possible TLDs.
122-
elements = cu.many(data, min_size=1, average_size=1, max_size=126)
122+
elements = cu.many(data, min_size=1, average_size=3, max_size=126)
123123
while elements.more():
124124
# Generate a new valid subdomain using the regex strategy.
125125
sub_domain = data.draw(st.from_regex(self.label_regex, fullmatch=True))

‎hypothesis-python/tests/conjecture/test_utils.py‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -320,3 +320,7 @@ def test_can_draw_arbitrary_fractions(p, b):
320320
def test_samples_from_a_range_directly():
321321
s = cu.check_sample(range(10 ** 1000), "")
322322
assert isinstance(s, range)
323+
324+
325+
def test_p_continue_to_average_saturates():
326+
assert cu._p_continue_to_avg(1.1, 100) == 100

‎hypothesis-python/tests/nocover/test_conjecture_utils.py‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,9 +15,11 @@
1515

1616
from fractions import Fraction
1717

18+
from hypothesis import assume, example, given, strategies as st, target
1819
from hypothesis.internal.compat import int_to_bytes
1920
from hypothesis.internal.conjecture import utils as cu
2021
from hypothesis.internal.conjecture.data import ConjectureData, StopTest
22+
from hypothesis.internal.conjecture.engine import BUFFER_SIZE
2123

2224

2325
def test_gives_the_correct_probabilities():
@@ -44,3 +46,21 @@ def test_gives_the_correct_probabilities():
4446
i += 256
4547
else:
4648
i += 1
49+
50+
51+
# BUFFER_SIZE divided by (2bytes coin + 1byte element) gives the
52+
# maximum number of elements that we would ever be able to generate.
53+
@given(st.floats(0, BUFFER_SIZE // 3), st.integers(0, BUFFER_SIZE // 3))
54+
def test_p_continue(average_size, max_size):
55+
assume(average_size <= max_size)
56+
p = cu._calc_p_continue(average_size, max_size)
57+
assert 0 <= target(p, label="p") <= 1
58+
abs_err = abs(average_size - cu._p_continue_to_avg(p, max_size))
59+
assert target(abs_err, label="abs_err") < 0.01
60+
61+
62+
@example(1.1, 10)
63+
@given(st.floats(0, 1), st.integers(0, BUFFER_SIZE // 3))
64+
def test_p_continue_to_average(p_continue, max_size):
65+
average = cu._p_continue_to_avg(p_continue, max_size)
66+
assert 0 <= average <= max_size

0 commit comments

Comments
 (0)