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>>();
addAll(items);
}
private void addAll(List<T> items) {
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()) {
itemDataList.add(new ItemData<T>(entry.getKey(), entry.getValue(), 0));
}
}
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>();
list.add("sachin");
list.add("sachin");
list.add("sachin");
list.add("rahul");
list.add("rahul");
list.add("ganguly");
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);
}
}
