1919import math
2020import sys
2121from collections import OrderedDict , abc
22+ from functools import lru_cache
2223
2324from hypothesis .errors import InvalidArgument
2425from 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 )
0 commit comments