Package it.unimi.dsi.util
Miscellaneaous utility classes.
Pseudorandom number generators
We provide a number of fast, highquality PRNGs with different features. You can get detailed information about the generators at our PRNG page, together with a reasoned guide to the choice of the generator that's right for you.
A table summarizing timings is provided below. The timings were measured on an
Intel® Core™ i78700B CPU @3.20GHz using
JMH microbenchmarks. The JMH timings were decreased by 1ns, as
using the lowlevel perfasm
profiler the JMH overhead was estimated at ≈1ns per call.
Random
 ThreadLocalRandom
 SplittableRandom
 SplitMix64







 

nextLong()  14.419  1.252  1.283  1.241  1.428  1.574  1.295  1.738  1.884  1.653  1.901 
nextInt(100000)  6.715  2.045  2.499  2.543  2.336  2.594  1.202  2.607  2.954  2.367  3.119 
nextDouble()  14.458  1.876  2.161  2.176  1.918  2.219  1.853  2.304  2.503  2.112  2.755 
Note that generators that are extremely fast in C, such as xoshiro256+
, do not perform particularly well in Java, most likely
because of the cost of accessing variables, which rises as the size of the state space grows. Indeed,
smallerstate generators are faster. Moreover, generators based on the ++
scrambler are slightly faster than those based on the **
scrambler, contrarily to what happens in C.
For each generator, we provide a version that extends Random
, overriding (as usual) the next(int)
method. Nonetheless,
since the generators are all inherently 64bit also nextInt()
, nextFloat()
,
nextLong()
, nextDouble()
, nextBoolean()
and nextBytes(byte[])
have been overridden for speed (preserving, of course, Random
's semantics).
If you do not need an instance of Random
, or if you need a RandomGenerator
to use
with Commons Math, there is for each generator a corresponding RandomGenerator
implementation, which indeed we suggest to use in general if you do not need a generator implementing Random
.

Interface Summary Interface Description PrefixMap<S extends CharSequence> A map from prefixes to string intervals (and possibly vice versa).StringMap<S extends CharSequence> A map from strings to numbers (and possibly vice versa). 
Class Summary Class Description AbstractPrefixMap An abstract implementation of a prefix map.BloomFilter<T> A Bloom filter.ByteBufferLongBigList A bridge between byte buffers and long big lists.CircularCharArrayBuffer A circular char buffer that can be used to implement a sliding window over a text.FrontCodedStringList Compact storage of strings using frontcoding compression (a.k.a. compression by prefix omission).HyperLogLogCounterArray An array of approximate sets each represented using a HyperLogLog counter.ImmutableBinaryTrie<T> An immutable implementation of binary tries.ImmutableBinaryTrie.Node A node in the trie.ImmutableExternalPrefixMap An immutable prefix map mostly stored in external memory.Interval An interval of integers.Intervals A class providing static methods and objects that do useful things with intervals.IntParallelCounterArray An array of approximate sets each represented using a Parallel counter.KahanSummation Kahan's summation algorithm encapsulated in an object.LiterallySignedStringMap A string map based on a function signed using the original list of strings.LongInterval An interval of longs.LongIntervals A class providing static methods and objects that do useful things with intervals.PermutedFrontCodedStringList AFrontCodedStringList
whose indices are permuted.Properties An extension ofPropertiesConfiguration
providing setters for primitive types, a simpler way to save preferences and transparent handling ofEnum
lowercased keys.SemiExternalGammaList Provides semiexternal random access to a list of γencoded integers.ShiftAddXorSignedStringMap Deprecated. There are much better and faster hash functions.SplitMix64Random A fast, highquality, nonsplittable version of the SplitMix pseudorandom number generator used bySplittableRandom
.SplitMix64RandomGenerator A fast, highquality, nonsplittable version of the SplitMix pseudorandom number generator used bySplittableRandom
.StringMaps A class providing static methods and objects that do useful things with string maps and prefix maps.StringMaps.SynchronizedPrefixMap<S extends CharSequence> StringMaps.SynchronizedStringMap<S extends CharSequence> TernaryIntervalSearchTree Ternary interval search trees.TextPattern QuickSearch matching against a constant string.XorGensRandomGenerator A fast, highquality 64bit pseudorandom number generator described in “Some longperiod random number generators using shift and xors”, ANZIAM Journal 48, C188−C202, 2007.XoRoShiRo128PlusPlusRandom A fast, allpurpose, rocksolid, smallstate pseudorandom number generator.XoRoShiRo128PlusPlusRandomGenerator A fast, allpurpose, rocksolid, smallstate pseudorandom number generator.XoRoShiRo128PlusRandom A fast, highquality pseudorandom number generator for floatingpoint generation.XoRoShiRo128PlusRandomGenerator A fast, highquality pseudorandom number generator for floatingpoint generation.XoRoShiRo128StarStarRandom A fast, allpurpose, rocksolid, smallstate pseudorandom number generator.XoRoShiRo128StarStarRandomGenerator A fast, allpurpose, rocksolid, smallstate pseudorandom number generator.XorShift1024StarPhiRandom A fast, highquality pseudorandom number generator that combines a longperiod instance of George Marsaglia's Xorshift generators (described in “Xorshift RNGs”, Journal of Statistical Software, 8:1−6, 2003) with a multiplication.XorShift1024StarPhiRandomGenerator A fast, highquality pseudorandom number generator that combines a longperiod instance of George Marsaglia's Xorshift generators (described in “Xorshift RNGs”, Journal of Statistical Software, 8:1−6, 2003) with a multiplication.XorShift1024StarRandom Deprecated. Please useXorShift1024StarPhiRandom
instead.XorShift1024StarRandomGenerator Deprecated. Please useXorShift1024StarPhiRandomGenerator
instead.XorShift128PlusRandom Deprecated. Please useXoRoShiRo128PlusRandom
instead.XorShift128PlusRandomGenerator Deprecated. Please useXoRoShiRo128PlusRandomGenerator
instead.XorShift64StarRandom Deprecated. UseSplitMix64Random
instead.XorShift64StarRandomGenerator Deprecated. UseSplitMix64RandomGenerator
instead.XoShiRo256PlusPlusRandom A fast, allpurpose, rocksolid pseudorandom number generator.XoShiRo256PlusPlusRandomGenerator A fast, allpurpose, rocksolid pseudorandom number generator.XoShiRo256PlusRandom A fast, rocksolid pseudorandom number generator for floatingpoint generation.XoShiRo256PlusRandomGenerator A fast, rocksolid pseudorandom number generator for floatingpoint generation.XoShiRo256StarStarRandom A fast, allpurpose, rocksolid pseudorandom number generator.XoShiRo256StarStarRandomGenerator A fast, allpurpose, rocksolid pseudorandom number generator.