From d52269bfd029c4a517ea74c17edd5c3a250c366c Mon Sep 17 00:00:00 2001 From: Tim Peters Date: Thu, 25 Jan 2001 06:23:18 +0000 Subject: Fix bugs introduced by rewrite (in particular, time-based initialization got broken). Also added new method .jumpahead(N). This finally gives us a semi-decent answer to how Python's RNGs can be used safely and efficiently in multithreaded programs (although it requires the user to use the new machinery!). --- Doc/lib/librandom.tex | 27 +++++++++++++++++++-------- Lib/random.py | 42 ++++++++++++++++++++++++++++++++++++++---- Misc/NEWS | 15 ++++++++++----- 3 files changed, 67 insertions(+), 17 deletions(-) diff --git a/Doc/lib/librandom.tex b/Doc/lib/librandom.tex index 4e4d615..9d303c2 100644 --- a/Doc/lib/librandom.tex +++ b/Doc/lib/librandom.tex @@ -33,14 +33,15 @@ Else, because no critical sections are implemented internally, calls from different threads may see the same return values. The functions supplied by this module are actually bound methods of a -hidden instance of the \var{random.Random} class. You can instantiate -your own instances of \var{Random} to get generators that don't share state. -This may be especially useful for multi-threaded programs, although there's -no simple way to seed the distinct generators to ensure that the generated -sequences won't overlap. Class \var{Random} can also be subclassed if you -want to use a different basic generator of your own devising: in that -case, override the \method{random()}, \method{seed()}, \method{getstate()} -and \method{setstate()} methods. +hidden instance of the \var{random.Random} class. You can instantiate your +own instances of \var{Random} to get generators that don't share state. +This is especially useful for multi-threaded programs, creating a different +instance of \var{Random} for each thread, and using the \method{jumpahead()} +method to ensure that the generated sequences seen by each thread don't +overlap. Class \var{Random} can also be subclassed if you want to use a +different basic generator of your own devising: in that case, override the +\method{random()}, \method{seed()}, \method{getstate()}, +\method{setstate()} and \method{jumpahead()} methods. Bookkeeping functions: @@ -68,6 +69,16 @@ Bookkeeping functions: of the generate to what it was at the time \code{setstate()} was called. \end{funcdesc} +\begin{funcdesc}{jumpahead}{n} + Change the internal state to what it would be if \code{random()} were + called n times, but do so quickly. \var{n} is a non-negative integer. + This is most useful in multi-threaded programs, in conjuction with + multiple instances of the \var{Random} class: \method{setstate()} or + \method{seed()} can be used to force all instances into the same + internal state, and then \method{jumpahead()} can be used to force the + instances' states as far apart as you like (up to the period of the + generator). + \end{funcdesc} Functions for integers: diff --git a/Lib/random.py b/Lib/random.py index a818f73..1b91886 100644 --- a/Lib/random.py +++ b/Lib/random.py @@ -72,8 +72,8 @@ class Random: self.gauss_next = None # Specific to Wichmann-Hill generator. Subclasses wishing to use a - # different core generator should override seed(), random(), getstate() - # and setstate(). + # different core generator should override the seed(), random(), + # getstate(), setstate(), and jumpahead() methods. def __whseed(self, x=0, y=0, z=0): """Set the Wichmann-Hill seed from (x, y, z). @@ -104,6 +104,7 @@ class Random: if a is None: self.__whseed() + return a = hash(a) a, x = divmod(a, 256) a, y = divmod(a, 256) @@ -115,11 +116,10 @@ class Random: def getstate(self): """Return internal state; can be passed to setstate() later.""" - return self.VERSION, self._seed, self.gauss_next def __getstate__(self): # for pickle - self.getstate() + return self.getstate() def setstate(self, state): """Restore internal state from object returned by getstate().""" @@ -134,6 +134,28 @@ class Random: def __setstate__(self, state): # for pickle self.setstate(state) + def jumpahead(self, n): + """Act as if n calls to random() were made, but quickly. + + n is an int, greater than or equal to 0. + + Example use: If you have 2 threads and know that each will + consume no more than a million random numbers, create two Random + objects r1 and r2, then do + r2.setstate(r1.getstate()) + r2.jumpahead(1000000) + Then r1 and r2 will use guaranteed-disjoint segments of the full + period. + """ + + if not n >= 0: + raise ValueError("n must be >= 0") + x, y, z = self._seed + x = int(x * pow(171, n, 30269)) % 30269 + y = int(y * pow(172, n, 30307)) % 30307 + z = int(z * pow(170, n, 30323)) % 30323 + self._seed = x, y, z + def random(self): """Get the next random number in the range [0.0, 1.0).""" @@ -471,6 +493,17 @@ def _test_generator(n, funccall): print 'avg %g, stddev %g, min %g, max %g' % \ (avg, stddev, smallest, largest) + s = getstate() + N = 1019 + jumpahead(N) + r1 = random() + setstate(s) + for i in range(N): # now do it the slow way + random() + r2 = random() + if r1 != r2: + raise ValueError("jumpahead test failed " + `(N, r1, r2)`) + def _test(N=200): print 'TWOPI =', TWOPI print 'LOG4 =', LOG4 @@ -515,6 +548,7 @@ paretovariate = _inst.paretovariate weibullvariate = _inst.weibullvariate getstate = _inst.getstate setstate = _inst.setstate +jumpahead = _inst.jumpahead if __name__ == '__main__': _test() diff --git a/Misc/NEWS b/Misc/NEWS index 058d55c..def0dd3 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -8,7 +8,12 @@ Standard library - random.py is now self-contained, and offers all the functionality of the now-deprecated whrandom.py. See the docs for details. random.py also supports new functions getstate() and setstate(), for saving - and restoring the internal state of all the generators. + and restoring the internal state of the generator; and jumpahead(n), + for quickly forcing the internal state to be the same as if n calls to + random() had been made. The latter is particularly useful for multi- + threaded programs, creating one instance of the random.Random() class for + each thread, then using .jumpahead() to force each instance to use a + non-overlapping segment of the full period. What's New in Python 2.1 alpha 1? @@ -107,12 +112,12 @@ Core language, builtins, and interpreter a complicated (but still thread-safe) method using fgets() is used by default. - You can force use of the fgets() method by #define'ing - USE_FGETS_IN_GETLINE at build time (it may be faster than + You can force use of the fgets() method by #define'ing + USE_FGETS_IN_GETLINE at build time (it may be faster than getc_unlocked()). - You can force fgets() not to be used by #define'ing - DONT_USE_FGETS_IN_GETLINE (this is the first thing to try if std test + You can force fgets() not to be used by #define'ing + DONT_USE_FGETS_IN_GETLINE (this is the first thing to try if std test test_bufio.py fails -- and let us know if it does!). - In addition, the fileinput module, while still slower than the other -- cgit v0.12