# Weighted probabilistic sampling

Problem description. Returns strings with probability determined by the frequency of each of the strings. eg: if "foo" has weight of 50% and "bar" has weight of another 50% then both foo and bar should be 5 and 5 times each given that 10 tries were made.

If question is unclear let me know I will reply asap. Looking for code review, optimizations and best practice.

Also verifying that complexity of next() is undefined due to probabilistic nature.

public final class WeightedRandom<T> {

private final List<ItemData<T>> itemDataList;
private final int size;
private int count;

/**
* Takes in a list of items.
*
* @param items the list of items
* @throws NullPointerException if items is null.
* @throws IllegalArgumentException if the input list size is zero.
*/
public WeightedRandom (List<T> items) {
if (items.size() == 0) throw new IllegalArgumentException("The size of list should be greater than zero.");
size = items.size();
itemDataList = new ArrayList<ItemData<T>>();
}

final Map<T, Integer> map = new HashMap<T, Integer>();
for (T item : items) {
int val = 0;
if (map.containsKey(item)) {
val = map.get(item);
}
map.put(item, val + 1);
}

for (Entry<T, Integer> entry : map.entrySet()) {
}
}

private static class ItemData<T> {
T item;
int frequency;
int usedCount;

ItemData (T item, int frequency, int usedCount) {
this.item = item;
this.frequency =  frequency;
this.usedCount = usedCount;
}
}

/**
*  Returns strings with probability determined by the frequency
*  of each of the strings.
*  eg: if "foo" has weight of 50% and "bar" has weight of another 50% then both foo and
*  bar should be 5 and 5 times each given that 10 tries were made
*
*  @return the next item in the weighted probabilistic manner.
*/
public synchronized T next() {
if (count == size) {
clear();
}

ItemData<T> data = getRandomData();
// until we reach the item who is not-exhausted, keep trying.
while (data.usedCount == data.frequency) {
data = getRandomData();
}

data.usedCount++;
count++;
return data.item;
}

private ItemData<T> getRandomData() {
int random = new Random().nextInt(itemDataList.size());
return itemDataList.get(random);
}

/**
* Resets the weights, which are exptected to be modified
* in the duration of the code.
*/
public synchronized void clear() {
count = 0;
for (ItemData<T> data : itemDataList)  {
data.usedCount = 0;
}
}

public static void main(String[] args) {
List<String> list = new ArrayList<String>();

WeightedRandom<String> wrr1 = new WeightedRandom<String>(list);
WeightedRandom<String> wrr2 = new WeightedRandom<String>(list);

/*
* tests the random behavior, by checking output of two objects differ.
* This testing too is probablistic.
*/
boolean result1 = false;
int count = 0;
while (count < 6) {
if (!wrr1.next().equals(wrr2.next())) {
result1  = true;
break;
}
count++;
}

System.out.println(" random ? Answer: " + result1);

/*
* testing that weights are honored.
*/
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("sachin", 6);
map.put("rahul", 4);
map.put("ganguly", 2);
count = 0;
wrr1.clear();
while (count < 12) {
map.remove(wrr1.next());
count++;
}

boolean result2 = true;
for (Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() != 0) {
result2 = false;
break;
}
}
System.out.println(" weights obeyed ? : Answer: " +  result2);

}
}


You are not clear in your question what the purpose of your class is... the code suggests that, for an input list of size k, that once you have 'pulled' k items from the WeightedRandom that the histogram of the results will exactly match the histogram of the input frequencies. Additionally, for every 2k elements you pull, the relative frequency will remain unchanged.

Unfortunately, your code does not actually do a very good job of randomizing the values. For example, consider data with the input frequency of [a, b, b, b, b, b, b, b, b, b] (i.e. 1 a and 9 b values). What your code is supposed to do is:

For every 10 times we pull values from the WeightedRandom:

• one value will be a
• the remaining 9 will be b
• the a value should be randomly distributed among the b values.

The problem you have is with the random distribution. Your code does this:

• it creates 2 buckets, one for a with frequency 1, one for b with frequency 9.
• it then does a random selection between the 2 buckets ( int random = new Random().nextInt(itemDataList.size()); )
• this means that the odds are 50/50 that it will chose a the first time for every 10
• if it does not choose a, it will 50/50 choose a the next time....

The bottom line is that the odds of a being at the front of the list are 50%, but only 0.2% that it will be the last item. In reality, it should be 10% likely to end up at any location...

The logical way to solve this problem is so much simpler than what you have done:

• create an array with the data members
• shuffle it
• walk the shuffled data when you need an item
• when you reach the end, re-shuffle the data, and start again.

The code to do it is:

public final class WeightedRandom<T> {

private final List<T> itemData;
private int cursor = 0;

public WeightedRandom (List<T> items) {
if (items.size() == 0) throw new IllegalArgumentException("The size of list should be greater than zero.");
// take a copy of the list.
itemData = new ArrayList<T>(items);
}

public synchronized T next() {
cursor--;
if (cursor < 0) {
Collections.shuffle(itemData);
cursor = itemData.size() - 1;
}
return itemData.get(cursor);
}

public synchronized void clear() {
cursor = 0;
}
}


The code looks nice. A few minor improvements or ideas:

1. You need only two simple methods to make it an Iterator:

