I wanted a data structure that allowed me to set the chances of randomly returning each of it's elements.
For example, suppose I have a Human class. Every Human has an attribute called eyeColor. I don't know what the actual percentages are, but let's say 60% of people have brown eyes, 30% have blue eyes, and 10% have green eyes.
Using this class I set the chances, out of 100, of returning any given eye color.
To do this, I use a TreeMap and choose a random double between 0, and 100 (inclusive). Then I return the value using the TreeMap's ceilingEntry method, unless that would return a null. In that case I return the value from the floorEntry method.
The restriction is that the sum of all the chances must equal 100, or nearly so, to return anything.
How can I make this data structure run faster, and make the code more elegant?
My Data Structure:
import java.util.TreeMap;
import java.util.concurrent.ThreadLocalRandom;
/**
* Objects of this class can have object or primitive types added to them and
* retrieved randomly with a different chance for different objects.
* <p>
* This is done by having the user include a "percentage chance" when adding new
* elements.
* <p>
* The percentage chance represents the percentage, out of 100, that the added
* element will be returned when the getRandomElement() method is called.
* <p>
* The sum of all the percentage chances should never be greater than 100 or the
* program will throw an IllegalArgumentException.
*/
public final class RandomTree<T> {
// holds the objects and primitives to be randomly returned
private TreeMap<Double, T> tree;
// keeps track of whether the RandomSet is full
private double sum;
public RandomTree() {
// contains the values to be randomly returned with getRandomElement()
this.tree = new TreeMap<>();
// keeps track of the sum of the percentages
this.sum = 0.0;
}
/**
* Adds a new object or primitive to the RandomTree. The percentChance
* argument represents the chances, out of 100, that the element will be
* return when the getRandomElement() method is called.
* <p>
* The sum of all the percentage chances including the given percentChance
* argument must be less than or equal to 100. Also, the percentChance
* argument must be greater than zero. Otherwise, the program throws
* an IllegalArgumentException.
*
* @param object The object or primitive to add.
* @param percentChance The chance of returning the object argument.
*/
public void add(final T object, final double percentChance) {
this.sum += percentChance;
// do not allow negative percent chances
if (percentChance <= 0.0) {
throw new IllegalArgumentException("percentChance must be > 0.0");
// prevent unnecessary exception throwing over being slightly more than 100.0
} else if (Math.abs(this.sum - 100.0) < 0.1 && this.sum != 100.0) {
this.sum = 100.0;
this.tree.put(this.sum, object);
// do not allow values to be above 100.0
} else if (this.sum > 100.0) {
throw new IllegalArgumentException(this.sum + " is > 100.");
// prevent unnecessary exception throwing over being slightly less than 100.0
} else if (100.0 - this.sum < 0.1 && this.sum != 100.0) {
this.sum = 100.0;
this.tree.put(this.sum, object);
} else // add the key and value to this.tree
this.tree.put(this.sum, object);
}
/**
* Returns a getRandomRace element from this.values.
* Elements with higher associated percentage-change values (in this.keys)
* are more likely to be returned.
* <p>
* Throws an IllegalArgumentException if this.sum is not equal to 100.
*/
public T getRandomElement() {
// don't allow retrieval before this.sum == 100.0
if (this.sum != 100.0)
throw new IllegalArgumentException("sum == " + this.sum);
double choice = ThreadLocalRandom.current().nextDouble(Math.nextUp(100.0));
final T obj = this.tree.ceilingEntry(choice).getValue();
if (obj != null)
return obj;
else
return this.tree.floorEntry(choice).getValue();
}
/**
* Returns the sum of the percentage chances added to this RandomTree.
*
* @return The sum of the percentage chances added to this RandomTree.
*/
public double getSum() {
return this.sum;
}
}
Test Class:
public class RandomTreeTest {
public static void main(String[] args) {
RandomTree<String> randTree = new RandomTree<>();
randTree.add("ten", 10.0);
randTree.add("twenty", 20.0);
randTree.add("thirty", 30.0);
randTree.add("forty", 40.0);
int countTens = 0;
int countTwenties = 0;
int countThirties = 0;
int countForties = 0;
final double iterationNumber = 1000.0;
for(int i = 0; i < iterationNumber; i++) {
String num = randTree.getRandomElement();
switch(num) {
case "ten":
countTens++;
break;
case "twenty":
countTwenties++;
break;
case "thirty":
countThirties++;
break;
case "forty":
countForties++;
break;
}
}
double percentOfTens = (countTens / iterationNumber) * 100;
double percentOfTwenties = (countTwenties / iterationNumber) * 100;
double percentOfThirties = (countThirties / iterationNumber) * 100;
double percentOfForties = (countForties / iterationNumber) * 100;
String msg = "tens: " + percentOfTens + "%" + System.lineSeparator();
msg += "twenties: " + percentOfTwenties + "%" + System.lineSeparator();
msg += "thirties: " + percentOfThirties + "%" + System.lineSeparator();
msg += "forties: " + percentOfForties + "%" + System.lineSeparator();
System.out.println(msg);
}
}
RandomTree(int[] percentages, T[] items)
? You can then enforcesum(percentages) == 100
much more effectively. From an API design perspective, it's problematic to support anadd
function where you have specific input restrictions across multiple calls. It's easy for clients to screw up the input. \$\endgroup\$