Package elki.utilities.random

Class FastNonThreadsafeRandom

  • All Implemented Interfaces:
    java.io.Serializable
    public class FastNonThreadsafeRandom
extends java.util.Random
    Drop-in replacement for Random, but not using atomic long seeds. This implementation is no longer thread-safe (but faster)!

    It is still the same Linear Congruential Generator (LCG), with a cycle length of 248, of which we only use 32 bits at a time. Given the same seed, it is expected to produce the exact same random sequence as Java's Random, given the same seed. Which implies that you need to randomize your seeds with a better random source.

    Since:
    0.6.0
    Author:
    Erich Schubert
    See Also:
    Serialized Form

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static long addend  
      protected static java.lang.String BADBOUND
      Exception message for non-positive bounds
      private static long mask  
      private static long multiplier  
      private long seed
      The random seed.
      private static long serialVersionUID
      Serial version number.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected int next​(int bits)  
      double nextDouble()  
      int nextInt()  
      int nextInt​(int n)
      Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.
      int nextIntRefined​(int n)
      Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.
      void setSeed​(long seed)  

      • Methods inherited from class java.util.Random

        doubles, doubles, doubles, doubles, ints, ints, ints, ints, longs, longs, longs, longs, nextBoolean, nextBytes, nextFloat, nextGaussian, nextLong

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • FastNonThreadsafeRandom

        public FastNonThreadsafeRandom()
        Constructor called only by localRandom.initialValue.

      • FastNonThreadsafeRandom

        public FastNonThreadsafeRandom​(long seed)
        Constructor.
        Parameters:
        seed - Random generator seed.

    • Method Detail

      • setSeed

        public void setSeed​(long seed)
        Overrides:
        setSeed in class java.util.Random

      • next

        protected int next​(int bits)
        Overrides:
        next in class java.util.Random

      • nextInt

        public int nextInt()
        Overrides:
        nextInt in class java.util.Random

      • nextDouble

        public double nextDouble()
        Overrides:
        nextDouble in class java.util.Random

      • nextInt

        @Reference(authors="D. Lemire",title="Fast random shuffling",booktitle="Daniel Lemire\'s blog",url="http://lemire.me/blog/2016/06/30/fast-random-shuffling/",bibkey="blog/Lemire16") @Reference(authors="D. Lemire",title="Fast Random Integer Generation in an Interval",booktitle="ACM Trans. Model. Comput. Simul. 29(1)",url="https://doi.org/10.1145/3230636",bibkey="DBLP:journals/tomacs/Lemire19")
public int nextInt​(int n)
        Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

        This version mostly does this - except for very large n. In such cases, it may be better to use nextIntRefined(int) instead, which uses a rejection sampling technique to further reduce the bias.

        In contrast to the Java version, we use an approach that tries to avoid divisions for performance. We will have a slightly worse distribution in this fast version (see the XorShift generators for higher quality with rejection sampling) discussed in:

        D. Lemire
        Fast random shuffling
        http://lemire.me/blog/2016/06/30/fast-random-shuffling/

        D. Lemire
        Fast Random Integer Generation in an Interval
        ACM Trans. Model. Comput. Simul. 29(1)

        Overrides:
        nextInt in class java.util.Random

      • nextIntRefined

        @Reference(authors="D. Lemire",title="Fast random shuffling",booktitle="Daniel Lemire\'s blog",url="http://lemire.me/blog/2016/06/30/fast-random-shuffling/",bibkey="blog/Lemire16") @Reference(authors="D. Lemire",title="Fast Random Integer Generation in an Interval",booktitle="ACM Trans. Model. Comput. Simul. 29(1)",url="https://doi.org/10.1145/3230636",bibkey="DBLP:journals/tomacs/Lemire19")
public int nextIntRefined​(int n)
        Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability.

        In contrast to the Java version, we use an approach that tries to avoid divisions for performance. In this method, we also employ rejection sampling (for marginal improvement) as discussed in:

        D. Lemire
        Fast random shuffling
        http://lemire.me/blog/2016/06/30/fast-random-shuffling/

        D. Lemire
        Fast Random Integer Generation in an Interval
        ACM Trans. Model. Comput. Simul. 29(1)

        In our experiments, the difference was negligible, as the rejections are quite rare events at least for our use case.