public final class WeightedRandom<T> implements Iterator<T> {

...

@Override
public boolean hasNext() {
return true;
}

@Override
public void remove() {
throw new UnsupportedOperationException();
}
}


It could be useful/convenient for clients.

2. if (items.size() == 0) {
throw new IllegalArgumentException("The size of list should be greater than zero.");
}


items.isEmpty() would be a little bit readable and you could use Guava's Preconditons too to make it more fluent and explicit:

checkNotNull(items, "items cannot be null");
checkArgument(!items.isEmpty(), "The size of list should be greater than zero.");

3. itemDataList = new ArrayList<ItemData<T>>();


This could be in the declaration:

import static com.google.common.collect.Lists.newArrayList;

...

private final List<ItemData<T>> itemDataList = newArrayList();

4. The constructor of ItemData is always called with zero usedCount. Consider setting a default value for that parameter and remove it from the signature:

private static class ItemData<T> {
T item;
int frequency;
int usedCount = 0;

ItemData(final T item, final int frequency) {
this.item = item;
this.frequency = frequency;
}
}


Currently the number 0 is a magic number in the constructor call:

itemDataList.add(new ItemData<T>(entry.getKey(), entry.getValue(), 0));


Readers have to check the constructor of ItemData to figure out what it means. An explanatory local variable be an improvement. (Clean Code by Robert C. Martin, G19: Use Explanatory Variables; Refactoring: Improving the Design of Existing Code by Martin Fowler, Introduce Explaining Variable)

5. addAll would be a little bit shorter with a Multiset:

private void addAll(final List<T> items) {
final Multiset<T> multiset = HashMultiset.create();

for (final Entry<T> entry: multiset.entrySet()) {
}
}

6. Javadoc of next speaks about strings but it could be any type (T). It's a little bit confusing.

7. Javadoc typo: exptected (Eclipse has spell check.)

The code looks nice and I think that the main() method has the biggest room for improvements here. You could automatize testing with JUnit. It would make it a self-checking test without manual intervention and manual result verification.

First, you need to make the class deterministic. You can do that with modifying the class to be able to use a mocked Random instance or a Random instance with a fixed seed. (If the seed is the same the returned values are predictable.)

A way for that is moving the Random instance to a field:

private final Random random = new Random();

...

private ItemData<T> getRandomData() {
final int randomIndex = random.nextInt(itemDataList.size());
return itemDataList.get(randomIndex);
}


Then, you could modify it with reflection (Apache Commons Lang has a nice FieldUtils for that).

Another way is creating a constructor which has a Random parameter:

private final Random random;

public WeightedRandom(final List<T> items) {
this(items, new Random());
}

public WeightedRandom(final List<T> items, final Random random) {
checkNotNull(items, "items cannot be null");
checkArgument(!items.isEmpty(),
"The size of list should be greater than zero.");
size = items.size();
this.random = checkNotNull(random, "random cannot be null");

}


It's worth noting that

• this reduces coupling between the WeightedRandom and Random classes,
• it also could be useful if a client needs to use SecureRandom instead of Random,
• does not require reflection (and doesn't depend on the name of the field),
• it's a quite good example that making code testable improves its design/quality.

Finally, your tests rewritten with extensive use of Google Guava to make them sort:

import static com.google.common.collect.Lists.newArrayList;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.CoreMatchers.not;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.Assert.assertTrue;

import java.util.Iterator;
import java.util.List;
import java.util.Random;

import org.junit.Test;

public class WeightedRandomTest {

// @formatter:off
private final List<String> list = newArrayList(
"sachin",
"sachin",
"sachin",
"rahul",
"rahul",
"ganguly");
// @formatter:off

@Test
public void testRandomBehaviour() throws Exception {
final long seedOne = 1;
final long seedTwo = seedOne + 1;
final WeightedRandom<String> randomOne =
createWeightedRandomWithSeed(list, seedOne);
final WeightedRandom<String> randomTwo =
createWeightedRandomWithSeed(list, seedTwo);

final int elementCount = 6;
final List<String> elementsOne =
getElements(randomOne, elementCount);
final List<String> elementsTwo =
getElements(randomTwo, elementCount);

assertThat(elementsOne, not(equalTo(elementsTwo)));
}

@Test
public void testWeightsAreHonored() {
final WeightedRandom<String> weightedRandom =
new WeightedRandom<String>(list);
final Multiset<String> expectedDistribution =
HashMultiset.create();
expectedDistribution.setCount("sachin", 6);
expectedDistribution.setCount("rahul", 4);
expectedDistribution.setCount("ganguly", 2);

final List<String> randomElements =
getElements(weightedRandom, 12);

Multisets.removeOccurrences(expectedDistribution,
HashMultiset.create(randomElements));
assertTrue(expectedDistribution.isEmpty());
}

private List<String> getElements(
final WeightedRandom<String> weightedRandom,
final int count) {
final Iterator<String> limitedIterator =
Iterators.limit(weightedRandom, count);
return Lists.newArrayList(limitedIterator);
}

private WeightedRandom<String> createWeightedRandomWithSeed(
final List<String> list, final long seed)
throws IllegalAccessException {
final Random seededRandom = new Random(seed);
return new WeightedRandom<String>(list, seededRandom);
}

}