0

In Java, how long relative to a simple arithmetic operation does it take Math.random() to generate a number? I am trying to randomly distribute objects in an ArrayList that already contains values such that a somewhat even, but not completely even distribution is created, and I am not sure if choosing a random index for every insertion point by using Math.random() is the best approach to take.

Clarification: the distribution of inserted objects is meant to be even enough that the values are not all concentrated in one area, but also uneven enough that the distribution is not predictable (if someone were to go through the values one by one, they would not be able to determine if the next value was going to be a newly inserted value by detecting a constant pattern).

Daniel
  • 1,599
  • 1
  • 16
  • 19
  • Math.random() gives you a random location.. So "somewhat" even is not going to happen every single time... If you want a consistent output (evenly distributed)\ you should create your own operation... – DarkV1 Jul 23 '16 at 21:23
  • 2
    Just benchmark it! It's way slower than one add, but fast enough to sample many times. If you need more than 1 random sample, it's faster to call for these all at once (e.g. creating a random-pool). I don't know what you are doing, but i suspect there are more algorithmic problems here. Example: it's hard to implement a correct shuffle. – sascha Jul 23 '16 at 21:23
  • 2
    Generating a random value (through Math.random) is a fairly common operation and you should not worry about it without very good reason too. It looks like premature optimization. What other approachs do you consider? – zoom Jul 23 '16 at 21:25
  • I'm not just doing a shuffle: the ArrayList already contains values, and I want to add new ones so that they aren't all inserted in one area but also aren't spread evenly enough to be predictable. – Daniel Jul 23 '16 at 21:25
  • Describe your problem-setting more as i suspect that there are some *problems*. What does predicable mean for example. Even if using completely random operations, you could always recalculate the exact positions, because each RNG is deterministic. – sascha Jul 23 '16 at 21:27
  • 1
    Random is your best bet in that case.... Although there will always be a chance that it isnt distributed evenly.. you can control it with a conditional to re-roll a different index if it is too close to the other indexes – DarkV1 Jul 23 '16 at 21:28
  • Use uniformly sampled positions (without further constraints). This is the best against information-gain by some attacker (guesser). – sascha Jul 23 '16 at 21:32
  • In my case, uniformly sampled positions would not work. – Daniel Jul 23 '16 at 21:33
  • Then explain why! Be more precise and formal. Everything other than uniform-sampling is easier to attack (predict). That's a proven fact! – sascha Jul 23 '16 at 21:34
  • This is not to prevent attackers. I am generating quizzes and I want a certain percentage to be of a specific type. However, if they were this type at a specific interval, then the answer would be too predictable. – Daniel Jul 23 '16 at 21:35
  • If you have questions of type A, B, and C, shuffle each of the sets independently and then pick the desired number from the front of each of the shuffled sets. You'll get the target mix of questions, but the actual questions will be randomized. If you want, you can then shuffle the assembled quiz. I like to shuffle the answers on multiple choice questions as well. The random aspects of this are inconsequential, a well-written program will generate the end result "instantaneously" by human standards. – pjs Jul 23 '16 at 21:54
  • 1
    Unless you want to shuffle an array of millions of questions, this is not performance critical. Consider that during the time that the sound waves of the mouse click take to travel from the mouse to the ear of the person who clicked the button, the computer could create thousands (if not millions) of random numbers. Regardless of that: **I'd recommend to NOT use `Math.random()` AT ALL**. In most cases, a dedicated `Random` instance is more versatile (and easier to debug). – Marco13 Jul 24 '16 at 01:31

3 Answers3

4

Do not use Math.random. It relies on a global instance of java.util.Random that uses AtomicLong under the hood. Though the PRNG algorithm used in java.util.Random is pretty simple, the performance is mostly affected by the atomic CAS and the related cache-coherence traffic.

This can be particularly bad for multithread appliсations (like in this example), but has also a penalty even in a single-threaded case.

ThreadLocalRandom is always preferable to Math.random. It does not rely on atomic operations and does not suffer from contention. It only updates a thread-local state and uses a couple of arithmetic and bitwise operations.

Here is a JMH benchmark to compare the performance of Math.random() and ThreadLocalRandom.current().nextDouble() to a simple arithmetic operation.

package bench;

import org.openjdk.jmh.annotations.*;
import java.util.concurrent.ThreadLocalRandom;

@State(Scope.Thread)
public class RandomBench {
    double x = 1;

    @Benchmark
    public double multiply() {
        return x * Math.PI;
    }

    @Benchmark
    public double mathRandom() {
        return Math.random();
    }

    @Benchmark
    public double threadLocalRandom() {
        return ThreadLocalRandom.current().nextDouble();
    }
}

The results show that ThreadLocalRandom works in just a few nanoseconds, its performance is comparable to a simple arithmetic operation and perfectly scales in multithreaded environment unlike Math.random.

Benchmark                      Threads     Score     Error  Units
RandomBench.mathRandom            1       34.265 ±   1.709  ns/op
RandomBench.multiply              1        4.531 ±   0.108  ns/op
RandomBench.threadLocalRandom     1        8.322 ±   0.047  ns/op

RandomBench.mathRandom            2      366.589 ±  63.899  ns/op
RandomBench.multiply              2        4.627 ±   0.118  ns/op
RandomBench.threadLocalRandom     2        8.342 ±   0.079  ns/op

RandomBench.mathRandom            4     1328.472 ± 177.216  ns/op
RandomBench.multiply              4        4.592 ±   0.091  ns/op
RandomBench.threadLocalRandom     4        8.474 ±   0.157  ns/op
Community
  • 1
  • 1
apangin
  • 92,924
  • 10
  • 193
  • 247
2

Java documentations report this as the implementation for Random.nextDouble(), which is what Math.random() ends up invoking.

 public double nextDouble() {
   return (((long)next(26) << 27) + next(27))
     / (double)(1L << 53);
 }

Where next updates the seed to (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1) and returns (int)(seed >>> (48 - bits)).

As you can see it uses a simple algorithm to generate pseudo-random values. It requires just a few cheap operations and so I wouldn't worry about using it.

mariosangiorgio
  • 5,520
  • 4
  • 32
  • 46
  • 1
    Though the algorithm is pretty simple, its performance is affected by the [atomic CAS](http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a11ab21bb799/src/share/classes/java/util/Random.java#l200) which has a performance penalty even in a single-threaded application, not to mention possible contention in multithreaded case. – apangin Jul 24 '16 at 01:16
1

Creating a random number is a simple operation, you shouldn't worry about it.

But you should keep in mind several things

  • It is better to reuse Random instance, creating new Random() instance every time you need a random value usually is a bad decision.

  • But do not use the same Random instance across several threads simultaneously to avoid contention, you can use ThreadLocalRandom.current() instead.

  • If you do dome cryptography use SecureRandom instead.

SerCe
  • 5,826
  • 2
  • 32
  • 53