Intro
Suppose we throw a die \$N\$ times. Before writing this program, I was puzzled by a question: How should I approach each trial. I got two options:
- Choose a single die number, count how many times the die comes up with that number,
- On each toss of a die, choose the desired number and compare to the actual one.
My a priori assumptions was that 1 produces more successful guesses than 2, but it turned out that there is no significant statistical difference.
As additional fun, I have parallelized the computation for \$N \geq 65536\$.
Code
io.github.coderodde.simulation.dice.AbstractDiceSimulation.java:
package io.github.coderodde.simulation.dice;
import java.util.Objects;
import java.util.Random;
/**
* This class specifies the common facilities for distinct dice simulations.
*/
public abstract class AbstractDiceSimulation {
/**
* The number of dice numbers.
*/
public static final int NUMBER_OF_DICE = 6;
/**
* The minimum number of trials to perform on a concurrent worker.
*/
public static final int MINIMUM_WORKER_SIZE = 65_536;
/**
* Keeps the track of actual counters.
*/
protected final int[] counters = new int[NUMBER_OF_DICE];
/**
* The random number generator.
*/
protected final Random random;
/**
* The number of trials.
*/
protected int trials;
/**
* The number of successful matches.
*/
protected int successes;
/**
* Caches the dice counters object.
*/
protected DiceCounters diceCounters;
/**
* Constructs this class.
*
* @param random the input random number generator.
* @param trials the number of dice tosses (i.e., trials):
*/
public AbstractDiceSimulation(Random random, int trials) {
this.random = Objects.requireNonNull(random,
"The input random is null");
this.trials = checkTrials(trials);
}
/**
* Returns the number of successful trials.
* @return the number of successful trials.
*/
public int getNumberOfSuccessfulTrials() {
return successes;
}
/**
* Gets the counters object. Constructs a singleton if not yet constructed.
*
* @return the counters object.
*/
public DiceCounters getCounters() {
if (diceCounters == null) {
diceCounters = new DiceCounters(this.counters);
}
return diceCounters;
}
/**
* Runs the actual simulation.
*/
public abstract void simulate();
/**
* Generates a die.
*
* @return a die number.
*/
protected int generateDie(Random random) {
return random.nextInt(NUMBER_OF_DICE) + 1;
}
/**
* Checks that the trials parameter within reasonable range.
*
* @param trials the trial parameter to check.
*
* @return the input trial for the sake of assignment of the result of this
* method straight to the trials field.
*/
private static int checkTrials(int trials) {
if (trials < 0) {
throw new IllegalArgumentException(
String.format(
"trials(%d) < 0",
trials));
}
return trials;
}
}
io.github.coderodde.simulation.dice.ConstantDiceSimulation.java:
package io.github.coderodde.simulation.dice;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
/**
* This class models a dice simulator that chooses a constant die number and
* compares all the trial results to it.
*/
public class ConstantDiceSimulation extends AbstractDiceSimulation {
private final class DieWorker extends RecursiveTask<DiceCounters> {
private final int trialsToGenerate;
private final int constant;
private final int[] counters = new int[NUMBER_OF_DICE];
private final Random random;
private int successes;
DieWorker(int trialsToGenerate,
int constant,
Random random) {
this.trialsToGenerate = trialsToGenerate;
this.constant = constant;
this.random = random;
}
public int getSuccesses() {
return successes;
}
@Override
protected DiceCounters compute() {
for (int i = 0; i < trialsToGenerate; ++i) {
int die = generateDie(random);
if (die == constant) {
successes++;
}
counters[die - 1]++;
}
return new DiceCounters(counters);
}
}
/**
* Constructs this simulator.
*
* @param random the random number generator.
* @param trials the number of trials to perform.
*/
public ConstantDiceSimulation(Random random, int trials) {
super(random, trials);
}
/**
* {@inheritDoc }.
*/
@Override
public void simulate() {
int constant = generateDie(random);
int workers = trials / MINIMUM_WORKER_SIZE;
if (workers < 2) {
sequentialSimulate();
} else {
ForkJoinPool pool = ForkJoinPool.commonPool();
List<DieWorker> tasks =
splitIntoTasks(
trials,
workers,
constant);
for (DieWorker t : tasks) {
pool.execute(t);
}
DiceCounters joined =
new DiceCounters(new int[]{ 0, 0, 0, 0, 0, 0 });
int successes = 0;
for (DieWorker t : tasks) {
DiceCounters dc = t.join();
joined = joined.join(dc);
successes += t.getSuccesses();
}
this.diceCounters = joined;
this.successes = successes;
}
}
private List<DieWorker> splitIntoTasks(int trials,
int workers,
int constant) {
List<DieWorker> tasks = new ArrayList<>(workers);
int basicTrials = trials / workers;
int lastTrials = trials - trials / workers;
for (int i = 0; i < workers - 1; ++i) {
tasks.add(new DieWorker(basicTrials,
constant,
new Random(random.nextLong())));
}
tasks.add(new DieWorker(lastTrials,
constant,
new Random(random.nextLong())));
return tasks;
}
private void sequentialSimulate() {
int constant = generateDie(random);
for (int i = 0; i < trials; ++i) {
int trial = generateDie(random);
counters[trial - 1]++;
if (trial == constant) {
successes++;
}
}
}
}
io.github.coderodde.simulation.dice.Demo.java:
package io.github.coderodde.simulation.dice;
import java.util.Random;
public class Demo {
private static final int NUMBER_OF_TRIALS = 100_000;
public static void main(String[] args) {
long seed = System.currentTimeMillis();
Random random1 = new Random(seed);
Random random2 = new Random(seed);
System.out.println("Seed = " + seed);
for (int trials = 16; trials <= (1 << 26); trials <<= 1) {
System.out.printf("N = %6d:\n", trials);
AbstractDiceSimulation sim1 =
new ConstantDiceSimulation(random1, trials);
AbstractDiceSimulation sim2 =
new VaryingDiceSimulation(random2, trials);
long ta = System.currentTimeMillis();
sim1.simulate();
long tb = System.currentTimeMillis();
long duration1 = tb - ta;
ta = System.currentTimeMillis();
sim2.simulate();
tb = System.currentTimeMillis();
long duration2 = tb - ta;
System.out.printf(
" constant -- %d, counters: %s, duration: %d ms.\n",
sim1.getNumberOfSuccessfulTrials(),
sim1.getCounters(),
duration1);
System.out.printf(
" varying -- %s, counters: %s, duration: %d ms.\n",
sim2.getNumberOfSuccessfulTrials(),
sim2.getCounters(),
duration2);
float constantVaryingRatio =
(float)(sim1.getNumberOfSuccessfulTrials()) /
(float)(sim2.getNumberOfSuccessfulTrials());
System.out.printf( "Constant/varying ratio: %f\n",
constantVaryingRatio);
}
}
}
io.github.coderodde.simulation.dice.DiceCounters.java:
package io.github.coderodde.simulation.dice;
/**
* This class models the dice counters when simulating.
*/
public class DiceCounters {
/**
* The actual counter data.
*/
private final int[] counters;
/**
* Constructs this dice counter.
*
* @param rawCounters the actual counter array.
*/
DiceCounters(int[] counters) {
this.counters = new int[AbstractDiceSimulation.NUMBER_OF_DICE];
System.arraycopy(counters,
0,
this.counters,
0,
counters.length);
}
/**
* Access a counter at a particular index. Die number 1 corresponds to the
* {@code 0th} index, and so on.
*
* @param index the index of the desired counter.
*
* @return the desired counter.
*/
public int getCounter(int index) {
return counters[index];
}
/**
* Sets fast the number without any sanity check.
*
* @param index the index of the desired counter. Indexing starts from 0.
* @param number the new counter.
*/
void setCounter(int index, int number) {
counters[index] = number;
}
public DiceCounters join(DiceCounters dc) {
DiceCounters result = new DiceCounters(this.counters);
for (int i = 0; i < AbstractDiceSimulation.NUMBER_OF_DICE; ++i) {
result.setCounter(i, dc.getCounter(i));
}
return result;
}
/**
* Converts this dice counter to a string.
*
* @return the string representation of this counter object.
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
boolean first = true;
for (int number = 1;
number <= AbstractDiceSimulation.NUMBER_OF_DICE;
number++) {
if (first) {
first = false;
} else {
sb.append(", ");
}
sb.append(number)
.append(": ")
.append(getCounter(number - 1));
}
return sb.append("]").toString();
}
}
io.github.coderodde.simulation.dice.VaryingDiceSimulation.java:
package io.github.coderodde.simulation.dice;
import static io.github.coderodde.simulation.dice.AbstractDiceSimulation.MINIMUM_WORKER_SIZE;
import static io.github.coderodde.simulation.dice.AbstractDiceSimulation.NUMBER_OF_DICE;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
/**
* This class models a dice simulator that chooses a constant die number and
* compares all the trial results to it.
*/
public class VaryingDiceSimulation extends AbstractDiceSimulation {
private final class DieWorker extends RecursiveTask<DiceCounters> {
private final int trialsToGenerate;
private final int[] counters = new int[NUMBER_OF_DICE];
private final Random random;
private int successes;
DieWorker(int trialsToGenerate,
Random random) {
this.trialsToGenerate = trialsToGenerate;
this.random = random;
}
public int getSuccesses() {
return successes;
}
@Override
protected DiceCounters compute() {
for (int i = 0; i < trialsToGenerate; ++i) {
int constant = generateDie(random);
int die = generateDie(random);
if (die == constant) {
successes++;
}
counters[die - 1]++;
}
return new DiceCounters(counters);
}
}
/**
* Constructs this simulator.
*
* @param random the random number generator.
* @param trials the number of trials to perform.
*/
public VaryingDiceSimulation(Random random, int trials) {
super(random, trials);
}
/**
* {@inheritDoc }.
*/
@Override
public void simulate() {
int workers = trials / MINIMUM_WORKER_SIZE;
if (workers < 2) {
sequentialSimulate();
} else {
ForkJoinPool pool = ForkJoinPool.commonPool();
List<DieWorker> tasks =
splitIntoTasks(
trials,
workers);
for (DieWorker t : tasks) {
pool.execute(t);
}
DiceCounters joined =
new DiceCounters(new int[]{ 0, 0, 0, 0, 0, 0 });
int successes = 0;
for (DieWorker t : tasks) {
DiceCounters dc = t.join();
joined = joined.join(dc);
successes += t.getSuccesses();
}
this.diceCounters = joined;
this.successes = successes;
}
}
private List<DieWorker> splitIntoTasks(int trials,
int workers) {
List<DieWorker> tasks = new ArrayList<>(workers);
int basicTrials = trials / workers;
int lastTrials = trials - trials / workers;
for (int i = 0; i < workers - 1; ++i) {
tasks.add(new DieWorker(basicTrials,
new Random(random.nextLong())));
}
tasks.add(new DieWorker(lastTrials,
new Random(random.nextLong())));
return tasks;
}
private void sequentialSimulate() {
int constant = generateDie(random);
for (int i = 0; i < trials; ++i) {
int trial = generateDie(random);
counters[trial - 1]++;
if (trial == constant) {
successes++;
}
}
}
}
Typical output
Seed = 1769855066473
N = 16:
constant -- 1, counters: [1: 3, 2: 2, 3: 2, 4: 1, 5: 3, 6: 5], duration: 0 ms.
varying -- 5, counters: [1: 3, 2: 2, 3: 2, 4: 1, 5: 3, 6: 5], duration: 0 ms.
Constant/varying ratio: 0,200000
N = 32:
constant -- 0, counters: [1: 4, 2: 8, 3: 6, 4: 0, 5: 10, 6: 4], duration: 0 ms.
varying -- 1, counters: [1: 4, 2: 8, 3: 6, 4: 1, 5: 9, 6: 4], duration: 0 ms.
Constant/varying ratio: 0,000000
N = 64:
constant -- 12, counters: [1: 8, 2: 12, 3: 12, 4: 9, 5: 13, 6: 10], duration: 1 ms.
varying -- 11, counters: [1: 7, 2: 11, 3: 13, 4: 9, 5: 14, 6: 10], duration: 0 ms.
Constant/varying ratio: 1,090909
N = 128:
constant -- 17, counters: [1: 15, 2: 29, 3: 17, 4: 25, 5: 28, 6: 14], duration: 0 ms.
varying -- 14, counters: [1: 14, 2: 30, 3: 17, 4: 24, 5: 27, 6: 16], duration: 0 ms.
Constant/varying ratio: 1,214286
N = 256:
constant -- 45, counters: [1: 43, 2: 30, 3: 40, 4: 49, 5: 45, 6: 49], duration: 0 ms.
varying -- 40, counters: [1: 43, 2: 30, 3: 40, 4: 51, 5: 44, 6: 48], duration: 0 ms.
Constant/varying ratio: 1,125000
N = 512:
constant -- 82, counters: [1: 99, 2: 87, 3: 69, 4: 85, 5: 90, 6: 82], duration: 0 ms.
varying -- 90, counters: [1: 100, 2: 87, 3: 67, 4: 85, 5: 90, 6: 83], duration: 0 ms.
Constant/varying ratio: 0,911111
N = 1024:
constant -- 162, counters: [1: 194, 2: 162, 3: 175, 4: 159, 5: 142, 6: 192], duration: 0 ms.
varying -- 192, counters: [1: 194, 2: 162, 3: 175, 4: 158, 5: 143, 6: 192], duration: 0 ms.
Constant/varying ratio: 0,843750
N = 2048:
constant -- 336, counters: [1: 336, 2: 340, 3: 320, 4: 362, 5: 360, 6: 330], duration: 1 ms.
varying -- 322, counters: [1: 336, 2: 340, 3: 322, 4: 362, 5: 360, 6: 328], duration: 0 ms.
Constant/varying ratio: 1,043478
N = 4096:
constant -- 694, counters: [1: 691, 2: 669, 3: 669, 4: 716, 5: 694, 6: 657], duration: 0 ms.
varying -- 716, counters: [1: 689, 2: 670, 3: 668, 4: 716, 5: 697, 6: 656], duration: 0 ms.
Constant/varying ratio: 0,969274
N = 8192:
constant -- 1415, counters: [1: 1415, 2: 1342, 3: 1400, 4: 1324, 5: 1346, 6: 1365], duration: 1 ms.
varying -- 1365, counters: [1: 1420, 2: 1340, 3: 1400, 4: 1324, 5: 1343, 6: 1365], duration: 1 ms.
Constant/varying ratio: 1,036630
N = 16384:
constant -- 2661, counters: [1: 2740, 2: 2794, 3: 2732, 4: 2705, 5: 2752, 6: 2661], duration: 1 ms.
varying -- 2661, counters: [1: 2738, 2: 2796, 3: 2733, 4: 2704, 5: 2752, 6: 2661], duration: 2 ms.
Constant/varying ratio: 1,000000
N = 32768:
constant -- 5405, counters: [1: 5488, 2: 5527, 3: 5343, 4: 5509, 5: 5405, 6: 5496], duration: 4 ms.
varying -- 5408, counters: [1: 5487, 2: 5526, 3: 5342, 4: 5507, 5: 5408, 6: 5498], duration: 3 ms.
Constant/varying ratio: 0,999445
N = 65536:
constant -- 11092, counters: [1: 10809, 2: 10957, 3: 11092, 4: 10811, 5: 10913, 6: 10954], duration: 2 ms.
varying -- 10809, counters: [1: 10809, 2: 10959, 3: 11092, 4: 10813, 5: 10911, 6: 10952], duration: 1 ms.
Constant/varying ratio: 1,026182
N = 131072:
constant -- 21940, counters: [1: 10941, 2: 11080, 3: 10919, 4: 10830, 5: 10912, 6: 10854], duration: 20 ms.
varying -- 22120, counters: [1: 10981, 2: 10806, 3: 11013, 4: 10966, 5: 10827, 6: 10943], duration: 15 ms.
Constant/varying ratio: 0,991863
N = 262144:
constant -- 65602, counters: [1: 32736, 2: 32881, 3: 32681, 4: 32818, 5: 32815, 6: 32677], duration: 22 ms.
varying -- 65607, counters: [1: 32787, 2: 32857, 3: 32732, 4: 32624, 5: 32788, 6: 32820], duration: 10 ms.
Constant/varying ratio: 0,999924
N = 524288:
constant -- 152458, counters: [1: 76360, 2: 76341, 3: 76577, 4: 76672, 5: 76326, 6: 76476], duration: 8 ms.
varying -- 153269, counters: [1: 76271, 2: 76541, 3: 76464, 4: 76261, 5: 76539, 6: 76676], duration: 15 ms.
Constant/varying ratio: 0,994709
N = 1048576:
constant -- 327915, counters: [1: 164167, 2: 164013, 3: 163676, 4: 163863, 5: 163652, 6: 163669], duration: 19 ms.
varying -- 327449, counters: [1: 163891, 2: 164040, 3: 163623, 4: 163371, 5: 164134, 6: 163981], duration: 29 ms.
Constant/varying ratio: 1,001423
N = 2097152:
constant -- 676608, counters: [1: 339359, 2: 338642, 3: 338074, 4: 338887, 5: 338374, 6: 338280], duration: 35 ms.
varying -- 676599, counters: [1: 338537, 2: 338783, 3: 338603, 4: 338737, 5: 338863, 6: 338093], duration: 56 ms.
Constant/varying ratio: 1,000013
N = 4194304:
constant -- 1375065, counters: [1: 689811, 2: 688558, 3: 688333, 4: 688428, 5: 686202, 6: 687436], duration: 70 ms.
varying -- 1376126, counters: [1: 689146, 2: 687889, 3: 686772, 4: 688244, 5: 688609, 6: 688108], duration: 111 ms.
Constant/varying ratio: 0,999229
N = 8388608:
constant -- 2772716, counters: [1: 1385947, 2: 1386165, 3: 1387981, 4: 1386985, 5: 1387542, 6: 1388452], duration: 133 ms.
varying -- 2772434, counters: [1: 1383864, 2: 1389245, 3: 1389396, 4: 1385523, 5: 1388360, 6: 1386684], duration: 218 ms.
Constant/varying ratio: 1,000102
N = 16777216:
constant -- 5572704, counters: [1: 2783884, 2: 2785647, 3: 2786877, 4: 2785790, 5: 2785052, 6: 2784430], duration: 260 ms.
varying -- 5569827, counters: [1: 2784207, 2: 2784787, 3: 2783071, 4: 2785883, 5: 2788610, 6: 2785122], duration: 510 ms.
Constant/varying ratio: 1,000517
N = 33554432:
constant -- 11163895, counters: [1: 5582839, 2: 5584627, 3: 5579002, 4: 5580326, 5: 5582633, 6: 5579469], duration: 608 ms.
varying -- 11159203, counters: [1: 5585032, 2: 5581800, 3: 5578147, 4: 5578288, 5: 5581298, 6: 5584331], duration: 956 ms.
Constant/varying ratio: 1,000420
N = 67108864:
constant -- 22344746, counters: [1: 11170190, 2: 11169194, 3: 11175723, 4: 11175852, 5: 11175740, 6: 11176629], duration: 1164 ms.
varying -- 22348768, counters: [1: 11175380, 2: 11175514, 3: 11173028, 4: 11172265, 5: 11173271, 6: 11173870], duration: 1940 ms.
Constant/varying ratio: 0,999820
On larger \$N\$, the approach 2. takes almost twice as much time as 1. This is not a coincidence as 2 calls Random twice and 2 only once.
Critique request
Please, feel free to break my program into pieces.
